login
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.
19

%I #50 May 21 2021 16:30:49

%S 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 203,0,1,232,652,827,869,876,877,0,1,764,2780,3795,4075,4131,4139,

%U 4140,0,1,2620,12644,18755,20645,21065,21137,21146,21147

%N 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 _John Riordan_ calls these Allied Bell Numbers. - _N. J. A. Sloane_, Jan 10 2018

%C 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 G(n,k) - G(n,k-1) = A080510(n,k).

%C 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 Alois P. Heinz, <a href="/A229223/b229223.txt">Rows n = 0..140, flattened</a>

%H J. Riordan, <a href="/A229223/a229223.pdf">Letter, 11/23/1970</a>

%F 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 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 E.g.f. of column k: exp(Sum_{j=1..k} x^j/j!).

%e 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 Triangle G(n,k) begins:

%e 1;

%e 0, 1;

%e 0, 1, 2;

%e 0, 1, 4, 5;

%e 0, 1, 10, 14, 15,

%e 0, 1, 26, 46, 51, 52;

%e 0, 1, 76, 166, 196, 202, 203;

%e 0, 1, 232, 652, 827, 869, 876, 877;

%e 0, 1, 764, 2780, 3795, 4075, 4131, 4139, 4140;

%e ...

%p G:= proc(n, k) option remember; `if`(n=0, 1, `if`(k<1, 0,

%p add(G(n-k*j, k-1) *n!/k!^j/(n-k*j)!/j!, j=0..n/k)))

%p end:

%p seq(seq(G(n, k), k=0..n), n=0..10);

%p # second Maple program:

%p G:= proc(n, k) option remember; local j; if k>n then G(n, n)

%p elif n=0 then 1 elif k<1 then 0 else G(n-k, k);

%p for j from k-1 to 1 by -1 do %*(n-j)/j +G(n-j,k) od; % fi

%p end:

%p seq(seq(G(n, k), k=0..n), n=0..10);

%p # third Maple program:

%p G:= proc(n, k) option remember; `if`(n=0, 1, add(

%p G(n-i, k)*binomial(n-1, i-1), i=1..min(n, k)))

%p end:

%p seq(seq(G(n, k), k=0..n), n=0..10); # _Alois P. Heinz_, Jun 26 2017

%p # fourth Maple program (for columns G(n>=0,k)):

%p init := n -> seq(a(j) = combinat:-bell(j), j=0..n): # A000110

%p b := (n, k) -> mul((n - j)/(j + 1), j = 0..k-1):

%p recg := k -> {(k-1)!*(add(j*b(n, j)*a(n-j), j = 1..k) - n*a(n)), init(k-1)}:

%p column := proc(k, len) local f; f := gfun:-rectoproc(recg(k), a(n), remember):

%p map(f, [$0..len-1]) end:

%p seq(print(column(k, 12)), k=1..9); # _Georg Fischer_, May 19 2021

%t 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 Columns k=0-10 give: A000007, A000012, A000085, A001680, A001681, A110038, A148092, A229224, A229225, A229226, A229227.

%Y Main diagonal gives: A000110. Lower diagonal gives: A058692.

%Y Cf. A066223 (G(2n,2)), A229228 (G(2n,n)), A229229 (G(n^2,n)), A227223 (G(2^n,n)).

%Y Cf. A008279, A080510.

%K nonn,tabl

%O 0,6

%A _Alois P. Heinz_, Sep 16 2013