A270953 Number T(n,k) of set partitions of [n] having exactly k pairs (m,m+1) such that m+1 is in some block b and m is in block b+1; triangle T(n,k), n>=0, 0<=k<=n-floor((1+sqrt(max(0,8n-7)))/2), read by rows.

1, 1, 2, 4, 1, 9, 6, 25, 24, 3, 84, 91, 27, 1, 323, 374, 159, 21, 1377, 1699, 857, 197, 10, 6412, 8410, 4726, 1421, 174, 4, 32312, 44794, 27385, 9573, 1783, 127, 1, 174941, 254718, 167097, 64724, 15158, 1856, 76, 1011357, 1538027, 1071422, 449567, 121464, 20074, 1650, 36

Offset: 0

Author

Alois P. Heinz, Mar 26 2016

Keywords

• nonn
• tabf

Examples

			T(3,1) = 1: 13|2.
T(4,1) = 6: 124|3, 134|2, 13|24, 13|2|4, 14|23, 1|24|3.
T(5,2) = 3: 135|24, 13|25|4, 15|24|3.
T(6,3) = 1: 136|25|4.
T(7,3) = 21: 1247|36|5, 1347|26|5, 1357|246, 135|247|6, 137|246|5, 1367|25|4, 136|257|4, 136|25|47, 136|25|4|7, 137|256|4, 13|257|46, 13|25|47|6, 137|26|45, 13|27|46|5, 147|236|5, 157|246|3, 15|247|36, 15|24|37|6, 17|246|35, 1|247|36|5, 17|26|35|4.
T(8,4) = 10: 1358|247|6, 1368|257|4, 136|258|47, 136|25|48|7, 138|257|46, 13|258|47|6, 138|27|46|5, 158|247|36, 15|248|37|6, 18|247|36|5.
T(9,5) = 4: 1369|258|47, 136|259|48|7, 139|258|47|6, 159|248|37|6.
T(10,6) = 1: 136(10)|259|48|7.
Triangle T(n,k) begins:
00 :      1;
01 :      1;
02 :      2;
03 :      4,     1;
04 :      9,     6;
05 :     25,    24,     3;
06 :     84,    91,    27,    1;
07 :    323,   374,   159,   21;
08 :   1377,  1699,   857,  197,   10;
09 :   6412,  8410,  4726, 1421,  174,   4;
10 :  32312, 44794, 27385, 9573, 1783, 127,  1;
		

Links

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

Crossrefs

Columns k=0-10 give: A270954, A270955, A270956, A270957, A270958, A270959, A270960, A270961, A270962, A270963, A270964.

Row sums give A000110.

T(2n,n) gives A270965.

Last terms of rows give A270967.

Cf. A000217, A056857, A083920, A185982.

Programs

Maple

b:= proc(n, i, m) option remember; expand(`if`(n=0, 1, add(
       b(n-1, j, max(m, j))*`if`(j=i-1, x, 1), j=1..m+1)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1, 0)):
seq(T(n), n=0..14);

Mathematica

b[n_, i_, m_] := b[n, i, m] = Expand[If[n == 0, 1, Sum[b[n - 1, j, Max[m, j]]*If[j == i - 1, x, 1], {j, 1, m + 1}]]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 1, 0]]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Dec 12 2016, after Alois P. Heinz *)

Formula

T(A000217(n+1),A000217(n)) = 1 for n>=0.

T(A000217(n+1)-1,A000217(n)-1) = 1+n for n>=1.

T(A000217(n+1)-2,A000217(n)-2) = A000217(1+n) for n>=2.