|
%I #34 Nov 13 2020 06:26:02
%S 1,0,2,9,76,805,10626,167839,3091768,65127465,1544951350,40770052411,
%T 1184951084340,37616775522781,1295202587597842,48080003446006575,
%U 1914305438178286576,81379323738092982097,3679128029385789284718,176267238847686913800547
%N Number of different forests of rooted trees, without isolated vertices, on n labeled nodes.
%H Alois P. Heinz, <a href="/A105785/b105785.txt">Table of n, a(n) for n = 0..387</a>
%H A. Mansuy, <a href="https://doi.org/10.1016/j.jalgebra.2014.04.017">Preordered forests, packed words and contraction algebras</a>, J. Alg. 411 (2014) 259 Section 4.4.
%F a(n) = sum N/D over all the partitions of n: 1K1 + 2K2 + ... + nKn, with smallest part greater than 1, where N = n!*Product_{i=1..n} i^((i-1)Ki) and D = Product_{i=1..n} (Ki!(i!)^Ki).
%F E.g.f.: -exp(-x)*LambertW(-x)/x. a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*(k+1)^(k-1). - _Vladeta Jovovic_, Apr 22 2005
%F a(0) = 1, a(n) = Sum_{j=1..n-1} binomial(n-1,j) (j+1)^j a(n-1-j) if n>0. - _Alois P. Heinz_, Sep 15 2008
%F a(n) ~ exp(-exp(-1)+1) * n^(n-1). - _Vaclav Kotesovec_, Aug 16 2013
%e a(5) = 805 because there are 625 such trees and 5 vertices can be partitioned in two trees only in one way: 3 go to one tree and 2 go to the other. It's impossible to split 5 vertices in 3 or more trees without giving only one vertex to a tree. Each one of the 3^2 distinct trees on 3 vertices can be labeled in binomial(5,3) ways and to each one of the 9*binomial(5,3) = 90 possibilities there are 2 different trees of order 2, so we get 180 forests of two trees.
%p a:= proc(n) option remember; if n=0 then 1 else add(binomial(n-1, j) *(j+1)^j *a(n-1-j), j=1..n-1) fi end: seq(a(n), n=0..25); # _Alois P. Heinz_, Sep 15 2008
%t nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Drop[Range[0,nn]!CoefficientList[ Series[Exp[t-x] ,{x,0,nn}],x],1] (* _Geoffrey Critzer_, Nov 10 2012 *)
%Y Cf. A033185, A105599.
%Y Row sums of A105819.
%K nonn
%O 0,3
%A _Washington Bomfim_, Apr 21 2005
%E More terms from _Alois P. Heinz_, Sep 15 2008
%E a(0)=1 prepended by _Alois P. Heinz_, Aug 13 2017
|
