A338708 Number of 4-linear trees on n nodes.
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6, 37, 158, 591, 1896, 5537, 14812, 37133, 87841, 198267, 429199, 896731, 1814978, 3572810, 6858774, 12874977, 23679669, 42752787, 75887244, 132618635, 228443753, 388297169, 651868064, 1081771385, 1775876764, 2885944062, 4645393253, 7410678577, 11722238660, 18394159344
Offset: 1
Keywords
Links
- Andrew Howroyd, Table of n, a(n) for n = 1..1000
- Tanay Wakhare, Eric Wityk, and Charles R. Johnson, The proportion of trees that are linear, Discrete Mathematics 343.10 (2020): 112008. Also Corrigendum and preprint arXiv:1901.08502 [math.CO], 2019-2020. See Tables 1 and 2 (but beware errors).
Programs
-
PARI
seq(n)={my(A=O(x^(n-5)), p=1/eta(x + A), p2=1/eta(x^2 + A)); Vec(((p - 1/(1-x))^2*(p - 1)^2/(1 - x)^3 + (p2 - 1/(1 - x^2))*(p2 - 1)/((1 - x^2)*(1 - x)))/2, -n)} \\ Andrew Howroyd, Jan 26 2025
Formula
G.f.: x^4*((P(x) - 1/(1 - x))^2*(P(x) - 1)^2/(1 - x)^3 + (P(x^2) - 1/(1 - x^2))*(P(x^2) - 1)/((1 - x^2)*(1 - x)))/2 where P(x) is the g.f. of A000041. - Andrew Howroyd, Jan 26 2025
Extensions
a(26) onwards from Andrew Howroyd, Jan 26 2025