A276891 Number T(n,k) of ordered set partitions of [n] where k is minimal such that for each block b the smallest integer interval containing b has at most k elements; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 2, 1, 0, 6, 4, 3, 0, 24, 20, 18, 13, 0, 120, 114, 118, 114, 75, 0, 720, 750, 878, 924, 870, 541, 0, 5040, 5616, 7224, 8152, 8760, 7818, 4683, 0, 40320, 47304, 65514, 79682, 90084, 94560, 81078, 47293, 0, 362880, 443400, 652446, 845874, 998560, 1135776, 1148016, 954474, 545835

Offset

0,5

Links

Alois P. Heinz, Rows n = 0..21, flattened

Formula

T(n,k) = A276890(n,k) - A276890(n,k-1) for k>0, T(n,0) = A000007(n).

Example

Triangle T(n,k) begins:
  1;
  0,     1;
  0,     2,     1;
  0,     6,     4,     3;
  0,    24,    20,    18,    13;
  0,   120,   114,   118,   114,    75;
  0,   720,   750,   878,   924,   870,   541;
  0,  5040,  5616,  7224,  8152,  8760,  7818,  4683;
  0, 40320, 47304, 65514, 79682, 90084, 94560, 81078, 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)]))):
T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):
seq(seq(T(n, k), k=0..n), n=0..10);

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]]]]; T [n_, k_] := A[n, k] - If[k == 0, 0, A[n, k - 1]]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 04 2017, translated from Maple *)

Crossrefs

Columns k=0-10 give: A000007, A000142 (for n>0), A320615, A320616, A320617, A320618, A320619, A320620, A320621, A320622, A320623.

Row sums give: A000670.

Main diagonal gives A000670(n-1) for n>0.

T(2n,n) gives A276892.

Cf. A276727, A276890.

Sequence in context: A090238 A358694 A047922 * A021830 A247686 A352369

Adjacent sequences: A276888 A276889 A276890 * A276892 A276893 A276894

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 21 2016

Status

approved