login
Number A(n,k) of set partitions of [n] such that for each block b the smallest integer interval containing b has at most k elements; square array A(n,k), n>=0, k>=0, read by antidiagonals.
12

%I #28 Dec 27 2018 16:30:04

%S 1,1,0,1,1,0,1,1,1,0,1,1,2,1,0,1,1,2,3,1,0,1,1,2,5,5,1,0,1,1,2,5,10,8,

%T 1,0,1,1,2,5,15,20,13,1,0,1,1,2,5,15,37,42,21,1,0,1,1,2,5,15,52,87,87,

%U 34,1,0,1,1,2,5,15,52,151,208,179,55,1,0,1,1,2,5,15,52,203,409,515,370,89,1,0

%N Number A(n,k) of set partitions of [n] such that for each block b the smallest integer interval containing b has at most k elements; square array A(n,k), n>=0, k>=0, read by antidiagonals.

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

%H Alois P. Heinz, <a href="/A276719/b276719.txt">Antidiagonals n = 0..40, flattened</a>

%H Pierpaolo Natalini, Paolo Emilio Ricci, <a href="https://doi.org/10.3390/axioms7040071">New Bell-Sheffer Polynomial Sets</a>, Axioms 2018, 7(4), 71.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_of_a_set">Partition of a set</a>

%F A(n,k) = Sum_{i=0..k} A276727(n,i).

%e A(3,2) = 3: 12|3, 1|23, 1|2|3.

%e A(4,3) = 10: 123|4, 12|34, 12|3|4, 13|24, 13|2|4, 1|234, 1|23|4, 1|24|3, 1|2|34, 1|2|3|4.

%e A(5,4) = 37: 1234|5, 123|45, 123|4|5, 124|35, 124|3|5, 12|345, 12|34|5, 12|35|4, 12|3|45, 12|3|4|5, 134|25, 134|2|5, 13|245, 13|24|5, 13|25|4, 13|2|45, 13|2|4|5, 14|235, 14|23|5, 1|2345, 1|234|5, 1|235|4, 1|23|45, 1|23|4|5, 14|25|3, 14|2|35, 14|2|3|5, 1|245|3, 1|24|35, 1|24|3|5, 1|25|34, 1|2|345, 1|2|34|5, 1|25|3|4, 1|2|35|4, 1|2|3|45, 1|2|3|4|5.

%e Square array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 0, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 0, 1, 2, 2, 2, 2, 2, 2, 2, ...

%e 0, 1, 3, 5, 5, 5, 5, 5, 5, ...

%e 0, 1, 5, 10, 15, 15, 15, 15, 15, ...

%e 0, 1, 8, 20, 37, 52, 52, 52, 52, ...

%e 0, 1, 13, 42, 87, 151, 203, 203, 203, ...

%e 0, 1, 21, 87, 208, 409, 674, 877, 877, ...

%e 0, 1, 34, 179, 515, 1100, 2066, 3263, 4140, ...

%p b:= proc(n, m, l) option remember; `if`(n=0, 1,

%p add(b(n-1, max(m, j), [subsop(1=NULL, l)[],

%p `if`(j<=m, 0, j)]), j={l[], m+1} minus {0}))

%p end:

%p A:= (n, k)-> `if`(n=0, 1, `if`(k<2, k, b(n, 0, [0$(k-1)]))):

%p seq(seq(A(n, d-n), n=0..d), d=0..14);

%t b[n_, m_, l_List] := b[n, m, l] = If[n == 0, 1, Sum[b[n - 1, Max[m, j], Append[ReplacePart[l, 1 -> Nothing], If[j <= m, 0, j]]], {j, Append[l, m + 1] ~Complement~ {0}}]]; A[n_, k_] := If[n == 0, 1, If[k < 2, k, b[n, 0, Array[0&, k-1]]]]; Table[A[n, d-n], {d, 0, 14}, {n, 0, d}] // Flatten (* _Jean-François Alcover_, Jan 06 2017, after _Alois P. Heinz_ *)

%Y Columns k=0..10 give: A000007, A000012, A000045(n+1), A129847, A276720, A276721, A276722, A276723, A276724, A276725, A276726.

%Y Main diagonal gives A000110.

%Y A(n+1,n) gives A005493(n-1) for n>0.

%Y Cf. A276727, A276837.

%K nonn,tabl

%O 0,13

%A _Alois P. Heinz_, Sep 16 2016