cp's OEIS Frontend

A174135 Irregular triangle read by rows: T(n,k), n >= 2, 1 <= k <= n/2, = number of rooted forests with n nodes and k trees, with at least two nodes in each tree.

%I A174135 #28 Dec 26 2023 12:11:17
%S A174135 1,2,4,1,9,2,20,7,1,48,17,2,115,48,7,1,286,124,21,2,719,336,60,7,1,
%T A174135 1842,888,171,21,2,4766,2393,488,65,7,1,12486,6419,1372,187,21,2,
%U A174135 32973,17376,3862,554,65,7,1,87811,47097,10846,1600,193,21,2,235381,128365,30429,4644,574,65,7,1,634847,350837,85365,13362,1685,193,21,2
%N A174135 Irregular triangle read by rows: T(n,k), n >= 2, 1 <= k <= n/2, = number of rooted forests with n nodes and k trees, with at least two nodes in each tree.
%C A174135 In other words, components consisting of just a root node are forbidden. If this condition is removed, we get A033185.
%C A174135 First column is a version of A000081. Row sums give A174145.
%C A174135 Diagonal sums give A181360 (e.g., 9+7+2+1 = 19).
%H A174135 Alois P. Heinz, <a href="/A174135/b174135.txt">Rows n = 2..200, flattened</a>
%F A174135 G.f.: 1/Product((1-x*y^i)^A000081(i), i=2..infinity).
%e A174135 Triangle begins:
%e A174135 1,
%e A174135 2,
%e A174135 4, 1,
%e A174135 9, 2,
%e A174135 20, 7, 1,
%e A174135 48, 17, 2,
%e A174135 115, 48, 7, 1,
%e A174135 286, 124, 21, 2,
%e A174135 719, 336, 60, 7, 1,
%e A174135 1842, 888, 171, 21, 2,
%e A174135 4766, 2393, 488, 65, 7, 1,
%e A174135 12486, 6419, 1372, 187, 21, 2,
%e A174135 32973, 17376, 3862, 554, 65, 7, 1,
%e A174135 87811, 47097, 10846, 1600, 193, 21, 2,
%e A174135 235381, 128365, 30429, 4644, 574, 65, 7, 1,
%e A174135 634847, 350837, 85365, 13362, 1685, 193, 21, 2,
%e A174135 1721159, 962731, 239566, 38459, 4948, 581, 65, 7, 1,
%e A174135 ...
%p A174135 with(numtheory):
%p A174135 t:= proc(n) option remember; local d, j; `if`(n<=1, n,
%p A174135       (add(add(d*t(d), d=divisors(j))*t(n-j), j=1..n-1))/(n-1))
%p A174135     end:
%p A174135 b:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
%p A174135       `if`(p<1 or i<2, 0, add(b(n-i*j, i-1, p-j) *
%p A174135        binomial(t(i)+j-1, j), j=0..min(n/i, p) ))))
%p A174135     end:
%p A174135 T:= (n, k)-> b(n, n, k):
%p A174135 seq(seq(T(n, k), k=1..iquo(n, 2)), n=2..18);  # _Alois P. Heinz_, May 17 2013
%t A174135 t[n_] := t[n] = Module[{d, j}, If[n <= 1, n, Sum[Sum[d*t[d], {d, Divisors[j]}]*t[n-j], {j, 1, n-1}]/(n-1)]]; b[n_, i_, p_] := b[n, i, p] = If[p > n, 0, If[n == 0, 1, If[p < 1 || i < 2, 0, Sum[b[n-i*j, i-1, p-j]* Binomial[t[i]+j-1, j], {j, 0, Min[n/i, p]}]]]]; T[n_, k_] := b[n, n, k]; Table[Table[T[n, k], {k, 1, Quotient[n, 2]}], {n, 2, 18}] // Flatten (* _Jean-François Alcover_, Mar 05 2014, after _Alois P. Heinz_ *)
%Y A174135 Cf. A000081, A033185, A174145, A181360.
%K A174135 nonn,tabf
%O A174135 2,2
%A A174135 _N. J. A. Sloane_, Nov 26 2010