A370770 Triangle read by rows: T(n,k) is the number of k-trees with n unlabeled nodes.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 2, 1, 1, 1, 1, 6, 5, 2, 1, 1, 1, 1, 11, 12, 5, 2, 1, 1, 1, 1, 23, 39, 15, 5, 2, 1, 1, 1, 1, 47, 136, 58, 15, 5, 2, 1, 1, 1, 1, 106, 529, 275, 64, 15, 5, 2, 1, 1, 1, 1, 235, 2171, 1505, 331, 64, 15, 5, 2, 1, 1, 1

Offset

0,12

Links

Table of n, a(n) for n=0..77.

Carlos A. Alfaro, Jesús Uriel Medrano, and Iván Téllez Téllez, The Smith normal form of distance matrices of high dimensional trees, Comput. Appl. Math. 45 (2026), 226. See also arXiv:2510.04471 [math.CO], 2025.

Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.

Andrew Gainer-Dewar, Gamma-Species and the Enumeration of k-Trees, Electronic Journal of Combinatorics, Volume 19 (2012), #P45.

Andrew Gainer-Dewar and Ira M. Gessel, Counting unlabeled k-trees, arXiv:1309.1429 [math.CO], 2013-2014.

Andrew Gainer-Dewar and Ira M. Gessel, Counting unlabeled k-trees, J. Combin. Theory Ser. A 126 (2014), 177-193.

Andrew Howroyd, SageMath Program code (from Andrew Gainer-Dewar reference).

Formula

T(n,k) = A370771(n,k) + A370772(n,k) - A370773(n,k).

Example

Triangle begins:
  1;
  1,   1;
  1,   1,   1;
  1,   1,   1,   1;
  1,   2,   1,   1,  1;
  1,   3,   2,   1,  1,  1;
  1,   6,   5,   2,  1,  1, 1;
  1,  11,  12,   5,  2,  1, 1, 1;
  1,  23,  39,  15,  5,  2, 1, 1, 1;
  1,  47, 136,  58, 15,  5, 2, 1, 1, 1;
  1, 106, 529, 275, 64, 15, 5, 2, 1, 1, 1;
  ...

Crossrefs

Columns k=0..7 are A000012, A000055, A054581, A078792, A078793, A201702, A202037, A322754.

Cf. A135021 (labeled version), A370771, A370772, A370773.

Sequence in context: A030358 A118914 A135063 * A124010 A212171 A337255

Adjacent sequences: A370767 A370768 A370769 * A370771 A370772 A370773

Keyword

nonn,tabl

Author

Andrew Howroyd, Mar 01 2024

Status

approved