login
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.
14
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,3
COMMENTS
Patterns 1-23, 3-21, 32-1 give the same triangle.
LINKS
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
FORMULA
Sum_{k>0} k * T(n,k) = A001754(n).
EXAMPLE
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;
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 *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Alois P. Heinz, Nov 14 2015
STATUS
approved