A105784 Number of different forests of unrooted trees, without isolated vertices, on n labeled nodes.

0, 1, 3, 19, 155, 1641, 21427, 334377, 6085683, 126745435, 2975448641, 77779634571, 2241339267037, 70604384569005, 2414086713172695, 89049201691604881, 3525160713653081279, 149075374211881719939, 6707440248292609651513, 319946143503599791200675

Offset

1,3

Links

Alois P. Heinz, Table of n, a(n) for n = 1..150

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-2)Ki) and D = Product_{i=1..n}(Ki!(i!)^Ki).

Inverse binomial transform of A001858. E.g.f.: exp(-x-LambertW(-x) -LambertW(-x)^2/2). - Vladeta Jovovic, Apr 22 2005

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

Example

a(4) = 19 because there are 19 different such forests on 4 labeled nodes: 4^2 are trees, 3 have two trees and none can have more than two trees.

Maple

b:= n-> add(add(binomial(m, j) *binomial(n-1, n-m-j)
        *n^(n-m-j) *(m+j)!/ (-2)^j, j=0..m)/m!, m=0..n):
a:= n-> add(b(k) *(-1)^(n-k) *binomial(n, k), k=0..n):
seq(a(n), n=1..17);  # Alois P. Heinz, Sep 10 2008

Mathematica

Unprotect[Power]; 0^0 = 1; b[n_] := Sum[Sum[Binomial[m, j]*Binomial[n-1, n -m-j]*n^(n-m-j)*(m+j)!/(-2)^j, {j, 0, m}]/m!, {m, 0, n}]; a[n_] := Sum[ b[k]*(-1)^(n-k)*Binomial[n, k], {k, 0, n}]; Table[a[n], {n, 1, 17}] (* Jean-François Alcover, Jan 08 2016, after Alois P. Heinz *)

Crossrefs

Cf. A033185, A105599.

Sequence in context: A323668 A235134 A235322 * A077046 A232607 A307697

Adjacent sequences: A105781 A105782 A105783 * A105785 A105786 A105787

Keyword

nonn

Author

Washington Bomfim, Apr 21 2005

Status

approved