cp's OEIS Frontend

A229223 Number G(n,k) of set partitions of {1,...,n} into sets of size at most k; triangle G(n,k), n>=0, 0<=k<=n, read by rows.

%I A229223 #50 May 21 2021 16:30:49
%S A229223 1,0,1,0,1,2,0,1,4,5,0,1,10,14,15,0,1,26,46,51,52,0,1,76,166,196,202,
%T A229223 203,0,1,232,652,827,869,876,877,0,1,764,2780,3795,4075,4131,4139,
%U A229223 4140,0,1,2620,12644,18755,20645,21065,21137,21146,21147
%N A229223 Number G(n,k) of set partitions of {1,...,n} into sets of size at most k; triangle G(n,k), n>=0, 0<=k<=n, read by rows.
%C A229223 _John Riordan_ calls these Allied Bell Numbers. - _N. J. A. Sloane_, Jan 10 2018
%C A229223 G(n,k) is defined for n,k >= 0.  The triangle contains only the terms with k<=n. G(n,k) = G(n,n) = A000110(n) for k>n.
%C A229223 G(n,k) - G(n,k-1) = A080510(n,k).
%C A229223 A column G(n>=0,k) can be generated by a linear recurrence with polynomial coefficients, where the initial terms correspond with A000110, and the coefficients contain constant factors derived from A008279 (cf. recg(k) in the fourth Maple program below). - _Georg Fischer_, May 19 2021
%H A229223 Alois P. Heinz, <a href="/A229223/b229223.txt">Rows n = 0..140, flattened</a>
%H A229223 J. Riordan, <a href="/A229223/a229223.pdf">Letter, 11/23/1970</a>
%F A229223 G(0,k) = 1, G(n,k) = 0 for n>0 and k<1, otherwise G(n,k) = Sum_{j=0..floor(n/k)} G(n-k*j,k-1) * n!/(k!^j*(n-k*j)!*j!).
%F A229223 G(n,k) = G(n-1,k) +(n-1)/1 *(G(n-2,k) +(n-2)/2 *(G(n-3,k) +(n-3)/3 *(G(n-4,k) + ... +(n-(k-1))/(k-1) *G(n-k,k)...))).
%F A229223 E.g.f. of column k: exp(Sum_{j=1..k} x^j/j!).
%e A229223 G(4,2) = 10: 1/2/3/4, 12/3/4, 13/2/4, 14/2/3, 1/23/4, 1/24/3, 1/2/34, 12/34, 13/24, 14/23.
%e A229223 Triangle G(n,k) begins:
%e A229223   1;
%e A229223   0,  1;
%e A229223   0,  1,   2;
%e A229223   0,  1,   4,    5;
%e A229223   0,  1,  10,   14,   15,
%e A229223   0,  1,  26,   46,   51,   52;
%e A229223   0,  1,  76,  166,  196,  202,  203;
%e A229223   0,  1, 232,  652,  827,  869,  876,  877;
%e A229223   0,  1, 764, 2780, 3795, 4075, 4131, 4139, 4140;
%e A229223   ...
%p A229223 G:= proc(n, k) option remember; `if`(n=0, 1, `if`(k<1, 0,
%p A229223        add(G(n-k*j, k-1) *n!/k!^j/(n-k*j)!/j!, j=0..n/k)))
%p A229223     end:
%p A229223 seq(seq(G(n, k), k=0..n), n=0..10);
%p A229223 # second Maple program:
%p A229223 G:= proc(n, k) option remember; local j; if k>n then G(n, n)
%p A229223       elif n=0 then 1 elif k<1 then 0 else G(n-k, k);
%p A229223       for j from k-1 to 1 by -1 do %*(n-j)/j +G(n-j,k) od; % fi
%p A229223     end:
%p A229223 seq(seq(G(n, k), k=0..n), n=0..10);
%p A229223 # third Maple program:
%p A229223 G:= proc(n, k) option remember; `if`(n=0, 1, add(
%p A229223       G(n-i, k)*binomial(n-1, i-1), i=1..min(n, k)))
%p A229223     end:
%p A229223 seq(seq(G(n, k), k=0..n), n=0..10);  # _Alois P. Heinz_, Jun 26 2017
%p A229223 # fourth Maple program (for columns G(n>=0,k)):
%p A229223 init := n -> seq(a(j) = combinat:-bell(j), j=0..n): # A000110
%p A229223 b := (n, k) -> mul((n - j)/(j + 1), j = 0..k-1):
%p A229223 recg := k -> {(k-1)!*(add(j*b(n, j)*a(n-j), j = 1..k) - n*a(n)), init(k-1)}:
%p A229223 column := proc(k, len) local f; f := gfun:-rectoproc(recg(k), a(n), remember):
%p A229223 map(f, [$0..len-1]) end:
%p A229223 seq(print(column(k, 12)), k=1..9); # _Georg Fischer_, May 19 2021
%t A229223 g[n_, k_] := g[n, k] = If[n == 0, 1, If[k < 1, 0, Sum[g[n - k*j, k - 1] *n!/k!^j/(n - k*j)!/j!, { j, 0, n/k}]]]; Table[Table[g[n, k], { k, 0, n}], {n, 0, 10}] // Flatten (* _Jean-François Alcover_, Dec 09 2013, translated from Maple *)
%Y A229223 Columns k=0-10 give: A000007, A000012, A000085, A001680, A001681, A110038, A148092, A229224, A229225, A229226, A229227.
%Y A229223 Main diagonal gives: A000110. Lower diagonal gives: A058692.
%Y A229223 Cf. A066223 (G(2n,2)), A229228 (G(2n,n)), A229229 (G(n^2,n)), A227223 (G(2^n,n)).
%Y A229223 Cf. A008279, A080510.
%K A229223 nonn,tabl
%O A229223 0,6
%A A229223 _Alois P. Heinz_, Sep 16 2013