login
A287214
Number A(n,k) of set partitions of [n] such that for each block all absolute differences between consecutive elements are <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.
13
1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 4, 1, 1, 1, 2, 5, 8, 1, 1, 1, 2, 5, 13, 16, 1, 1, 1, 2, 5, 15, 34, 32, 1, 1, 1, 2, 5, 15, 47, 89, 64, 1, 1, 1, 2, 5, 15, 52, 150, 233, 128, 1, 1, 1, 2, 5, 15, 52, 188, 481, 610, 256, 1, 1, 1, 2, 5, 15, 52, 203, 696, 1545, 1597, 512, 1
OFFSET
0,9
COMMENTS
The sequence of column k satisfies a linear recurrence with constant coefficients of order 2^(k-1) for k>0.
LINKS
Pierpaolo Natalini, Paolo Emilio Ricci, New Bell-Sheffer Polynomial Sets, Axioms 2018, 7(4), 71.
FORMULA
A(n,k) = Sum_{j=0..k} A287213(n,j).
EXAMPLE
A(4,0) = 1: 1|2|3|4.
A(4,1) = 8: 1234, 123|4, 12|34, 12|3|4, 1|234, 1|23|4, 1|2|34, 1|2|3|4.
A(4,2) = 13: 1234, 123|4, 124|3, 12|34, 12|3|4, 134|2, 13|24, 13|2|4, 1|234, 1|23|4, 1|24|3, 1|2|34, 1|2|3|4.
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 1, 1, 1, ...
1, 2, 2, 2, 2, 2, 2, 2, ...
1, 4, 5, 5, 5, 5, 5, 5, ...
1, 8, 13, 15, 15, 15, 15, 15, ...
1, 16, 34, 47, 52, 52, 52, 52, ...
1, 32, 89, 150, 188, 203, 203, 203, ...
1, 64, 233, 481, 696, 825, 877, 877, ...
MAPLE
b:= proc(n, k, l) option remember; `if`(n=0, 1, b(n-1, k, map(x->
`if`(x-n>=k, [][], x), [l[], n]))+add(b(n-1, k, sort(map(x->
`if`(x-n>=k, [][], x), subsop(j=n, l)))), j=1..nops(l)))
end:
A:= (n, k)-> b(n, min(k, n-1), []):
seq(seq(A(n, d-n), n=0..d), d=0..12);
MATHEMATICA
b[0, _, _] = 1; b[n_, k_, l_List] := b[n, k, l] = b[n - 1, k, If[# - n >= k, Nothing, #]& /@ Append[l, n]] + Sum[b[n - 1, k, Sort[If[# - n >= k, Nothing, #]& /@ ReplacePart[l, j -> n]]], {j, 1, Length[l]}];
A[n_, k_] := b[n, Min[k, n - 1], {}];
Table[A[n, d - n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Apr 30 2018, after Alois P. Heinz *)
CROSSREFS
Main diagonal gives A000110.
Sequence in context: A216656 A353435 A295679 * A287216 A145515 A267383
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, May 21 2017
STATUS
approved