A271206 Number T(n,k) of set partitions of [n] having exactly k triples (t,t+1,t+2) such that t+i is in block b+i for some b; triangle T(n,k), n>=0, 0<=k<=max(0,n-2), read by rows.

1, 1, 2, 4, 1, 10, 4, 1, 28, 18, 5, 1, 89, 77, 30, 6, 1, 315, 345, 164, 45, 7, 1, 1233, 1617, 919, 299, 63, 8, 1, 5285, 8003, 5262, 2011, 492, 84, 9, 1, 24583, 41871, 31180, 13611, 3857, 754, 108, 10, 1, 123062, 231474, 191889, 94020, 30128, 6755, 1095, 135, 11, 1

Offset: 0

Author

Alois P. Heinz, Apr 01 2016

Keywords

• nonn
• tabf

Examples

			T(3,1) = 1: 1|2|3.
T(4,1) = 4: 12|3|4, 14|2|3, 1|24|3, 1|2|34.
T(5,1) = 18: 123|4|5, 125|3|4, 12|35|4, 12|3|45, 13|24|5, 1|23|4|5, 145|2|3, 14|25|3, 14|2|35, 14|2|3|5, 15|24|3, 1|245|3, 1|24|35, 1|24|3|5, 15|2|34, 1|25|34, 1|2|345, 1|2|34|5.
T(5,2) = 5: 12|3|4|5, 15|2|3|4, 1|25|3|4, 1|2|35|4, 1|2|3|45.
T(5,3) = 1: 1|2|3|4|5.
Triangle T(n,k) begins:
:  0 :     1;
:  1 :     1;
:  2 :     2;
:  3 :     4,     1;
:  4 :    10,     4,     1;
:  5 :    28,    18,     5,     1;
:  6 :    89,    77,    30,     6,    1;
:  7 :   315,   345,   164,    45,    7,   1;
:  8 :  1233,  1617,   919,   299,   63,   8,   1;
:  9 :  5285,  8003,  5262,  2011,  492,  84,   9,  1;
: 10 : 24583, 41871, 31180, 13611, 3857, 754, 108, 10, 1;
		

Links

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

Crossrefs

Column k=0 gives A271207.

Row sums give A000110.

Cf. A185982.

Programs

Maple

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

Mathematica

b[n_, i_, t_, m_] := b[n, i, t, m] = Expand[If[n==0, 1, Sum[Function[v, If[t && v, x, 1]*b[n-1, j, v, Max[m, j]]][j==i+1], {j, 1, m+1}]]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 1, False, 0]]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Feb 05 2017, translated from Maple *)