A260670 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the generalized pattern 23-1; triangle T(n,k), n>=0, 0<=k<=A125811(n)-1, read by rows.

1, 1, 2, 5, 1, 15, 6, 3, 52, 32, 23, 10, 3, 203, 171, 152, 98, 62, 22, 11, 1, 877, 944, 984, 791, 624, 392, 240, 111, 55, 18, 4, 4140, 5444, 6460, 6082, 5513, 4302, 3328, 2141, 1393, 780, 432, 187, 88, 24, 6, 21147, 32919, 43626, 46508, 46880, 41979, 36774

Offset: 0

Author

Alois P. Heinz, Nov 14 2015

Keywords

• nonn
• tabf

Comments

Patterns 1-32, 3-12, 21-3 give the same sequence.

Examples

			T(3,1) = 1: 231.
T(4,1) = 6: 1342, 2314, 2413, 2431, 3241, 4231.
T(4,2) = 3: 2341, 3412, 3421.
T(5,2) = 23: 13452, 14523, 14532, 23415, 23514, 23541, 24351, 25341, 32451, 34125, 34152, 34215, 35124, 35142, 35214, 35412, 35421, 42351, 43512, 43521, 52341, 53412, 53421.
T(5,3) = 10: 23451, 24513, 24531, 34251, 35241, 45123, 45132, 45213, 45312, 45321.
T(5,4) = 3: 34512, 34521, 45231.
Triangle T(n,k) begins:
0 :   1;
1 :   1;
2 :   2;
3 :   5,   1;
4 :  15,   6,   3;
5 :  52,  32,  23,  10,   3;
6 : 203, 171, 152,  98,  62,  22,  11,   1;
7 : 877, 944, 984, 791, 624, 392, 240, 111, 55, 18, 4;
		

Links

• Alois P. Heinz, Rows n = 0..50, flattened
• A. Claesson and T. Mansour, Counting occurrences of a pattern of type (1,2) or (2,1) in permutations, arXiv:math/0110036 [math.CO], 2001

Crossrefs

Columns k=0-10 give: A000110, A264460, A264461, A264462, A264463, A264464, A264465, A264466, A264467, A264468, A264469.

Row sums give A000142.

Cf. A001754, A125811, A260665, A263776.

Programs

Maple

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

Mathematica

b[u_, o_] := b[u, o] = If[u+o == 0, 1, Sum[b[u-j, o+j-1], {j, 1, u}] + Sum[Expand[b[u+j-1, o-j]*x^u], {j, 1, o}]]; T[n_] := Function[p, Table[ Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0]]; Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 16 2017, after Alois P. Heinz *)

Formula

Sum_{k>0} k * T(n,k) = A001754(n).