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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A105785 Number of different forests of rooted trees, without isolated vertices, on n labeled nodes. 3
1, 0, 2, 9, 76, 805, 10626, 167839, 3091768, 65127465, 1544951350, 40770052411, 1184951084340, 37616775522781, 1295202587597842, 48080003446006575, 1914305438178286576, 81379323738092982097, 3679128029385789284718, 176267238847686913800547 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..387

FORMULA

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

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

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

a(n) ~ exp(-exp(-1)+1) * n^(n-1). - Vaclav Kotesovec, Aug 16 2013

EXAMPLE

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.

MAPLE

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

MATHEMATICA

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

CROSSREFS

Cf. A033185, A105599.

Row sums of A105819.

Sequence in context: A080638 A232471 A277181 * A245406 A276742 A123680

Adjacent sequences:  A105782 A105783 A105784 * A105786 A105787 A105788

KEYWORD

nonn

AUTHOR

Washington Bomfim, Apr 21 2005

EXTENSIONS

More terms from Alois P. Heinz, Sep 15 2008

a(0)=1 prepended by Alois P. Heinz, Aug 13 2017

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 22 16:41 EDT 2019. Contains 327311 sequences. (Running on oeis4.)