login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001858 Number of forests of trees on n labeled nodes.
(Formerly M1804 N0714)
22
1, 1, 2, 7, 38, 291, 2932, 36961, 561948, 10026505, 205608536, 4767440679, 123373203208, 3525630110107, 110284283006640, 3748357699560961, 137557910094840848, 5421179050350334929, 228359487335194570528, 10239206473040881277575, 486909744862576654283616 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

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

T. D. Noe, Table of n, a(n) for n=0..100

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.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 132

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.

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.

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 (smiley(AT)math.uaa.alaska.edu), 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

MAPLE

exp(x+x^2+add(n^(n-2)*x^n/n!, n=3..50));

a:= proc(n) option remember; if n=0 then 1 else add(binomial(n-1, j) *(j+1)^(j-1) *a(n-1-j), j=0..n-1) fi end: seq(a(n), n=0..20); # Alois P. Heinz, Sep 15 2008

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

PROG

(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 */

CROSSREFS

Cf. A088956. Row sums of A138464. Cf. also A006572, A006573.

Sequence in context: A145159 A084552 A094664 * A233335 A000366 A106211

Adjacent sequences:  A001855 A001856 A001857 * A001859 A001860 A001861

KEYWORD

nonn,easy,eigen

AUTHOR

N. J. A. Sloane and Simon Plouffe

EXTENSIONS

More terms from Michael Somos, Aug 22 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified July 8 02:27 EDT 2015. Contains 259370 sequences.