A287216 Number A(n,k) of set partitions of [n] such that all absolute differences between least elements of consecutive blocks 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, 9, 1, 1, 1, 2, 5, 14, 23, 1, 1, 1, 2, 5, 15, 44, 66, 1, 1, 1, 2, 5, 15, 51, 152, 210, 1, 1, 1, 2, 5, 15, 52, 191, 571, 733, 1, 1, 1, 2, 5, 15, 52, 202, 780, 2317, 2781, 1, 1, 1, 2, 5, 15, 52, 203, 857, 3440, 10096, 11378, 1
Offset: 0
Examples
A(4,0) = 1: 1234. A(4,1) = 9: 1234, 134|2, 13|24, 14|23, 1|234, 14|2|3, 1|24|3, 1|2|34, 1|2|3|4. A(4,2) = 14: 1234, 124|3, 12|34, 12|3|4, 134|2, 13|24, 13|2|4, 14|23, 1|234, 1|23|4, 14|2|3, 1|24|3, 1|2|34, 1|2|3|4. A(5,1) = 23: 12345, 1345|2, 134|25, 135|24, 13|245, 145|23, 14|235, 15|234, 1|2345, 145|2|3, 14|25|3, 14|2|35, 15|24|3, 1|245|3, 1|24|35, 15|2|34, 1|25|34, 1|2|345, 15|2|3|4, 1|25|3|4, 1|2|35|4, 1|2|3|45, 1|2|3|4|5. 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, 9, 14, 15, 15, 15, 15, 15, ... 1, 23, 44, 51, 52, 52, 52, 52, ... 1, 66, 152, 191, 202, 203, 203, 203, ... 1, 210, 571, 780, 857, 876, 877, 877, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..140, flattened
- Wikipedia, Partition of a set
Crossrefs
Programs
-
Maple
b:= proc(n, k, m, l) option remember; `if`(n<1, 1, `if`(l-n>k, 0, b(n-1, k, m+1, n))+m*b(n-1, k, m, l)) end: A:= (n, k)-> b(n-1, min(k, n-1), 1, n): seq(seq(A(n, d-n), n=0..d), d=0..12); -
Mathematica
b[n_, k_, m_, l_] := b[n, k, m, l] = If[n < 1, 1, If[l - n > k, 0, b[n - 1, k, m + 1, n]] + m*b[n - 1, k, m, l]]; A[n_, k_] := b[n - 1, Min[k, n - 1], 1, n]; 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} A287215(n,j).