A001862 Number of forests of least height with n nodes.

1, 1, 2, 7, 26, 111, 562, 3151, 19252, 128449, 925226, 7125009, 58399156, 507222535, 4647051970, 44747776651, 451520086208, 4761032807937, 52332895618066, 598351410294193, 7102331902602676, 87365859333294151, 1111941946738682522, 14621347433458883187

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

From Gus Wiseman, Feb 14 2024: (Start)

Also the number of minimal loop-graphs covering n vertices. This is the minimal case of A322661. For example, the a(0) = 1 through a(3) = 7 loop-graphs are (loops represented as singletons):

{} {1} {12} {1-23}

{1-2} {2-13}

{3-12}

{12-13}

{12-23}

{13-23}

{1-2-3}

(End)

References

• I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983. See (3.3.7): number of ways to cover the complete graph K_n with star graphs.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n = 0..100
• John Riordan, Forests of labeled trees, J. Combin. Theory, 5 (1968), 90-103.
• John Riordan, Letter to N. J. A. Sloane, Oct. 1970
• John Riordan and N. J. A. Sloane, Correspondence, 1974

Crossrefs

The connected case is A000272.

Without loops we have A053530, minimal case of A369191.

This is the minimal case of A322661.

A000666 counts unlabeled loop-graphs, covering A322700.

A006125 counts simple graphs; also loop-graphs if shifted left.

A006129 counts covering graphs, unlabeled A002494.

A054548 counts graphs covering n vertices with k edges, with loops A369199.

Cf. A000085, A000169, A003465, A062740, A066383, A133686, A368597.

Programs

Mathematica

Range[0, 20]! CoefficientList[Series[Exp[x Exp[x] - x^2/2], {x, 0, 20}], x] (* Geoffrey Critzer, Mar 13 2011 *)
fasmin[y_]:=Complement[y,Union@@Table[Union[s,#]& /@ Rest[Subsets[Complement[Union@@y,s]]],{s,y}]];
Table[Length@fasmin[Select[Subsets[Subsets[Range[n],{1,2}]], Union@@#==Range[n]&]],{n,0,4}] (* Gus Wiseman, Feb 14 2024 *)

Formula

E.g.f.: exp(x*(exp(x)-x/2)).

Binomial transform of A053530. - Gus Wiseman, Feb 14 2024

Extensions

Formula and more terms from Vladeta Jovovic, Mar 27 2001