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

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001858 Number of forests of trees on n labeled nodes.
(Formerly M1804 N0714)
21
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.

J. Riordan, Forests of labeled trees, J. Combin. Theory, 5 (1968), 90-103.

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

L. Takacs, On the number of distinct forests, SIAM J. Discrete Math., 3 (1990), 574-581.

Wright, E. M., A relationship between two sequences, Proc. London Math. Soc. (3) 17 (1967) 296-304.

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.

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>1. - 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

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

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

PARI code and 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 April 16 10:28 EDT 2014. Contains 240577 sequences.