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

%I M1773 N0702 #38 May 19 2024 14:02:59

%S 1,1,2,7,26,111,562,3151,19252,128449,925226,7125009,58399156,

%T 507222535,4647051970,44747776651,451520086208,4761032807937,

%U 52332895618066,598351410294193,7102331902602676,87365859333294151,1111941946738682522,14621347433458883187

%N Number of forests of least height with n nodes.

%C From _Gus Wiseman_, Feb 14 2024: (Start)

%C 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):

%C {} {1} {12} {1-23}

%C {1-2} {2-13}

%C {3-12}

%C {12-13}

%C {12-23}

%C {13-23}

%C {1-2-3}

%C (End)

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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A001862/b001862.txt">Table of n, a(n) for n = 0..100</a>

%H John Riordan, <a href="https://doi.org/10.1016/S0021-9800(68)80033-X">Forests of labeled trees</a>, J. Combin. Theory, 5 (1968), 90-103.

%H John Riordan, <a href="/A001861/a001861.pdf">Letter to N. J. A. Sloane, Oct. 1970</a>

%H John Riordan and N. J. A. Sloane, <a href="/A003471/a003471_1.pdf">Correspondence, 1974</a>

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

%F Binomial transform of A053530. - _Gus Wiseman_, Feb 14 2024

%t Range[0, 20]! CoefficientList[Series[Exp[x Exp[x] - x^2/2], {x, 0, 20}], x] (* _Geoffrey Critzer_, Mar 13 2011 *)

%t fasmin[y_]:=Complement[y,Union@@Table[Union[s,#]& /@ Rest[Subsets[Complement[Union@@y,s]]],{s,y}]];

%t Table[Length@fasmin[Select[Subsets[Subsets[Range[n],{1,2}]], Union@@#==Range[n]&]],{n,0,4}] (* _Gus Wiseman_, Feb 14 2024 *)

%Y The connected case is A000272.

%Y Without loops we have A053530, minimal case of A369191.

%Y This is the minimal case of A322661.

%Y A000666 counts unlabeled loop-graphs, covering A322700.

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

%Y A006129 counts covering graphs, unlabeled A002494.

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

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

%K nonn

%O 0,3

%A _N. J. A. Sloane_

%E Formula and more terms from _Vladeta Jovovic_, Mar 27 2001