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

Comments

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

Links

Alois P. Heinz, Rows n = 1..141, flattened

Wikipedia, Partition of a set

Formula

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

Example

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

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

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

Sequence in context: A259873 A121462 A349706 * A218581 A307177 A340264

Adjacent sequences: A271463 A271464 A271465 * A271467 A271468 A271469

Keyword

nonn,tabl

Author

Alois P. Heinz, Apr 08 2016

Status

approved