%I #58 Feb 21 2024 08:26:49
%S 1,1,2,4,11,32,117,468,2151,10722,58071,333774,2018321,12678506,
%T 82035085,542520052,3646124339,24791545874,169986552195,1172526610674,
%U 8122332718341,56435590886610,392969320828713,2740480494041976,19132214719583207,133671249471111626
%N Number of (unlabeled) 7-paths with n vertices.
%C 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.
%C 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.
%C Recurrences appear in the papers by Bickle, Eckhoff, and Markenzon et al.
%D 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.]
%H Allan Bickle, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL25/Bickle/bickle5.html">How to Count k-Paths</a>, J. Integer Sequences, 25 (2022) Article 22.5.6.
%H Allan Bickle, <a href="https://doi.org/10.20429/tag.2024.000105">A Survey of Maximal k-degenerate Graphs and k-Trees</a>, Theory and Applications of Graphs 0 1 (2024) Article 5.
%H J. Eckhoff, <a href="https://doi.org/10.1002/jgt.3190170112">Extremal interval graphs</a>, J. Graph Theory 17 1 (1993), 117-127.
%H L. Markenzon, O. Vernet, and P. R. da Costa Pereira, <a href="https://doi.org/10.1016/j.dam.2008.05.015">A clique-difference encoding scheme for labelled k-path graphs</a>, Discrete Appl. Math. 156 (2008), 3216-3222.
%H <a href="/index/Rec#order_13">Index entries for linear recurrences with constant coefficients</a>, signature (20,-134,200,1502,-6120,-200,35440,-41269,-66380,141454,840,-135912,70560).
%F 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;
%F 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.
%F 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
%t 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 *)
%Y Column 7 of A320750.
%Y The numbers of unlabeled k-paths for k = 2..6 are given in A005418, A001998, A056323, A056324, and A056325, respectively.
%Y The sequences above converge to A103293(n+1).
%K easy,nonn
%O 9,3
%A _Allan Bickle_, Jun 10 2021
%E Title changed by _Allan Bickle_, Apr 05 2022