A271466 Number T(n,k) of set partitions of [n] such that k is the largest element of the last block; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

1, 0, 2, 0, 1, 4, 0, 1, 4, 10, 0, 1, 6, 15, 30, 0, 1, 10, 29, 59, 104, 0, 1, 18, 63, 139, 250, 406, 0, 1, 34, 149, 365, 692, 1145, 1754, 0, 1, 66, 375, 1039, 2110, 3627, 5649, 8280, 0, 1, 130, 989, 3149, 6932, 12521, 20085, 29874, 42294, 0, 1, 258, 2703, 10039, 24190, 46299, 77133, 117488, 168509, 231950

Offset: 1

Author

Alois P. Heinz, Apr 08 2016

Keywords

• nonn
• tabl

Comments

Each set partition is written as a sequence of blocks, ordered by the smallest elements in the blocks.

Examples

			T(1,1) = 1: 1.
T(2,2) = 2: 12, 1|2.
T(3,2) = 1: 13|2.
T(3,3) = 4: 123, 12|3, 1|23, 1|2|3.
T(4,2) = 1: 134|2.
T(4,3) = 4: 124|3, 14|23, 14|2|3, 1|24|3.
T(4,4) = 10: 1234, 123|4, 12|34, 12|3|4, 13|24, 13|2|4, 1|234, 1|23|4, 1|2|34, 1|2|3|4.
T(5,2) = 1: 1345|2.
T(5,3) = 6: 1245|3, 145|23, 145|2|3, 14|25|3, 15|24|3, 1|245|3.
T(5,4) = 15: 1235|4, 125|34, 125|3|4, 12|35|4, 135|24, 135|2|4, 13|25|4, 15|234, 15|23|4, 1|235|4, 15|2|34, 1|25|34, 15|2|3|4, 1|25|3|4, 1|2|35|4.
Triangle T(n,k) begins:
  1;
  0, 2;
  0, 1,   4;
  0, 1,   4,  10;
  0, 1,   6,  15,   30;
  0, 1,  10,  29,   59,  104;
  0, 1,  18,  63,  139,  250,   406;
  0, 1,  34, 149,  365,  692,  1145,  1754;
  0, 1,  66, 375, 1039, 2110,  3627,  5649,  8280;
  0, 1, 130, 989, 3149, 6932, 12521, 20085, 29874, 42294;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened
• Wikipedia, Partition of a set

Crossrefs

Columns k=1-10 give: A000007(n-1), A054977(n-2), A052548(n-3) for n>3, A271743, A271744, A271745, A271746, A271747, A271748, A271749.

Main diagonal gives A186021(n-1).

Lower diagonals d=1-10 give: A271752, A271753, A271754, A271755, A271756, A271757, A271758, A271759, A271760, A271761.

Row sums give A000110.

T(2n,n) gives A271467.

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

Cf. A095149 (k is maximum of the first block), A113547 (k is minimum of the last block).

Programs

Maple

b:= proc(n, m, c) option remember; `if`(n=0, x^c, add(
      b(n-1, max(m, j), `if`(j>=m, n, c)), j=1..m+1))
    end:
T:= n-> (p-> seq(coeff(p, x, n-i), i=0..n-1))(b(n, 0$2)):
seq(T(n), n=1..12);

Mathematica

b[n_, m_, c_] := b[n, m, c] = If[n == 0, x^c, Sum[b[n-1, Max[m, j], If[j >= m, n, c]], {j, 1, m+1}]];
T[n_] := Function[p, Table[Coefficient[p, x, n-i], {i, 0, n-1}]][b[n, 0, 0]];
Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Apr 24 2016, translated from Maple *)

Formula

T(n,n) = 2 * A000110(n-1) = 2 * Sum_{j=0..n-1} T(n-1,j) for n>1.