|
%I M1804 N0714 #112 Aug 04 2022 05:01:50
%S 1,1,2,7,38,291,2932,36961,561948,10026505,205608536,4767440679,
%T 123373203208,3525630110107,110284283006640,3748357699560961,
%U 137557910094840848,5421179050350334929,228359487335194570528,10239206473040881277575,486909744862576654283616
%N Number of forests of trees on n labeled nodes.
%C The number of integer lattice points in the permutation polytope of {1,2,...,n}. - _Max Alekseyev_, Jan 26 2010
%C 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
%D B. Bollobas, Modern Graph Theory, Springer, 1998, p. 290.
%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 Alois P. Heinz, <a href="/A001858/b001858.txt">Table of n, a(n) for n = 0..388</a> (first 101 terms from T. D. Noe)
%H J. E. Bartels, J. Mount, and D. J. A. Welsh, <a href="https://johnmount.github.io/mzlabs/JMPubs/The%20Polytope%20of%20Win%20Vectors-Bartels.pdf">The polytope of win vectors</a>. Annals of Combinatorics 1, 1-15 (1997). https://doi.org/10.1007/BF02558460
%H David Callan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Callan/callan10.html">A Combinatorial Derivation of the Number of Labeled Forests</a>, J. Integer Seqs., Vol. 6, 2003.
%H Huantian Cao, <a href="https://web.archive.org/web/20100613201911/http://www.cs.uga.edu/~rwr/STUDENTS/hcao.html">AutoGF: An Automated System to Calculate Coefficients of Generating Functions</a>, thesis, 2002.o
%H Huantian Cao, <a href="http://cobweb.cs.uga.edu/~rwr/STUDENTS/hcao.html">AutoGF: An Automated System to Calculate Coefficients of Generating Functions</a>, thesis, 2002.
%H Huantian Cao, <a href="/A000009/a000009.pdf">AutoGF: An Automated System to Calculate Coefficients of Generating Functions</a>, thesis, 2002 [Local copy, with permission]
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 132.
%H Samuele Giraudo, <a href="https://arxiv.org/abs/1709.08416">Combalgebraic structures on decorated cliques</a>, Formal Power Series and Algebraic Combinatorics, Séminaire Lotharingien de Combinatoire, 78B.15, 2017, p. 7, arXiv:1709.08416 [math.CO], 2017.
%H Anton Izosimov, <a href="http://arxiv.org/abs/1506.05179">Matrix polynomials, generalized Jacobians, and graphical zonotopes</a>, arXiv:1506.05179 [math.AG], 2015.
%H Arun P. Mani and Rebecca J. Stones, <a href="https://www.emis.de/journals/INTEGERS/papers/q17/q17.Abstract.html">Congruences for weighted number of labeled forests</a>, INTEGERS 16 (2016). #A17.
%H J. Pitman, <a href="https://doi.org/10.1006/jcta.1998.2919">Coalescent Random Forests</a>, J. Combin. Theory, A85 (1999), 165-193.
%H J. Riordan, <a href="http://dx.doi.org/10.1016/S0021-9800(68)80033-X">Forests of labeled trees</a>, J. Combin. Theory, 5 (1968), 90-103.
%H J. Riordan, <a href="/A001861/a001861.pdf">Letter to N. J. A. Sloane, Oct 19 1970</a>
%H J. Riordan, <a href="/A000262/a000262_1.pdf">Letter to N. J. A. Sloane, Nov 10 1975</a>
%H John Riordan and N. J. A. Sloane, <a href="/A003471/a003471_1.pdf">Correspondence, 1974</a>
%H N. J. A. Sloane, <a href="/A001514/a001514.pdf">Letter to J. Riordan, Nov. 1970</a>
%H R. Stanley, <a href="https://math.mit.edu/~rstan/pubs/pubfiles/40.pdf">Decompositions of rational convex polytopes</a>, Ann. Discrete Math 6.6 (1980): 333-342.
%H L. Takacs, <a href="http://dx.doi.org/10.1137/0403050">On the number of distinct forests</a>, SIAM J. Discrete Math., 3 (1990), 574-581.
%H E. M. Wright, <a href="http://plms.oxfordjournals.org/content/s3-17/2/296.extract">A relationship between two sequences</a>, Proc. London Math. Soc. (3) 17 (1967) 296-304.
%H <a href="/index/Fo#forests">Index entries for sequences related to forests</a>
%F 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]
%F 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
%F Shifts 1 place left under the hyperbinomial transform (cf. A088956). - _Paul D. Hanna_, Nov 03 2003
%F 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
%p exp(x+x^2+add(n^(n-2)*x^n/n!, n=3..50));
%p # second Maple program:
%p a:= proc(n) option remember; `if`(n=0, 1, add(
%p binomial(n-1, j-1)*j^(j-2)*a(n-j), j=1..n))
%p end:
%p seq(a(n), n=0..20); # _Alois P. Heinz_, Sep 15 2008
%p # third Maple program:
%p F:= exp(-LambertW(-x)*(1+LambertW(-x)/2)):
%p S:= series(F,x,51):
%p seq(coeff(S,x,j)*j!, j=0..50); # _Robert Israel_, May 21 2015
%t 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 *)
%t nmax = 20; CoefficientList[Series[-LambertW[-x]/(x*E^(LambertW[-x]^2/2)), {x, 0, nmax}], x] * Range[0, nmax]! (* _Vaclav Kotesovec_, Jul 19 2019 *)
%o (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 */
%Y Cf. A088956. Row sums of A138464. Cf. also A006572, A006573.
%K nonn,easy,eigen
%O 0,3
%A _N. J. A. Sloane_ and _Simon Plouffe_
%E More terms from _Michael Somos_, Aug 22 2002
|
