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.

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, 203, 0, 1, 232, 652, 827, 869, 876, 877, 0, 1, 764, 2780, 3795, 4075, 4131, 4139, 4140, 0, 1, 2620, 12644, 18755, 20645, 21065, 21137, 21146, 21147

Offset: 0

Author

Alois P. Heinz, Sep 16 2013

Keywords

• nonn
• tabl

Comments

John Riordan calls these Allied Bell Numbers. - N. J. A. Sloane, Jan 10 2018

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.

G(n,k) - G(n,k-1) = A080510(n,k).

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

Examples

			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.
Triangle G(n,k) begins:
  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,  203;
  0,  1, 232,  652,  827,  869,  876,  877;
  0,  1, 764, 2780, 3795, 4075, 4131, 4139, 4140;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened
• J. Riordan, Letter, 11/23/1970

Crossrefs

Columns k=0-10 give: A000007, A000012, A000085, A001680, A001681, A110038, A148092, A229224, A229225, A229226, A229227.

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

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

Cf. A008279, A080510.

Programs

Maple

G:= proc(n, k) option remember; `if`(n=0, 1, `if`(k<1, 0,
       add(G(n-k*j, k-1) *n!/k!^j/(n-k*j)!/j!, j=0..n/k)))
    end:
seq(seq(G(n, k), k=0..n), n=0..10);
# second Maple program:
G:= proc(n, k) option remember; local j; if k>n then G(n, n)
      elif n=0 then 1 elif k<1 then 0 else G(n-k, k);
      for j from k-1 to 1 by -1 do %*(n-j)/j +G(n-j,k) od; % fi
    end:
seq(seq(G(n, k), k=0..n), n=0..10);
# third Maple program:
G:= proc(n, k) option remember; `if`(n=0, 1, add(
      G(n-i, k)*binomial(n-1, i-1), i=1..min(n, k)))
    end:
seq(seq(G(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Jun 26 2017
# fourth Maple program (for columns G(n>=0,k)):
init := n -> seq(a(j) = combinat:-bell(j), j=0..n): # A000110
b := (n, k) -> mul((n - j)/(j + 1), j = 0..k-1):
recg := k -> {(k-1)!*(add(j*b(n, j)*a(n-j), j = 1..k) - n*a(n)), init(k-1)}:
column := proc(k, len) local f; f := gfun:-rectoproc(recg(k), a(n), remember):
map(f, [$0..len-1]) end:
seq(print(column(k, 12)), k=1..9); # Georg Fischer, May 19 2021

Mathematica

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 *)

Formula

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!).

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)...))).

E.g.f. of column k: exp(Sum_{j=1..k} x^j/j!).