|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|