cp's OEIS Frontend

A287417 Number A(n,k) of set partitions of [n] such that all absolute differences between least elements of consecutive blocks and between consecutive elements within the blocks are not larger than k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

%I A287417 #21 Oct 18 2018 15:47:06
%S A287417 1,1,1,1,1,0,1,1,2,0,1,1,2,3,0,1,1,2,5,4,0,1,1,2,5,12,5,0,1,1,2,5,15,
%T A287417 27,6,0,1,1,2,5,15,46,58,7,0,1,1,2,5,15,52,139,121,8,0,1,1,2,5,15,52,
%U A287417 187,410,248,9,0,1,1,2,5,15,52,203,677,1189,503,10,0
%N A287417 Number A(n,k) of set partitions of [n] such that all absolute differences between least elements of consecutive blocks and between consecutive elements within the blocks are not larger than k; square array A(n,k), n>=0, k>=0, read by antidiagonals.
%H A287417 Alois P. Heinz, <a href="/A287417/b287417.txt">Antidiagonals n = 0..40, flattened</a>
%H A287417 Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_of_a_set">Partition of a set</a>
%F A287417 A(n,k) = Sum_{j=0..k} A287416(n,j).
%e A287417 A(5,3) = 46 = 52 - 6 = A000110(5) - 6 counts all set partitions of [5] except: 1234|5, 15|234, 15|23|4, 15|24|3, 15|2|34, 15|2|3|4.
%e A287417 Square array A(n,k) begins:
%e A287417   1, 1,   1,   1,   1,   1,   1,   1, ...
%e A287417   1, 1,   1,   1,   1,   1,   1,   1, ...
%e A287417   0, 2,   2,   2,   2,   2,   2,   2, ...
%e A287417   0, 3,   5,   5,   5,   5,   5,   5, ...
%e A287417   0, 4,  12,  15,  15,  15,  15,  15, ...
%e A287417   0, 5,  27,  46,  52,  52,  52,  52, ...
%e A287417   0, 6,  58, 139, 187, 203, 203, 203, ...
%e A287417   0, 7, 121, 410, 677, 824, 877, 877, ...
%p A287417 b:= proc(n, k, l, t) option remember; `if`(n<1, 1, `if`(t-n>k, 0,
%p A287417        b(n-1, k, map(x-> `if`(x-n>=k, [][], x), [l[], n]), n)) +add(
%p A287417        b(n-1, k, sort(map(x-> `if`(x-n>=k, [][], x), subsop(j=n, l))),
%p A287417        `if`(t-n>k, infinity, t)), j=1..nops(l)))
%p A287417     end:
%p A287417 A:= (n, k)-> b(n, min(k, n-1), [], n):
%p A287417 seq(seq(A(n, d-n), n=0..d), d=0..14);
%t A287417 b[n_, k_, l_, t_] := b[n, k, l, t] = If[n < 1, 1, If[t - n > k, 0, b[n - 1, k, If[# - n >= k, Nothing, #]& /@  Append[l, n], n]] + Sum[b[n - 1, k, Sort[If[# - n >= k, Nothing, #]& /@ ReplacePart[l, j -> n]], If[t - n > k, Infinity, t]], {j, 1, Length[l]}]];
%t A287417 A[n_, k_] := b[n, Min[k, n - 1], {}, n];
%t A287417 Table[A[n, d - n], {d, 0, 14}, { n, 0, d}] // Flatten (* _Jean-François Alcover_, May 24 2018, translated from Maple *)
%Y A287417 Columns k=1-10 give: A028310, A000325, A287582, A287583, A287584, A287585, A287586, A287587, A287588, A287589.
%Y A287417 Main diagonal gives A000110.
%Y A287417 Cf. A287214, A287216, A287416, A287641.
%K A287417 nonn,tabl
%O A287417 0,9
%A A287417 _Alois P. Heinz_, May 24 2017