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

Links

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

Wikipedia, Partition of a set

Example

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;

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

Crossrefs

Column k=0 gives A271207.

Row sums give A000110.

Cf. A185982.

Sequence in context: A373756 A102405 A363575 * A211244 A228337 A114506

Adjacent sequences: A271203 A271204 A271205 * A271207 A271208 A271209

Keyword

nonn,tabf

Author

Alois P. Heinz, Apr 01 2016

Status

approved