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.

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

Author

Alois P. Heinz, May 21 2017

Keywords

• nonn
• tabl

Comments

The sequence of column k satisfies a linear recurrence with constant coefficients of order 2^(k-1) for k>0.

Examples

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

Links

• Alois P. Heinz, Antidiagonals n = 0..45, flattened
• Pierpaolo Natalini, Paolo Emilio Ricci, New Bell-Sheffer Polynomial Sets, Axioms 2018, 7(4), 71.
• Wikipedia, Partition of a set

Crossrefs

Columns k=0-10 give: A000012, A011782, A001519, A287275, A287276, A287277, A287278, A287279, A287280, A287281, A287282.

Main diagonal gives A000110.

Cf. A287213, A287216, A287417, A287641.

Programs

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

Formula

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