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,9

Comments

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

Links

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

Formula

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

Example

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

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

Crossrefs

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

Main diagonal gives: A000670.

Cf. A276719, A276891.

Sequence in context: A215086 A261440 A295684 * A276921 A339677 A333158

Adjacent sequences: A276887 A276888 A276889 * A276891 A276892 A276893

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 21 2016

Status

approved