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
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
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).
Comments