A276890 Number A(n,k) of ordered set partitions of [n] such that for each block b the smallest integer interval containing b has at most k elements; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 1, 2, 0, 1, 1, 3, 6, 0, 1, 1, 3, 10, 24, 0, 1, 1, 3, 13, 44, 120, 0, 1, 1, 3, 13, 62, 234, 720, 0, 1, 1, 3, 13, 75, 352, 1470, 5040, 0, 1, 1, 3, 13, 75, 466, 2348, 10656, 40320, 0, 1, 1, 3, 13, 75, 541, 3272, 17880, 87624, 362880, 0

Offset: 0

Author

Alois P. Heinz, Sep 21 2016

Keywords

• nonn
• tabl

Comments

Column k > 0 is asymptotic to exp(k-1) * n!. - Vaclav Kotesovec, Sep 22 2016

Examples

			Square array A(n,k) begins:
  1,    1,     1,     1,     1,     1,     1,     1, ...
  0,    1,     1,     1,     1,     1,     1,     1, ...
  0,    2,     3,     3,     3,     3,     3,     3, ...
  0,    6,    10,    13,    13,    13,    13,    13, ...
  0,   24,    44,    62,    75,    75,    75,    75, ...
  0,  120,   234,   352,   466,   541,   541,   541, ...
  0,  720,  1470,  2348,  3272,  4142,  4683,  4683, ...
  0, 5040, 10656, 17880, 26032, 34792, 42610, 47293, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..42, flattened

Crossrefs

Columns k=0-10: A000007, A000142, A240172, A276893, A276894, A276895, A276896, A276897, A276898, A276899, A276900.

Main diagonal gives: A000670.

Cf. A276719, A276891.

Programs

Maple

b:= proc(n, m, l) option remember; `if`(n=0, m!,
      add(b(n-1, max(m, j), [subsop(1=NULL, l)[],
      `if`(j<=m, 0, j)]), j={l[], m+1} minus {0}))
    end:
A:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0),
             `if`(k=1, n!, b(n, 0, [0$(k-1)]))):
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

b[n_, m_, l_List] := b[n, m, l] = If[n == 0, m!, Sum[b[n - 1, Max[m, j], Append[ReplacePart[l, 1 -> Nothing], If[j <= m, 0, j]]], {j, Append[l, m + 1] ~Complement~ {0}}]]; A[n_, k_] := If[k==0, If[n==0, 1, 0], If[k==1, n!, b[n, 0, Array[0&, k-1]]]]; Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Jan 06 2017, after Alois P. Heinz *)

Formula

A(n,k) = Sum_{j=0..k} A276891(n,j).