A174135 -id:A174135 - cp's OEIS frontend

A174145 Number of rooted forests with n nodes in which each component contains at least two nodes.

1, 0, 1, 2, 5, 11, 28, 67, 171, 433, 1123, 2924, 7720, 20487, 54838, 147570, 399466, 1086312, 2967517, 8137552, 22395604, 61833349, 171227674, 475442129, 1323449661, 3692461865, 10324097819, 28923331940, 81179488039, 228240293289, 642744665401, 1812762839702

Offset: 0

N. J. A. Sloane, Nov 26 2010

nonn

Row sums of A174135.

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

Cf. A000081, A051491, A187770, A255170.

with(numtheory):
t:= proc(n) option remember; local d, j; `if`(n<=1, n,
      (add(add(d*t(d), d=divisors(j))*t(n-j), j=1..n-1))/(n-1))
    end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<2, 0,
      add(b(n-i*j, i-1)*binomial(t(i)+j-1, j), j=0..n/i)))
    end:
a:= n-> b(n, n):
seq(a(n), n=0..32);  # Alois P. Heinz, May 17 2013

t[n_] := t[n] = If[n <= 1, n, Sum[Sum[d*t[d], {d, Divisors[j]}]*t[n-j], {j, 1, n-1}]/(n-1)]; b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<2, 0, Sum[b[n-i*j, i-1]*Binomial[t[i]+j-1, j], {j, 0, n/i}]]]; a[n_] := b[n, n]; Table[a[n] // FullSimplify, {n, 0, 32}] (* Jean-François Alcover, Mar 19 2014, after Alois P. Heinz *)
t[1] = 1; t[n_] := t[n] = Sum[k t[k] t[n - k m]/(n-1), {k, n-1}, {m, (n-1)/k}]; a[n_] := t[n+1] - t[n]; Table[a[n], {n, 0, 32}] (* Vladimir Reshetnikov, Aug 12 2016 *)

a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = 0.8603881121111431... . - Vaclav Kotesovec, Sep 10 2014
In the asymptotics above the constant c = A187770 * (A051491 - 1). - Vladimir Reshetnikov, Aug 12 2016
a(n) = A000081(n+1) - A000081(n). - Vladimir Reshetnikov, Nov 06 2015

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

Original entry on oeis.org

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

Peter A. Lawrence, Oct 15 2010

nonn

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.

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

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.

Cf. A000081 (rooted trees).
Cf. A093637 (products of partition numbers).
Cf. A174135, A033185.

(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

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

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

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

cp's OEIS Frontend

A174145 Number of rooted forests with n nodes in which each component contains at least two nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula