A370770 -id:A370770 - cp's OEIS frontend

A054581 Number of unlabeled 2-trees with n nodes.

0, 1, 1, 1, 2, 5, 12, 39, 136, 529, 2171, 9368, 41534, 188942, 874906, 4115060, 19602156, 94419351, 459183768, 2252217207, 11130545494, 55382155396, 277255622646, 1395731021610, 7061871805974, 35896206800034, 183241761631584

Offset: 1

Vladeta Jovovic, Apr 11 2000

A 2-tree is recursively defined as follows: K_2 is a 2-tree and any 2-tree on n+1 vertices is obtained by joining a vertex to a 2-clique in a 2-tree on n vertices. Care is needed with the term 2-tree (and k-tree in general) because it has at least two commonly used definitions.
A036361 gives the labeled version of this sequence, which has an easy formula analogous to Cayley's formula for the number of trees.
Also, number of unlabeled 3-gonal 2-trees with n 3-gons.

			a(1)=0 because K_1 is not a 2-tree;
a(2)=a(3)=1 because K_2 and K_3 are the only 2-trees on those sizes.
a(4)=1 because there is a unique example obtained by joining a triangle to K_3 along an edge (thus forming K_4\e). The two graphs on 5 nodes are obtained by joining a triangle to K_4\e, either along the shared edge or along one of the non-shared edges.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 327-328.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 76, t(x), (3.5.19).

Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
T. Fowler, I. Gessel, G. Labelle, and P. Leroux, The specification of 2-trees, Adv. Appl. Math. 28 (2) (2002) 145-168, Table 1.
Nick Early, Anaëlle Pfister, and Bernd Sturmfels, Minimal Kinematics on M_{0,n}, arXiv:2402.03065 [math.AG], 2024.
Andrew Gainer-Dewar, Gamma-Species and the Enumeration of k-Trees, Electronic Journal of Combinatorics, Volume 19 (2012), #P45. - From _N. J. A. Sloane_, Dec 15 2012
Gilbert Labelle, Cédric Lamathe, and Pierre Leroux, Labeled and unlabeled enumeration of k-gonal 2-trees, arXiv:math/0312424 [math.CO], 2003.
Eric Weisstein's World of Mathematics, k-Tree.
Index entries for sequences related to trees

Column k=3 of A340811, column k=2 of A370770.

Cf. A000272 (labeled trees), A036361 (labeled 2-trees), A036362 (labeled 3-trees), A036506 (labeled 4-trees), A000055 (unlabeled trees).

Additional comments from Gordon F. Royle, Dec 02 2002

Missing initial term 0 inserted by Brendan McKay, Aug 07 2023

A078793 Number of unlabeled 4-trees on n vertices.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 2, 5, 15, 64, 331, 2150, 15817, 127194, 1077639, 9466983, 85252938, 782238933, 7283470324, 68639621442, 653492361220, 6276834750665, 60759388837299, 592227182125701, 5808446697002391, 57289008242377068, 567939935463185078

Offset: 1

Gordon F. Royle, Dec 05 2002

nonn

A k-tree is recursively defined as follows: K_k is a k-tree and any k-tree on n+1 vertices is obtained by joining a vertex to a k-clique in a k-tree on n vertices.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 328.

Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
P. Di Francesco, P. Zinn-Justin, and J.-B. Zuber, Determinant Formulae for some Tiling Problems and Application to Fully Packed Loops, arXiv:math-ph/0410002, 2004.
Andrew Gainer-Dewar, Gamma-Species and the Enumeration of k-Trees, Electronic Journal of Combinatorics, Volume 19 (2012), #P45. - From _N. J. A. Sloane_, Dec 15 2012
Eric Weisstein's World of Mathematics, k-Tree

Column k=4 of A370770.

Cf. A036506 (labeled 4-trees).

More terms from Andrew R. Gainer, Dec 03 2011

A135021 Triangle read by rows: T(n,r) = number of maximum r-uniform acyclic hypergraphs of order n and size n-r+1, 1 <= r <= n+1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 16, 6, 1, 1, 1, 125, 70, 10, 1, 1, 1, 1296, 1215, 200, 15, 1, 1, 1, 16807, 27951, 5915, 455, 21, 1, 1, 1, 262144, 799708, 229376, 20230, 896, 28, 1, 1, 1, 4782969, 27337500, 10946964, 1166886, 55566, 1596, 36, 1, 1, 1, 100000000, 1086190605, 618435840, 82031250, 4429152, 131250, 2640, 45, 1, 1

Offset: 0

John Nnamdi (john_info_2008(AT)bbvczx.com), Feb 10 2008

T(n,r) is the number of (r-1)-trees on n nodes. - Andrew Howroyd, Mar 02 2024

			From _Bruno Berselli_, Dec 08 2012: (Start)
Triangle begins:
  1;
  1,       1;
  1,       1,        1;
  1,       3,        1,        1;
  1,      16,        6,        1,       1;
  1,     125,       70,       10,       1,     1;
  1,    1296,     1215,      200,      15,     1,    1;
  1,   16807,    27951,     5915,     455,    21,    1,  1;
  1,  262144,   799708,   229376,   20230,   896,   28,  1, 1;
  1, 4782969, 27337500, 10946964, 1166886, 55566, 1596, 36, 1, 1;
