A271024 Number T(n,k) of set partitions of [n] having exactly k pairs (i,j) with i < j such that i and j are in different blocks; triangle T(n,k), n >= 0, 0 <= k <= n*(n-1)/2 read by rows.

1, 1, 1, 1, 1, 0, 3, 1, 1, 0, 0, 4, 3, 6, 1, 1, 0, 0, 0, 5, 0, 10, 10, 15, 10, 1, 1, 0, 0, 0, 0, 6, 0, 0, 15, 25, 0, 60, 35, 45, 15, 1, 1, 0, 0, 0, 0, 0, 7, 0, 0, 0, 21, 21, 35, 0, 105, 105, 105, 210, 140, 105, 21, 1, 1, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 28, 28

Offset: 0

Author

Alois P. Heinz, Mar 28 2016

Keywords

• nonn
• look
• tabf

Examples

			T(3,0) = 1: 123.
T(3,2) = 3: 12|3, 13|2, 1|23.
T(3,3) = 1: 1|2|3.
Triangle T(n,k) begins:
  1;
  1;
  1, 1;
  1, 0, 3, 1;
  1, 0, 0, 4, 3, 6,  1;
  1, 0, 0, 0, 5, 0, 10, 10, 15, 10, 1;
  1, 0, 0, 0, 0, 6,  0,  0, 15, 25, 0, 60, 35, 45, 15, 1;
		

Links

• Alois P. Heinz, Rows n = 0..40, flattened
• Wikipedia, Partition of a set

Crossrefs

Row sums give A000110.

Cf. A161680, A271023.

Programs

Maple

b:= proc(n, l) option remember; `if`(n=0, x^(m->
      add(j*(m-j)/2, j=l))(add(i, i=l)), b(n-1, [l[], 1])+
      add(b(n-1, subsop(j=l[j]+1, l)), j=1..nops(l)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, [])):
seq(T(n), n=0..10);

Mathematica

b[n_, l_] := b[n, l] = If[n == 0, x^Function[m, Sum[(1/2)*j*(m - j), {j, l}]][Total[l]], Sum[b[n - 1, ReplacePart[l, j -> l[[j]] + 1]], {j, 1, Length[l]}] + b[n - 1, Append[l, 1]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, {}]];
Flatten[Table[T[n], {n, 0, 10}]] (* Jean-François Alcover, May 27 2018, translated from Maple *)

Formula

T(n,k) = A271023(n,n*(n-1)/2-k).

T(n,n-1) = n for n >= 3.