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