(End)

G. C. Greubel, Table of n, a(n) for n = 0..1325 (rows 0..50)
L. W. Beineke and R. E. Pipert, The number of labeled k-dimensional trees, J. Comb. Theory 6 (2) (1969) 200-205, formula (1).
Jian-fang Wang and Hai-zhu Li, Enumeration of Maximum Acyclic Hypergraphs, Acta Mathematicae Applicatae Sinica, English Series, 2002 vol.18 number 2, page 215. [Broken link]

Columns 1..5 are A000012, A000272, A036361, A036362, A036506.

Cf. A370770 (unlabeled version).

seq(seq(binomial(n,r-1)*(n*(r-1)-r^2+2*r)^(n-r-1),r=1..n),n=1..11);

T[n_, r_] := Binomial[n, r - 1]*(n (r - 1) - r^2 + 2 r)^(n - r - 1);
Table[T[n, r], {n, 1, 5}, {r, 1, n}] (* G. C. Greubel, Sep 16 2016 *)

T(n,r) = binomial(n,r-1)*(n*(r-1)-r^2+2*r)^(n-r-1) \\ Andrew Howroyd, Mar 02 2024

T(n,r) = binomial(n,r-1)*(n*(r-1)-r^2+2*r)^(n-r-1).

Diagonal r=n+1 inserted by Andrew Howroyd, Mar 02 2024

A078792 Number of unlabeled 3-trees on n vertices.

Original entry on oeis.org

0, 0, 1, 1, 1, 2, 5, 15, 58, 275, 1505, 9003, 56931, 372973, 2506312, 17165954, 119398333, 841244274, 5993093551, 43109340222, 312747109787, 2286190318744, 16826338257708, 124605344758149, 927910207739261, 6945172081954449, 52225283886702922

Offset: 1

Gordon F. Royle, Dec 05 2002

nonn

A k-tree is recursively defined as follows: K_k is a k-tree and any k-tree on n+1 vertices is obtained by joining a new vertex to a k-clique in a k-tree on n vertices.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 328.

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. - From _N. J. A. Sloane_, Dec 15 2012
Eric Weisstein's World of Mathematics, k-Tree.

Column k=3 of A370770.

Cf. A036362 (labeled 3-trees), A054581 (unlabeled 2-trees).

More terms from Andrew R. Gainer, Dec 03 2011

A201702 Number of unlabeled 5-trees on n nodes.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 1, 2, 5, 15, 64, 342, 2321, 18578, 168287, 1656209, 17288336, 188006362, 2105867058, 24108331027, 280638347609, 3310098377912, 39462525169310, 474697793413215, 5754095507495584, 70216415130786725, 861924378411516159, 10636562125193377459

Offset: 1

Andrew R. Gainer, Dec 03 2011

nonn

A k-tree is recursively defined as follows: K_k is a k-tree and any k-tree on n+1 vertices is obtained by joining a vertex to a k-clique in a k-tree on n vertices.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 328.

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. - From _N. J. A. Sloane_, Dec 15 2012
Eric Weisstein's World of Mathematics, k-Tree

Column k=5 of A370770.

Cf. A054581 (unlabeled 2-trees), A078792 (unlabeled 3-trees), A078793 (unlabeled 4-trees).

A202037 Number of unlabeled 6-trees on n nodes.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 1, 1, 2, 5, 15, 64, 342, 2344, 19090, 179562, 1878277, 21365403, 258965451, 3294561195, 43472906719, 589744428065, 8171396893523, 115094557122380, 1642269376265063, 23679803216530017, 344396036645439675, 5045351124912000756

Offset: 1

Andrew R. Gainer, Dec 09 2011

nonn

A k-tree is recursively defined as follows: K_k is a k-tree and any k-tree on n+1 vertices is obtained by joining a vertex to a k-clique in a k-tree on n vertices.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 328.

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. - From _N. J. A. Sloane_, Dec 15 2012

Column k=6 of A370770.

Cf. A054581 (unlabeled 2-trees), A078792 (unlabeled 3-trees), A078793 (unlabeled 4-trees), A201702 (unlabeled 5-trees)

A370771 Triangle read by rows: T(n,k) is the number of k-trees with n unlabeled nodes rooted at a front.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 4, 2, 1, 1, 1, 9, 6, 2, 1, 1, 1, 20, 21, 6, 2, 1, 1, 1, 48, 83, 25, 6, 2, 1, 1, 1, 115, 356, 126, 25, 6, 2, 1, 1, 1, 286, 1599, 745, 135, 25, 6, 2, 1, 1, 1, 719, 7434, 4784, 895, 135, 25, 6, 2, 1, 1, 1, 1842, 35381, 32372, 6846, 915, 135, 25, 6, 2, 1, 1

Offset: 0

Andrew Howroyd, Mar 01 2024

