A001858 Number of forests of trees on n labeled nodes.

1, 1, 2, 7, 38, 291, 2932, 36961, 561948, 10026505, 205608536, 4767440679, 123373203208, 3525630110107, 110284283006640, 3748357699560961, 137557910094840848, 5421179050350334929, 228359487335194570528, 10239206473040881277575, 486909744862576654283616

Offset: 0

Author

N. J. A. Sloane and Simon Plouffe

Keywords

• nonn
• easy
• eigen

Comments

The number of integer lattice points in the permutation polytope of {1,2,...,n}. - Max Alekseyev, Jan 26 2010

Equals the number of score sequences for a tournament on n vertices. See Prop. 7 of the article by Bartels et al., or Example 3.1 in the article by Stanley. - David Radcliffe, Aug 02 2022

Number of labeled acyclic graphs on n vertices. The unlabeled version is A005195. The covering case is A105784, connected A000272. - Gus Wiseman, Apr 29 2024

Examples

			From _Gus Wiseman_, Apr 29 2024: (Start)
Edge-sets of the a(4) = 38 forests:
  {}  {12}  {12,13}  {12,13,14}
      {13}  {12,14}  {12,13,24}
      {14}  {12,23}  {12,13,34}
      {23}  {12,24}  {12,14,23}
      {24}  {12,34}  {12,14,34}
      {34}  {13,14}  {12,23,24}
            {13,23}  {12,23,34}
            {13,24}  {12,24,34}
            {13,34}  {13,14,23}
            {14,23}  {13,14,24}
            {14,24}  {13,23,24}
            {14,34}  {13,23,34}
            {23,24}  {13,24,34}
            {23,34}  {14,23,24}
            {24,34}  {14,23,34}
                     {14,24,34}
(End)
		

References

• B. Bollobas, Modern Graph Theory, Springer, 1998, p. 290.
• 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

• Alois P. Heinz, Table of n, a(n) for n = 0..388 (first 101 terms from T. D. Noe)
• J. E. Bartels, J. Mount, and D. J. A. Welsh, The polytope of win vectors. Annals of Combinatorics 1, 1-15 (1997). https://doi.org/10.1007/BF02558460
• David Callan, A Combinatorial Derivation of the Number of Labeled Forests, J. Integer Seqs., Vol. 6, 2003.
• Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.o
• Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.
• Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002 [Local copy, with permission]
• P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 132.
• Samuele Giraudo, Combalgebraic structures on decorated cliques, Formal Power Series and Algebraic Combinatorics, Séminaire Lotharingien de Combinatoire, 78B.15, 2017, p. 7, arXiv:1709.08416 [math.CO], 2017.
• Anton Izosimov, Matrix polynomials, generalized Jacobians, and graphical zonotopes, arXiv:1506.05179 [math.AG], 2015.
• Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Bridging Weighted First Order Model Counting and Graph Polynomials, arXiv:2407.11877 [cs.LO], 2024. See pp. 32-33.
• Arun P. Mani and Rebecca J. Stones, Congruences for weighted number of labeled forests, INTEGERS 16 (2016). #A17.
• J. Pitman, Coalescent Random Forests, J. Combin. Theory, A85 (1999), 165-193.
• J. Riordan, Forests of labeled trees, J. Combin. Theory, 5 (1968), 90-103.
• J. Riordan, Letter to N. J. A. Sloane, Oct 19 1970
• J. Riordan, Letter to N. J. A. Sloane, Nov 10 1975
• John Riordan and N. J. A. Sloane, Correspondence, 1974
• N. J. A. Sloane, Letter to J. Riordan, Nov. 1970
• R. Stanley, Decompositions of rational convex polytopes, Ann. Discrete Math 6.6 (1980): 333-342.
• L. Takacs, On the number of distinct forests, SIAM J. Discrete Math., 3 (1990), 574-581.
• E. M. Wright, A relationship between two sequences, Proc. London Math. Soc. (3) 17 (1967) 296-304.
• Index entries for sequences related to forests

Crossrefs

The connected case is A000272, rooted A000169.

The unlabeled version is A005195, connected A000055.

The covering case is A105784, unlabeled A144958.

Row sums of A138464.

For triangles instead of cycles we have A213434, covering A372168.

For a unique cycle we have A372193, covering A372195.

A002807 counts cycles in a complete graph.

A006125 counts simple graphs, unlabeled A000088.

A006129 counts covering graphs, unlabeled A002494.

Cf. A006572, A006573, A088956.

Cf. A053530, A054548, A137916, A263340, A322661, A367863, A372176.

Programs

Maple

exp(x+x^2+add(n^(n-2)*x^n/n!, n=3..50));
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(
      binomial(n-1, j-1)*j^(j-2)*a(n-j), j=1..n))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Sep 15 2008
# third Maple program:
F:= exp(-LambertW(-x)*(1+LambertW(-x)/2)):
S:= series(F,x,51):
seq(coeff(S,x,j)*j!, j=0..50); # Robert Israel, May 21 2015

Mathematica

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[ Series[Exp[t-t^2/2],{x,0,nn}],x] (* Geoffrey Critzer, Sep 05 2012 *)
nmax = 20; CoefficientList[Series[-LambertW[-x]/(x*E^(LambertW[-x]^2/2)), {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jul 19 2019 *)

PARI

a(n)=if(n<0,0,sum(m=0,n,sum(j=0,m,binomial(m,j)*binomial(n-1,n-m-j)*n^(n-m-j)*(m+j)!/(-2)^j)/m!)) /* Michael Somos, Aug 22 2002 */

Formula

E.g.f.: exp( Sum_{n>=1} n^(n-2)*x^n/n! ). This implies (by a theorem of Wright) that a(n) ~ exp(1/2)*n^(n-2). - N. J. A. Sloane, May 12 2008 [Corrected by Philippe Flajolet, Aug 17 2008]

E.g.f.: exp(T - T^2/2), where T = T(x) = Sum_{n>=1} n^(n-1)*x^n/n! is Euler's tree function (see A000169). - Len Smiley, Dec 12 2001

Shifts 1 place left under the hyperbinomial transform (cf. A088956). - Paul D. Hanna, Nov 03 2003

a(0) = 1, a(n) = Sum_{j=0..n-1} C(n-1,j) (j+1)^(j-1) a(n-1-j) if n>0. - Alois P. Heinz, Sep 15 2008

Extensions

More terms from Michael Somos, Aug 22 2002