login
Number of 3-linear trees on n nodes.
5

%I #16 Jan 26 2025 21:47:41

%S 0,0,0,0,0,0,0,1,5,22,74,219,576,1394,3150,6733,13744,26969,51185,

%T 94323,169453,297533,512006,865050,1437739,2353756,3801041,6060918,

%U 9552826,14894428,22991659,35159606,53299703,80137271,119563216,177091225,260504790,380720841

%N Number of 3-linear trees on n nodes.

%C 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

%H Andrew Howroyd, <a href="/A338707/b338707.txt">Table of n, a(n) for n = 1..1000</a>

%H Tanay Wakhare, Eric Wityk, and Charles R. Johnson, <a href="https://doi.org/10.1016/j.disc.2020.112008">The proportion of trees that are linear</a>, Discrete Mathematics 343.10 (2020): 112008. Also <a href="https://doi.org/10.1016/j.disc.2020.112284">Corrigendum</a> and preprint <a href="https://arxiv.org/abs/1901.08502">arXiv:1901.08502 [math.CO]</a>, 2019-2020. See Tables 1 and 2 (but beware errors).

%F 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

%o (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

%Y Column k=3 of A380363 and A238415.

%Y Cf. A000041, A130131, A338706, A338708.

%K nonn

%O 1,9

%A _N. J. A. Sloane_, Nov 05 2020, using data supplied by Eric Wityk

%E Terms a(31) and beyond from _Andrew Howroyd_, Dec 17 2020