A001862 Number of forests of least height with n nodes. (Formerly M1773 N0702)

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,3

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

Formula

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

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

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

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.

Sequence in context: A150586 A196709 A150587 * A150588 A150589 A007168

Adjacent sequences: A001859 A001860 A001861 * A001863 A001864 A001865

Keyword

nonn

Author

N. J. A. Sloane

Extensions

Formula and more terms from Vladeta Jovovic, Mar 27 2001

Status

approved