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,7

Links

Alois P. Heinz, Rows n = 0..40, flattened

Wikipedia, Partition of a set

Formula

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

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

Example

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;

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

Crossrefs

Row sums give A000110.

Cf. A161680, A271023.

Sequence in context: A357638 A238414 A195151 * A125208 A333351 A193140

Adjacent sequences: A271021 A271022 A271023 * A271025 A271026 A271027

Keyword

nonn,look,tabf

Author

Alois P. Heinz, Mar 28 2016

Status

approved