A054581 - OEIS

%I #68 Mar 02 2024 11:59:54

%S 0,1,1,1,2,5,12,39,136,529,2171,9368,41534,188942,874906,4115060,

%T 19602156,94419351,459183768,2252217207,11130545494,55382155396,

%U 277255622646,1395731021610,7061871805974,35896206800034,183241761631584

%N Number of unlabeled 2-trees with n nodes.

%C 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.

%C A036361 gives the labeled version of this sequence, which has an easy formula analogous to Cayley's formula for the number of trees.

%C Also, number of unlabeled 3-gonal 2-trees with n 3-gons.

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 327-328.

%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 76, t(x), (3.5.19).

%H Allan Bickle, <a href="https://doi.org/10.20429/tag.2024.000105">A Survey of Maximal k-degenerate Graphs and k-Trees</a>, Theory and Applications of Graphs 0 1 (2024) Article 5.

%H T. Fowler, I. Gessel, G. Labelle, and P. Leroux, <a href="https://doi.org/10.1006/aama.2001.0771">The specification of 2-trees</a>, Adv. Appl. Math. 28 (2) (2002) 145-168, Table 1.

%H Nick Early, Anaëlle Pfister, and Bernd Sturmfels, <a href="https://arxiv.org/abs/2402.03065">Minimal Kinematics on M_{0,n}</a>, arXiv:2402.03065 [math.AG], 2024.

%H Andrew Gainer-Dewar, <a href="https://doi.org/10.37236/2615">Gamma-Species and the Enumeration of k-Trees</a>, Electronic Journal of Combinatorics, Volume 19 (2012), #P45. - From _N. J. A. Sloane_, Dec 15 2012

%H Gilbert Labelle, Cédric Lamathe, and Pierre Leroux, <a href="https://arxiv.org/abs/math/0312424">Labeled and unlabeled enumeration of k-gonal 2-trees</a>, arXiv:math/0312424 [math.CO], 2003.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/k-Tree.html">k-Tree</a>.

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%e a(1)=0 because K_1 is not a 2-tree;

%e a(2)=a(3)=1 because K_2 and K_3 are the only 2-trees on those sizes.

%e 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.

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

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

%K nonn,nice

%O 1,5

%A _Vladeta Jovovic_, Apr 11 2000

%E Additional comments from _Gordon F. Royle_, Dec 02 2002

%E Missing initial term 0 inserted by _Brendan McKay_, Aug 07 2023