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

Links

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

Wikipedia, Partition of a set

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.

Example

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;

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

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.

Sequence in context: A116424 A135306 A242352 * A240717 A166900 A192437

Adjacent sequences: A270950 A270951 A270952 * A270954 A270955 A270956

Keyword

nonn,tabf

Author

Alois P. Heinz, Mar 26 2016

Status

approved