cp's OEIS Frontend

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

%I A336087 #14 Sep 02 2020 10:39:49
%S A336087 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 A336087 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 A336087 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 A336087 Triangle read by rows: T(n, k) is the number of forests with n (unlabeled) nodes and k planted trees.
%C A336087 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 A336087 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 A336087 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A336087 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 A336087 If k > floor(n/2), T(n,k) = 0; otherwise T(n,k) = A033185(n-k, k).
%e A336087                            Triangle T(n,k)
%e A336087 n\k     1      2     3    4   5  6  7  8 9 10 11 12 13 14 15
%e A336087 1       0;
%e A336087 2       1,     0;
%e A336087 3       1,     0,    0;
%e A336087 4       2,     1,    0,   0;
%e A336087 5       4,     1,    0,   0,  0;
%e A336087 6       9,     3,    1,   0,  0, 0;
%e A336087 7      20,     6,    1,   0,  0, 0, 0;
%e A336087 8      48,    16,    3,   1,  0, 0, 0, 0;
%e A336087 9     115,    37,    7,   1,  0, 0, 0, 0, 0;
%e A336087 10    286,    96,   18,   3,  1, 0, 0, 0, 0, 0;
%e A336087 11    719,   239,   44,   7,  1, 0, 0, 0, 0, 0, 0;
%e A336087 12   1842,   622,  117,  19,  3, 1, 0, 0, 0, 0, 0, 0;
%e A336087 13   4766,  1607,  299,  46,  7, 1, 0, 0, 0, 0, 0, 0, 0;
%e A336087 14  12486,  4235,  793, 124, 19, 3, 1, 0, 0, 0, 0, 0, 0, 0;
%e A336087 15  32973, 11185, 2095, 320, 47, 7, 1, 0, 0, 0, 0, 0, 0, 0, 0;
%e A336087                            ...
%e A336087 n\k     1      2     3    4   5  6  7  8  9 10 11 12 13 14 15
%e A336087 A005199(6) = Sum_{k=1..6}( k * T(6,k) ) = 1*9 + 2*3 +3*1 = 18.
%o A336087 (PARI) g(m) = {my(f); if(m==0, return(1)); f = vector(m+1); f[1]=1;
%o A336087 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 A336087 global(max_n = 130); A000081 = vector(max_n, n, g(n-1));
%o A336087 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 A336087 s += prod(k=1, #D, binomial( A000081[D[k]-1] + c[k] - 1, c[k])),[2,n],[t,t]); s};
%Y A336087 Cf. A000081, A005199, A005198 (row sums), A033185.
%K A336087 nonn,tabl
%O A336087 1,7
%A A336087 _Washington Bomfim_, Jul 08 2020