A336087 Triangle read by rows: T(n, k) is the number of forests with n (unlabeled) nodes and k planted trees.

0, 1, 0, 1, 0, 0, 2, 1, 0, 0, 4, 1, 0, 0, 0, 9, 3, 1, 0, 0, 0, 20, 6, 1, 0, 0, 0, 0, 48, 16, 3, 1, 0, 0, 0, 0, 115, 37, 7, 1, 0, 0, 0, 0, 0, 286, 96, 18, 3, 1, 0, 0, 0, 0, 0, 719, 239, 44, 7, 1, 0, 0, 0, 0, 0, 0, 1842, 622, 117, 19, 3, 1, 0, 0, 0, 0, 0, 0, 4766, 1607, 299, 46, 7, 1, 0, 0, 0, 0, 0, 0, 0, 12486, 4235, 793, 124

Offset: 1

Author

Washington Bomfim, Jul 08 2020

Keywords

• nonn
• tabl

Comments

The number of planted trees with n+1 nodes is equal to the number of rooted trees with n nodes. [See Palmer-Schwenk link, pp. 115].

Examples

			                           Triangle T(n,k)
n\k     1      2     3    4   5  6  7  8 9 10 11 12 13 14 15
1       0;
2       1,     0;
3       1,     0,    0;
4       2,     1,    0,   0;
5       4,     1,    0,   0,  0;
6       9,     3,    1,   0,  0, 0;
7      20,     6,    1,   0,  0, 0, 0;
8      48,    16,    3,   1,  0, 0, 0, 0;
9     115,    37,    7,   1,  0, 0, 0, 0, 0;
10    286,    96,   18,   3,  1, 0, 0, 0, 0, 0;
11    719,   239,   44,   7,  1, 0, 0, 0, 0, 0, 0;
12   1842,   622,  117,  19,  3, 1, 0, 0, 0, 0, 0, 0;
13   4766,  1607,  299,  46,  7, 1, 0, 0, 0, 0, 0, 0, 0;
14  12486,  4235,  793, 124, 19, 3, 1, 0, 0, 0, 0, 0, 0, 0;
15  32973, 11185, 2095, 320, 47, 7, 1, 0, 0, 0, 0, 0, 0, 0, 0;
                           ...
n\k     1      2     3    4   5  6  7  8  9 10 11 12 13 14 15
A005199(6) = Sum_{k=1..6}( k * T(6,k) ) = 1*9 + 2*3 +3*1 = 18.
		

Links

• E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121.
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A000081, A005199, A005198 (row sums), A033185.

Programs

PARI

g(m) = {my(f); if(m==0, return(1)); f = vector(m+1); f[1]=1;
for(j=1, m, f[j+1]=1/j * sum(k=1, j, sumdiv(k,d, d * f[d]) * f[j-k+1])); f[m+1] };
global(max_n = 130); A000081 = vector(max_n, n, g(n-1));
F(n,t)={my(s=0, D, c, P_1); if(n==1,return(0)); forpart(P_1 = n, D = Set(P_1); c = vector(#D); for(k=1, #D, c[k] = #select(x->x == D[k], Vec(P_1)));
s += prod(k=1, #D, binomial( A000081[D[k]-1] + c[k] - 1, c[k])),[2,n],[t,t]); s};

Formula

T(1,1) = 0, if n >= 2 T(n,k) = Sum_{P_1(n,k)}( Product_{j=2..n} binomial(A000081(j-1) + c_j - 1, c_j) ), where P_1(n, k) is the set of the partitions of n with k parts greater than one: 2*c_2 + ... + n*c_n = n; c_2, ..., c_n >= 0.

If k > floor(n/2), T(n,k) = 0; otherwise T(n,k) = A033185(n-k, k).