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,7

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

Links

Table of n, a(n) for n=1..95.

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

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

Example

                           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.

Prog

(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};

Crossrefs

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

Sequence in context: A345698 A369195 A065719 * A204387 A110509 A113953

Adjacent sequences: A336084 A336085 A336086 * A336088 A336089 A336090

Keyword

nonn,tabl

Author

Washington Bomfim, Jul 08 2020

Status

approved