A front is a k-clique.

			Triangle begins:
  1;
  1,   1;
  1,   1,    1;
  1,   2,    1,    1;
  1,   4,    2,    1,   1;
  1,   9,    6,    2,   1,   1;
  1,  20,   21,    6,   2,   1,  1;
  1,  48,   83,   25,   6,   2,  1, 1;
  1, 115,  356,  126,  25,   6,  2, 1, 1;
  1, 286, 1599,  745, 135,  25,  6, 2, 1, 1;
  1, 719, 7434, 4784, 895, 135, 25, 6, 2, 1, 1;
  ...

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

Columns k=0..2 are A000012, A000081, A058866.

Cf. A370770 (unrooted), A370772, A370773.

A370772 Triangle read by rows: T(n,k) is the number of k-trees with n unlabeled nodes rooted at a hedron.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 3, 1, 1, 0, 1, 6, 3, 1, 1, 0, 1, 16, 10, 3, 1, 1, 0, 1, 37, 39, 10, 3, 1, 1, 0, 1, 96, 164, 48, 10, 3, 1, 1, 0, 1, 239, 746, 253, 48, 10, 3, 1, 1, 0, 1, 622, 3474, 1584, 273, 48, 10, 3, 1, 1, 0, 1, 1607, 16658, 10500, 1913, 273, 48, 10, 3, 1, 1, 0

Offset: 0

Andrew Howroyd, Mar 01 2024

A hedron is a (k+1)-clique.

			Triangle begins:
  0;
  1,   0;
  1,   1,    0;
  1,   1,    1,    0;
  1,   3,    1,    1,   0;
  1,   6,    3,    1,   1,  0;
  1,  16,   10,    3,   1,  1,  0;
  1,  37,   39,   10,   3,  1,  1, 0;
  1,  96,  164,   48,  10,  3,  1, 1, 0;
  1, 239,  746,  253,  48, 10,  3, 1, 1, 0;
  1, 622, 3474, 1584, 273, 48, 10, 3, 1, 1, 0;
  ...

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

Columns k=1..2 are A027852, A063688(n-2).

Cf. A370770 (unrooted), A370771, A370773.

A370773 Triangle read by rows: T(n,k) is the number of k-trees with n unlabeled nodes rooted at a hedron with a designated front.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 5, 2, 1, 0, 1, 12, 7, 2, 1, 0, 1, 30, 26, 7, 2, 1, 0, 1, 74, 110, 30, 7, 2, 1, 0, 1, 188, 481, 159, 30, 7, 2, 1, 0, 1, 478, 2209, 940, 168, 30, 7, 2, 1, 0, 1, 1235, 10379, 6093, 1104, 168, 30, 7, 2, 1, 0, 1, 3214, 49868, 41367, 8428, 1124, 168, 30, 7, 2, 1, 0

Offset: 0

Andrew Howroyd, Mar 01 2024

			Triangle begins:
  0;
  1,    0;
  1,    1,     0;
  1,    2,     1,    0;
  1,    5,     2,    1,    0;
  1,   12,     7,    2,    1,   0;
  1,   30,    26,    7,    2,   1,  0;
  1,   74,   110,   30,    7,   2,  1, 0;
  1,  188,   481,  159,   30,   7,  2, 1, 0;
  1,  478,  2209,  940,  168,  30,  7, 2, 1, 0;
  1, 1235, 10379, 6093, 1104, 168, 30, 7, 2, 1, 0;
  ...

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

Columns k=1 is A000106.

Cf. A370770 (unrooted), A370771, A370772.

A322754 Number of unlabeled 7-trees on n nodes.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 5, 15, 64, 342, 2344, 19137, 181098, 1922215, 22472875, 284556458, 3849828695, 54974808527, 819865209740, 12655913153775, 200748351368185, 3253193955012557, 53619437319817482, 895778170144927928, 15129118461773051724

Offset: 1

N. J. A. Sloane, Dec 26 2018

nonn

A k-tree is recursively defined as follows: K_k is a k-tree and any k-tree on n+1 vertices is obtained by joining a vertex to a k-clique in a k-tree on n vertices.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 328.

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.

Column k=7 of A370770.

Cf. A054581 (unlabeled 2-trees), A078792 (unlabeled 3-trees), A078793 (unlabeled 4-trees), A201702 (unlabeled 5-trees), A202037 (unlabeled 6-trees).

cp's OEIS Frontend

A054581 Number of unlabeled 2-trees with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A078793 Number of unlabeled 4-trees on n vertices.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A135021 Triangle read by rows: T(n,r) = number of maximum r-uniform acyclic hypergraphs of order n and size n-r+1, 1 <= r <= n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A078792 Number of unlabeled 3-trees on n vertices.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A201702 Number of unlabeled 5-trees on n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A202037 Number of unlabeled 6-trees on n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A370771 Triangle read by rows: T(n,k) is the number of k-trees with n unlabeled nodes rooted at a front.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A370772 Triangle read by rows: T(n,k) is the number of k-trees with n unlabeled nodes rooted at a hedron.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A370773 Triangle read by rows: T(n,k) is the number of k-trees with n unlabeled nodes rooted at a hedron with a designated front.

Views

Author

Keywords

Examples