login
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.
23

%I #30 Sep 08 2021 07:15:30

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

%T 406,0,1,34,149,365,692,1145,1754,0,1,66,375,1039,2110,3627,5649,8280,

%U 0,1,130,989,3149,6932,12521,20085,29874,42294,0,1,258,2703,10039,24190,46299,77133,117488,168509,231950

%N 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.

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

%H Alois P. Heinz, <a href="/A271466/b271466.txt">Rows n = 1..141, flattened</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_of_a_set">Partition of a set</a>

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

%e T(1,1) = 1: 1.

%e T(2,2) = 2: 12, 1|2.

%e T(3,2) = 1: 13|2.

%e T(3,3) = 4: 123, 12|3, 1|23, 1|2|3.

%e T(4,2) = 1: 134|2.

%e T(4,3) = 4: 124|3, 14|23, 14|2|3, 1|24|3.

%e 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.

%e T(5,2) = 1: 1345|2.

%e T(5,3) = 6: 1245|3, 145|23, 145|2|3, 14|25|3, 15|24|3, 1|245|3.

%e 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.

%e Triangle T(n,k) begins:

%e 1;

%e 0, 2;

%e 0, 1, 4;

%e 0, 1, 4, 10;

%e 0, 1, 6, 15, 30;

%e 0, 1, 10, 29, 59, 104;

%e 0, 1, 18, 63, 139, 250, 406;

%e 0, 1, 34, 149, 365, 692, 1145, 1754;

%e 0, 1, 66, 375, 1039, 2110, 3627, 5649, 8280;

%e 0, 1, 130, 989, 3149, 6932, 12521, 20085, 29874, 42294;

%e ...

%p b:= proc(n, m, c) option remember; `if`(n=0, x^c, add(

%p b(n-1, max(m, j), `if`(j>=m, n, c)), j=1..m+1))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, n-i), i=0..n-1))(b(n, 0$2)):

%p seq(T(n), n=1..12);

%t 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 T[n_] := Function[p, Table[Coefficient[p, x, n-i], {i, 0, n-1}]][b[n, 0, 0]];

%t Table[T[n], {n, 1, 12}] // Flatten (* _Jean-François Alcover_, Apr 24 2016, translated from Maple *)

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

%Y Main diagonal gives A186021(n-1).

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

%Y Row sums give A000110.

%Y T(2n,n) gives A271467.

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

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

%K nonn,tabl

%O 1,3

%A _Alois P. Heinz_, Apr 08 2016