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

Author

Allan Bickle, Jun 10 2021

Keywords

• easy
• nonn

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

• 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).

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).

Programs

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 *)

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

Extensions

Title changed by Allan Bickle, Apr 05 2022