A260665 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the generalized pattern 12-3; triangle T(n,k), n>=0, 0<=k<=(n-1)*(n-2)/2-[n=0], read by rows.

1, 1, 2, 5, 1, 15, 7, 1, 1, 52, 39, 13, 12, 2, 1, 1, 203, 211, 112, 103, 41, 24, 17, 5, 2, 1, 1, 877, 1168, 843, 811, 492, 337, 238, 122, 68, 39, 28, 8, 5, 2, 1, 1, 4140, 6728, 6089, 6273, 4851, 3798, 2956, 1960, 1303, 859, 594, 314, 204, 110, 64, 43, 17, 8, 5, 2, 1, 1

Offset: 0

Author

Alois P. Heinz, Nov 14 2015

Keywords

• nonn
• tabf

Comments

Patterns 1-23, 3-21, 32-1 give the same triangle.

Examples

			T(4,1) = 7: 1324, 1342, 2134, 2314, 2341, 3124, 4123.
T(4,2) = 1: 1243.
T(4,3) = 1: 1234.
T(5,3) = 12: 12534, 12543, 13245, 13425, 13452, 21345, 23145, 23415, 23451, 31245, 41235, 51234.
T(5,4) = 2: 12435, 12453.
T(5,5) = 1: 12354.
T(5,6) = 1: 12345.
Triangle T(n,k) begins:
0 :   1;
1 :   1;
2 :   2;
3 :   5,    1;
4 :  15,    7,   1,   1;
5 :  52,   39,  13,  12,   2,   1,   1;
6 : 203,  211, 112, 103,  41,  24,  17,   5,  2,  1,  1;
7 : 877, 1168, 843, 811, 492, 337, 238, 122, 68, 39, 28, 8, 5, 2, 1, 1;
		

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, A092923, A264451, A264452, A264453, A264454, A264455, A264456, A264457, A264458, A264459.

Row sums give A000142.

Cf. A000217, A001754, A260670, 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^(o-j)), 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^(o - j)], {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, Jul 10 2017, after Alois P. Heinz *)

Formula

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