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

Comments

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

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

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

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.

Sequence in context: A216656 A353435 A295679 * A287216 A145515 A267383

Adjacent sequences: A287211 A287212 A287213 * A287215 A287216 A287217

Keyword

nonn,tabl

Author

Alois P. Heinz, May 21 2017

Status

approved