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

Author

Andrew Howroyd, Jan 26 2025

Keywords

• nonn
• tabf

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.

Examples

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

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.

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