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

%I #19 Dec 12 2016 02:40:15

%S 1,1,2,4,1,9,6,25,24,3,84,91,27,1,323,374,159,21,1377,1699,857,197,10,

%T 6412,8410,4726,1421,174,4,32312,44794,27385,9573,1783,127,1,174941,

%U 254718,167097,64724,15158,1856,76,1011357,1538027,1071422,449567,121464,20074,1650,36

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

%H Alois P. Heinz, <a href="/A270953/b270953.txt">Rows n = 0..120, flattened</a>

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

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

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

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

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

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

%e T(5,2) = 3: 135|24, 13|25|4, 15|24|3.

%e T(6,3) = 1: 136|25|4.

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

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

%e T(9,5) = 4: 1369|258|47, 136|259|48|7, 139|258|47|6, 159|248|37|6.

%e T(10,6) = 1: 136(10)|259|48|7.

%e Triangle T(n,k) begins:

%e 00 : 1;

%e 01 : 1;

%e 02 : 2;

%e 03 : 4, 1;

%e 04 : 9, 6;

%e 05 : 25, 24, 3;

%e 06 : 84, 91, 27, 1;

%e 07 : 323, 374, 159, 21;

%e 08 : 1377, 1699, 857, 197, 10;

%e 09 : 6412, 8410, 4726, 1421, 174, 4;

%e 10 : 32312, 44794, 27385, 9573, 1783, 127, 1;

%p b:= proc(n, i, m) option remember; expand(`if`(n=0, 1, add(

%p b(n-1, j, max(m, j))*`if`(j=i-1, x, 1), j=1..m+1)))

%p end:

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

%p seq(T(n), n=0..14);

%t 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_ *)

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

%Y Row sums give A000110.

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

%Y Last terms of rows give A270967.

%Y Cf. A000217, A056857, A083920, A185982.

%K nonn,tabf

%O 0,3

%A _Alois P. Heinz_, Mar 26 2016