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

Author

Vladeta Jovovic, Apr 11 2000

Keywords

• nonn
• nice

Comments

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.

Examples

			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.
		

References

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

Links

• 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

Crossrefs

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

Extensions

Additional comments from Gordon F. Royle, Dec 02 2002

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