A298668 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.

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, 1, 127, 602, 390, 24, 0, 1, 255, 1932, 2100, 360, 0, 1, 511, 6050, 10206, 3360, 120, 0, 1, 1023, 18660, 46620, 25200, 2520, 0, 1, 2047, 57002, 204630, 166824, 31920, 720

Offset: 0

Author

Alois P. Heinz, Jan 24 2018

Keywords

• nonn
• tabf

Examples

			T(5,1) = 1: 12345.
T(5,2) = 7: 1234|5, 1235|4, 123|45, 1245|3, 124|35, 125|34, 12|345.
T(5,3) = 2: 124|3|5, 12|34|5.
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.
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.
Triangle T(n,k) begins:
  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, 1,  127,   602,   390,    24;
  0, 1,  255,  1932,  2100,   360;
  0, 1,  511,  6050, 10206,  3360,  120;
  0, 1, 1023, 18660, 46620, 25200, 2520;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..200, flattened
• Wenqin Cao, Emma Yu Jin, and Zhicong Lin, Enumeration of inversion sequences avoiding triples of relations, Discrete Applied Mathematics (2019); see also author's copy

Crossrefs

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

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

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

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

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

Programs

Maple

b:= proc(n, m, t) option remember; `if`(n=0, x^m, add(
      b(n-1, max(m, j), `if`(j>m, 1, 0)), j=1..m+1-t))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..14);
# second Maple program:
T:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), (k-1)!*Stirling2(n-k+1, k)):
seq(seq(T(n, k), k=0..ceil(n/2)), n=0..14);
# third Maple program:
T:= proc(n, k) option remember; `if`(k<2, `if`(n=0 xor k=0, 0, 1),
      `if`(k>ceil(n/2), 0, add((k-j)*T(n-1-j, k-j), j=0..1)))
    end:
seq(seq(T(n, k), k=0..ceil(n/2)), n=0..14);

Mathematica

T[n_, k_] := T[n, k] = If[k < 2, If[Xor[n == 0, k == 0], 0, 1],
     If[k > Ceiling[n/2], 0, Sum[(k-j) T[n-1-j, k-j], {j, 0, 1}]]];
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 *)

Formula

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

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

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

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