login
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.
12

%I #16 Sep 21 2018 12:25:46

%S 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,

%T 13,62,234,720,0,1,1,3,13,75,352,1470,5040,0,1,1,3,13,75,466,2348,

%U 10656,40320,0,1,1,3,13,75,541,3272,17880,87624,362880,0

%N 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.

%C Column k > 0 is asymptotic to exp(k-1) * n!. - _Vaclav Kotesovec_, Sep 22 2016

%H Alois P. Heinz, <a href="/A276890/b276890.txt">Antidiagonals n = 0..42, flattened</a>

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

%e Square array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 0, 1, 1, 1, 1, 1, 1, 1, ...

%e 0, 2, 3, 3, 3, 3, 3, 3, ...

%e 0, 6, 10, 13, 13, 13, 13, 13, ...

%e 0, 24, 44, 62, 75, 75, 75, 75, ...

%e 0, 120, 234, 352, 466, 541, 541, 541, ...

%e 0, 720, 1470, 2348, 3272, 4142, 4683, 4683, ...

%e 0, 5040, 10656, 17880, 26032, 34792, 42610, 47293, ...

%p b:= proc(n, m, l) option remember; `if`(n=0, m!,

%p add(b(n-1, max(m, j), [subsop(1=NULL, l)[],

%p `if`(j<=m, 0, j)]), j={l[], m+1} minus {0}))

%p end:

%p A:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0),

%p `if`(k=1, n!, b(n, 0, [0$(k-1)]))):

%p seq(seq(A(n, d-n), n=0..d), d=0..12);

%t 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_ *)

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

%Y Main diagonal gives: A000670.

%Y Cf. A276719, A276891.

%K nonn,tabl

%O 0,9

%A _Alois P. Heinz_, Sep 21 2016