login
A338707
Number of 3-linear trees on n nodes.
3
0, 0, 0, 0, 0, 0, 0, 1, 5, 22, 74, 219, 576, 1394, 3150, 6733, 13744, 26969, 51185, 94323, 169453, 297533, 512006, 865050, 1437739, 2353756, 3801041, 6060918, 9552826, 14894428, 22991659, 35159606, 53299703, 80137271, 119563216, 177091225, 260504790, 380720841
OFFSET
1,9
COMMENTS
A k-linear tree is a tree with exactly k vertices of degree 3 or higher all of which lie on a path. - Andrew Howroyd, Dec 17 2020
LINKS
Tanay Wakhare, Eric Wityk, and Charles R. Johnson, The proportion of trees that are linear, Discrete Mathematics, 343.10 (2020): 112008. Also on arXiv, arXiv:1901.08502 [math.CO], 2019-2020. See Tables 1 and 2 (but beware errors).
FORMULA
G.f.: x^3*(P(x)-1)*((P(x) - 1/(1-x))^2/(1-x)^2 + (P(x^2) - 1/(1-x^2))/(1-x^2))/2 where P(x) is the g.f. of A000041. - Andrew Howroyd, Dec 17 2020
PROG
(PARI) seq(n)={my(p=1/(eta(x + O(x^(n-5))))); Vec(x^3*(p-1)*((p - 1/(1-x))^2/(1-x)^2 + (subst(p, x, x^2) - 1/(1-x^2))/(1-x^2))/2, -n)} \\ Andrew Howroyd, Dec 17 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Nov 05 2020, using data supplied by Eric Wityk
EXTENSIONS
Terms a(31) and beyond from Andrew Howroyd, Dec 17 2020
STATUS
approved