A338706 Number of 2-linear trees on n nodes.

0, 0, 0, 0, 0, 1, 3, 10, 24, 56, 114, 224, 411, 733, 1252, 2091, 3393, 5408, 8440, 12982, 19650, 29388, 43394, 63430, 91754, 131584, 187057, 263932, 369624, 514253, 710838, 976876, 1334828, 1814492, 2454011, 3303436, 4426627, 5906599, 7848883, 10389557

Offset: 1

Author

N. J. A. Sloane, Nov 05 2020, using data supplied by Eric Wityk

Keywords

• nonn

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

Empirically the partial sums of A000147. - Sean A. Irvine, Jul 11 2022

Examples

			The a(6) = 1 tree is:
         o   o
         |   |
     o---o---o---o
		

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

Crossrefs

Column k=2 of A380363 and A238415.

Cf. A000041, A000147, A130131, A338707, A338708.

Programs

PARI

seq(n)=my(p=1/(eta(x + O(x^(n-3))))); Vec(((x*(p - 1/(1-x)))^2 + x^2*(subst(p,x,x^2) - 1/(1-x^2)))/(2*(1-x)), -n) \\ Andrew Howroyd, Dec 17 2020

Formula

G.f.: ((x*(P(x) - 1/(1-x)))^2 + x^2*(P(x^2) - 1/(1-x^2)))/(2*(1-x)) where P(x) is the g.f. of A000041. - Andrew Howroyd, Dec 17 2020

Extensions

Terms a(31) and beyond from Andrew Howroyd, Dec 17 2020