login
Number T(n,k) of set partitions of [n] into k blocks such that the absolute difference between least elements of consecutive blocks is always > 1; triangle T(n,k), n>=0, 0<=k<=ceiling(n/2), read by rows.
2

%I #53 Jan 09 2022 09:59:44

%S 1,0,1,0,1,0,1,1,0,1,3,0,1,7,2,0,1,15,12,0,1,31,50,6,0,1,63,180,60,0,

%T 1,127,602,390,24,0,1,255,1932,2100,360,0,1,511,6050,10206,3360,120,0,

%U 1,1023,18660,46620,25200,2520,0,1,2047,57002,204630,166824,31920,720

%N Number T(n,k) of set partitions of [n] into k blocks such that the absolute difference between least elements of consecutive blocks is always > 1; triangle T(n,k), n>=0, 0<=k<=ceiling(n/2), read by rows.

%H Alois P. Heinz, <a href="/A298668/b298668.txt">Rows n = 0..200, flattened</a>

%H Wenqin Cao, Emma Yu Jin, and Zhicong Lin, <a href="https://doi.org/10.1016/j.dam.2019.01.035">Enumeration of inversion sequences avoiding triples of relations</a>, Discrete Applied Mathematics (2019); see also <a href="http://www.emmayujin.at/Pubs/CaoJinLin19.pdf">author's copy</a>

%F T(n,k) = (k-1)! * Stirling2(n-k+1,k) for k>0, T(n,0) = A000007(n).

%F T(n,k) = Sum_{j=0..k-1} (-1)^j*C(k-1,j)*(k-j)^(n-k) for k>0, T(n,0) = A000007(n).

%F T(n,k) = (k-1)! * A136011(n,k) for n, k >= 1.

%F Sum_{j>=0} T(n+j,j) = A076726(n) = 2*A000670(n) = A000629(n) + A000007(n).

%e T(5,1) = 1: 12345.

%e T(5,2) = 7: 1234|5, 1235|4, 123|45, 1245|3, 124|35, 125|34, 12|345.

%e T(5,3) = 2: 124|3|5, 12|34|5.

%e T(7,4) = 6: 1246|3|5|7, 124|36|5|7, 124|3|56|7, 126|34|5|7, 12|346|5|7, 12|34|56|7.

%e T(9,5) = 24: 12468|3|5|7|9, 1246|38|5|7|9, 1246|3|58|7|9, 1246|3|5|78|9, 1248|36|5|7|9, 124|368|5|7|9, 124|36|58|7|9, 124|36|5|78|9, 1248|3|56|7|9, 124|38|56|7|9, 124|3|568|7|9, 124|3|56|78|9, 1268|34|5|7|9, 126|348|5|7|9, 126|34|58|7|9, 126|34|5|78|9, 128|346|5|7|9, 12|3468|5|7|9, 12|346|58|7|9, 12|346|5|78|9, 128|34|56|7|9, 12|348|56|7|9, 12|34|568|7|9, 12|34|56|78|9.

%e Triangle T(n,k) begins:

%e 1;

%e 0, 1;

%e 0, 1;

%e 0, 1, 1;

%e 0, 1, 3;

%e 0, 1, 7, 2;

%e 0, 1, 15, 12;

%e 0, 1, 31, 50, 6;

%e 0, 1, 63, 180, 60;

%e 0, 1, 127, 602, 390, 24;

%e 0, 1, 255, 1932, 2100, 360;

%e 0, 1, 511, 6050, 10206, 3360, 120;

%e 0, 1, 1023, 18660, 46620, 25200, 2520;

%e ...

%p b:= proc(n, m, t) option remember; `if`(n=0, x^m, add(

%p b(n-1, max(m, j), `if`(j>m, 1, 0)), j=1..m+1-t))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):

%p seq(T(n), n=0..14);

%p # second Maple program:

%p T:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), (k-1)!*Stirling2(n-k+1, k)):

%p seq(seq(T(n, k), k=0..ceil(n/2)), n=0..14);

%p # third Maple program:

%p T:= proc(n, k) option remember; `if`(k<2, `if`(n=0 xor k=0, 0, 1),

%p `if`(k>ceil(n/2), 0, add((k-j)*T(n-1-j, k-j), j=0..1)))

%p end:

%p seq(seq(T(n, k), k=0..ceil(n/2)), n=0..14);

%t T[n_, k_] := T[n, k] = If[k < 2, If[Xor[n == 0, k == 0], 0, 1],

%t If[k > Ceiling[n/2], 0, Sum[(k-j) T[n-1-j, k-j], {j, 0, 1}]]];

%t Table[Table[T[n, k], {k, 0, Ceiling[n/2]}], {n, 0, 14}] // Flatten (* _Jean-François Alcover_, Mar 08 2021, after third Maple program *)

%Y Columns k=0-11 give (offsets may differ): A000007, A057427, A168604, A028243, A028244, A028245, A032180, A228909, A228910, A228911, A228912, A228913.

%Y Row sums give A229046(n-1) for n>0.

%Y T(2n+1,n+1) gives A000142.

%Y T(2n,n) gives A001710(n+1).

%Y Cf. A000629, A000670, A008277, A028246, A048993, A076726, A110654, A136011, A173018.

%K nonn,tabf

%O 0,11

%A _Alois P. Heinz_, Jan 24 2018