A181360 Number of forests of rooted trees containing n nodes not counting the root nodes.

1, 1, 3, 7, 19, 47, 127, 330, 889, 2378, 6450, 17510, 47907, 131388, 362081, 1000665, 2774857, 7714695, 21505455, 60084062, 168234804, 471977022, 1326558625, 3734804268, 10531738149, 29742332548, 84111212892, 238176473946, 675269414372, 1916715819186

Offset: 0

Author

Peter A. Lawrence, Oct 15 2010

Keywords

• nonn

Comments

Every tree in the forest must have at least 2 nodes, i.e. at least one more node besides the root. - N. J. A. Sloane, Nov 26 2010

First, T(n), the number of rooted trees with n+1 nodes A000081(n+1) can be computed using partitions of n as follows: let n = (q1*1 + q2*2 + q3*3 + ... + qn*n) be a nonnegative integer partition of n (the "q"s are the multiplicities of the part sizes), and define a^b to be (a+b-1)! / (a-1)! / b! (the number of ways to color b identical items with a colors), then compute the sum of T(0)^q1 * T(1)^q2 * ... * T(n-1)^qn over all such partitions of n.

Then F(n), the number of forests of rooted trees containing N nodes not counting the roots, can be similarly computed as the sum of T(1)^q1 * T(2)^q2 * ... * T(n)^qn over all such partitions of n.

These are the diagonal sums of the triangle in A174135. - N. J. A. Sloane, Nov 26 2010.

Examples

			Trees for example (leaving out the "^0" factors for clarity):
T(0) = 1, T(1) = 1
T(2) = T(1)^1 + T(0)^2 = 2,
T(3) = T(2)^1 + T(1)^1*T(0)^1 + T(0)^3 = 4,
T(4) = T(3)^1 + T(2)^1*T(0)^1 + T(1)^2 + T(1)^1*T(0)^2 +T(0)^4 = 9,
T(5) = T(4)^1 + T(3)^1*T(0)^1 + T(2)^1*T(1)^1 + T(2)^1*T(0)^2 + T(1)^2*T(0)^1 + T(1)^1*T(0)^3 + T(0)^5 = 20.
Forests for example (leaving out the "^0" factors for clarity):
F(2) = T(2)^1 + T(1)^2 = 3,
F(3) = T(3)^1 + T(2)^1*T(1)^1 + T(1)^3 = 7,
F(4) = T(4)^1 + T(3)^1*T(1)^1 + T(2)^2 + T(2)*T(1)^2 + T(1)^4 = 19,
F(5) = T(5)^1 + T(4)^1*T(1)^1 + T(3)^1*T(2)^1 + T(3)^1*T(1)^2 + T(2)^2*T(1)^1 + T(2)^1*T(1)^3 + T(1)^5 = 47.
{Examples of this a^b definition:
2^1 = 2, 2^2 = 3, 2^3 = 4, 2^4 = 5,
3^1 = 3, 3^2 = 6, 3^3 = 10, 3^4 = 15, (triangular numbers)
4^1 = 4, 4^2 = 10, 4^3 = 20, 4^4 = 35, (tetrahedral numbers)
equivalently a^b = (b == 0 ? 1 : (a == 1 || b == 1 ? a : (a * (a+1)^(b-1) / b))) }
		

Links

• N. J. A. Sloane and Alois P. Heinz, Table of n, a(n) for n = 0..2133
• A. Mansuy, Preordered forests, packed words and contraction algebras, J. Algebra 411 (2014) 259-311, section 4.1
• R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016.

Crossrefs

Cf. A000081 (rooted trees).

Cf. A093637 (products of partition numbers).

Cf. A174135, A033185.

Programs

Maple

(From N. J. A. Sloane, Nov 26 2010) First read 110 terms of A000081 into array b1
M:=100;
t1:=1/mul((1-x*y^i)^b1[i+1],i=2..M):
t2:=series(t1,y,M):
t3:=series(t2,x,M):
a:=(n,k)->coeff(coeff(t3,x,k),y,n);
g:=n->add(a(n-1+i,i),i=1..n-1);
[seq(g(n),n=1..48)];
# second Maple program:
g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(T(i-1)+j-1, j) *g(n-i*j, i-1), j=0..n/i)))
    end:
T:= n-> g(n, n):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(T(i)+j-1, j) *b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> b(n, n):
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 20 2012
# third Maple program:
g:= proc(n) option remember; `if`(n<=1, n, (add(add(d*
      g(d), d=numtheory[divisors](j))*g(n-j), j=1..n-1))/(n-1))
    end:
a:= proc(n) option remember; `if`(n=0, 1, add(add(d*
      g(d+1), d=numtheory[divisors](j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Sep 19 2017

Mathematica

g[n_, i_] := g[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[T[i-1]+j-1, j]*g[n-i*j, i-1], {j, 0, n/i}]]]; T[n_] := g[n, n]; b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[T[i]+j-1, j]*b[n-i*j, i-1], {j, 0, n/i}]]]; a[n_] := b[n, n] // FullSimplify; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Mar 30 2015, after Alois P. Heinz *)

Formula

a(n) ~ c * d^n / n^(3/2), where d = 2.955765285651994974714817524... is the Otter's rooted tree constant (see A051491), and c = 10.088029891871277227771831767... . - Vaclav Kotesovec, May 09 2014

a(n) = A033185(2n, n). - Alois P. Heinz, Feb 15 2016

a(n) = A033185(2n+k, n+k) for all n, k >= 0. - Michael Somos, Aug 20 2018

Extensions

a(0)=1 prepended by Alois P. Heinz, Sep 19 2017