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

%I #14 Sep 02 2020 10:39:49

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

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

%U 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

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

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

%H E. M. Palmer and A. J. Schwenk, <a href="https://doi.org/10.1016/0095-8956(79)90073-X">On the number of trees in a random forest</a>, J. Combin. Theory, B 27 (1979), 109-121.

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%F 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.

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

%e Triangle T(n,k)

%e n\k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

%e 1 0;

%e 2 1, 0;

%e 3 1, 0, 0;

%e 4 2, 1, 0, 0;

%e 5 4, 1, 0, 0, 0;

%e 6 9, 3, 1, 0, 0, 0;

%e 7 20, 6, 1, 0, 0, 0, 0;

%e 8 48, 16, 3, 1, 0, 0, 0, 0;

%e 9 115, 37, 7, 1, 0, 0, 0, 0, 0;

%e 10 286, 96, 18, 3, 1, 0, 0, 0, 0, 0;

%e 11 719, 239, 44, 7, 1, 0, 0, 0, 0, 0, 0;

%e 12 1842, 622, 117, 19, 3, 1, 0, 0, 0, 0, 0, 0;

%e 13 4766, 1607, 299, 46, 7, 1, 0, 0, 0, 0, 0, 0, 0;

%e 14 12486, 4235, 793, 124, 19, 3, 1, 0, 0, 0, 0, 0, 0, 0;

%e 15 32973, 11185, 2095, 320, 47, 7, 1, 0, 0, 0, 0, 0, 0, 0, 0;

%e ...

%e n\k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

%e A005199(6) = Sum_{k=1..6}( k * T(6,k) ) = 1*9 + 2*3 +3*1 = 18.

%o (PARI) g(m) = {my(f); if(m==0, return(1)); f = vector(m+1); f[1]=1;

%o 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] };

%o global(max_n = 130); A000081 = vector(max_n, n, g(n-1));

%o 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)));

%o s += prod(k=1, #D, binomial( A000081[D[k]-1] + c[k] - 1, c[k])),[2,n],[t,t]); s};

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

%K nonn,tabl

%O 1,7

%A _Washington Bomfim_, Jul 08 2020