A380363 Triangle read by rows: T(n,k) is the number of linear trees with n vertices and k vertices of degree >= 3, 0 <= k <= max(0, floor(n/2)-1).

1, 1, 1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 7, 3, 1, 11, 10, 1, 1, 17, 24, 5, 1, 25, 56, 22, 1, 1, 36, 114, 74, 6, 1, 50, 224, 219, 37, 1, 1, 70, 411, 576, 158, 8, 1, 94, 733, 1394, 591, 58, 1, 1, 127, 1252, 3150, 1896, 304, 9, 1, 168, 2091, 6733, 5537, 1342, 82, 1

Offset

0,8

Comments

A linear tree is a tree with all vertices of degree > 2 belonging to a single path. These are equinumerous with lobster graphs. All trees having at most 3 vertices of degree > 2 are linear trees.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..2501 (rows 0..100)

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. See Table 1.

Eric Weisstein's World of Mathematics, Lobster Graph.

Example

Triangle begins:
  1;
  1;
  1;
  1;
  1,   1;
  1,   2;
  1,   4,    1;
  1,   7,    3;
  1,  11,   10,    1;
  1,  17,   24,    5;
  1,  25,   56,   22,    1;
  1,  36,  114,   74,    6;
  1,  50,  224,  219,   37,   1;
  1,  70,  411,  576,  158,   8;
  1,  94,  733, 1394,  591,  58, 1;
  1, 127, 1252, 3150, 1896, 304, 9;
  ...

Prog

(PARI)
G(n, y)={my(p=1/eta(x + O(x^n)), p2=1/eta(x^2 + O(x^n)),
  g1=(p - 1/(1-x))^2/((1 - x)*(1 - x*y*(p-1)/(1-x))),
  g2=(p2 - 1/(1-x^2))*(1 + x + x*y*(p-1))/((1 - x^2)*(1 - x^2*y^2*(p2-1)/(1-x^2))) );
  x^2*y^2*(g1 + g2)/2 + x*y*(p - 1/((1 + x)*(1 - x)^2)) + 1/(1-x)
}
T(n)=[Vecrev(p) | p<-Vec(G(n, y))]
{my(A=T(15)); for(i=1, #A, print(A[i]))}

Crossrefs

Columns 0..4 are A000012, A004250(n-1), A338706, A338707, A338708.

Row sums are A130131.

Cf. A238415 (initial columns same up to k=3).

Sequence in context: A191306 A191525 A066633 * A238415 A283826 A088443

Adjacent sequences: A380360 A380361 A380362 * A380364 A380365 A380366

Keyword

nonn,tabf

Author

Andrew Howroyd, Jan 26 2025

Status

approved