A345207 Number of (unlabeled) 7-paths with n vertices.

1, 1, 2, 4, 11, 32, 117, 468, 2151, 10722, 58071, 333774, 2018321, 12678506, 82035085, 542520052, 3646124339, 24791545874, 169986552195, 1172526610674, 8122332718341, 56435590886610, 392969320828713, 2740480494041976, 19132214719583207, 133671249471111626

Offset

9,3

Comments

A k-path with order n at least k+2 is a k-tree with exactly two k-leaves (vertices of degree k). It can be constructed from a clique with k+1 vertices by iteratively adding a new degree k vertex adjacent to an existing clique containing an existing k-leaf.

Also, the number of equivalence classes of strings of length n-9 using a maximum of seven different numbers that are equivalent when they can be made the same by permutation of their numbers and possible reversal of the string.

Recurrences appear in the papers by Bickle, Eckhoff, and Markenzon et al.

References

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2.]

Links

Table of n, a(n) for n=9..34.

Allan Bickle, How to Count k-Paths, J. Integer Sequences, 25 (2022) Article 22.5.6.

Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.

J. Eckhoff, Extremal interval graphs, J. Graph Theory 17 1 (1993), 117-127.

L. Markenzon, O. Vernet, and P. R. da Costa Pereira, A clique-difference encoding scheme for labelled k-path graphs, Discrete Appl. Math. 156 (2008), 3216-3222.

Index entries for linear recurrences with constant coefficients, signature (20,-134,200,1502,-6120,-200,35440,-41269,-66380,141454,840,-135912,70560).

Formula

a(n) = (7^(n-9) + 21*5^(n-9) + 70*4^(n-9) + 315*3^(n-9) + 924*2^(n-9) + 232*7^((n-9)/2) + 700*4^((n-9)/2) + 840*3^((n-9)/2) + 1008*2^((n-9)/2) + 2975)/10080 for n>9 odd;

a(n) = (7^(n-9) + 21*5^(n-9) + 70*4^(n-9) + 315*3^(n-9) + 924*2^(n-9) + 76*7^((n-8)/2) + 280*4^((n-8)/2) + 420*3^((n-8)/2) + 504*2^((n-8)/2) + 2975)/10080 for n even.

a(n) = 20*a(n-1) - 134*a(n-2) + 200*a(n-3) + 1502*a(n-4) - 6120*a(n-5) - 200*a(n-6) + 35440*a(n-7) - 41269*a(n-8) - 66380*a(n-9) + 141454*a(n-10) + 840*a(n-11) - 135912*a(n-12) + 70560*a(n-13) for n > 22. - Stefano Spezia, Aug 01 2021

Mathematica

LinearRecurrence[{20, -134, 200, 1502, -6120, -200, 35440, -41269, -66380, 141454, 840, -135912, 70560}, {1, 1, 2, 4, 11, 32, 117, 468, 2151, 10722, 58071, 333774, 2018321, 12678506}, 26] (* Stefano Spezia, Aug 01 2021 *)

Crossrefs

Column 7 of A320750.

The numbers of unlabeled k-paths for k = 2..6 are given in A005418, A001998, A056323, A056324, and A056325, respectively.

The sequences above converge to A103293(n+1).

Sequence in context: A124504 A056324 A056325 * A103293 A123418 A123412

Adjacent sequences: A345204 A345205 A345206 * A345208 A345209 A345210

Keyword

easy,nonn

Author

Allan Bickle, Jun 10 2021

Extensions

Title changed by Allan Bickle, Apr 05 2022

Status

approved