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,11

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

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

Prog

(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

Crossrefs

Column k=4 of A380363.

Cf. A000041, A130131, A338706, A338707.

Sequence in context: A362336 A349857 A047670 * A129552 A293800 A327611

Adjacent sequences: A338705 A338706 A338707 * A338709 A338710 A338711

Keyword

nonn

Author

N. J. A. Sloane, Nov 05 2020

Extensions

a(26) onwards from Andrew Howroyd, Jan 26 2025

Status

approved