login
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.
13

%I #23 Jul 19 2017 10:48:16

%S 1,1,2,5,1,15,6,3,52,32,23,10,3,203,171,152,98,62,22,11,1,877,944,984,

%T 791,624,392,240,111,55,18,4,4140,5444,6460,6082,5513,4302,3328,2141,

%U 1393,780,432,187,88,24,6,21147,32919,43626,46508,46880,41979,36774

%N 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.

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

%H Alois P. Heinz, <a href="/A260670/b260670.txt">Rows n = 0..50, flattened</a>

%H A. Claesson and T. Mansour, <a href="https://arxiv.org/abs/math/0110036">Counting occurrences of a pattern of type (1,2) or (2,1) in permutations</a>, arXiv:math/0110036 [math.CO], 2001

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

%e T(3,1) = 1: 231.

%e T(4,1) = 6: 1342, 2314, 2413, 2431, 3241, 4231.

%e T(4,2) = 3: 2341, 3412, 3421.

%e 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.

%e T(5,3) = 10: 23451, 24513, 24531, 34251, 35241, 45123, 45132, 45213, 45312, 45321.

%e T(5,4) = 3: 34512, 34521, 45231.

%e Triangle T(n,k) begins:

%e 0 : 1;

%e 1 : 1;

%e 2 : 2;

%e 3 : 5, 1;

%e 4 : 15, 6, 3;

%e 5 : 52, 32, 23, 10, 3;

%e 6 : 203, 171, 152, 98, 62, 22, 11, 1;

%e 7 : 877, 944, 984, 791, 624, 392, 240, 111, 55, 18, 4;

%p b:= proc(u, o) option remember;

%p `if`(u+o=0, 1, add(b(u-j, o+j-1), j=1..u)+

%p add(expand(b(u+j-1, o-j)*x^u), j=1..o))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n,0)):

%p seq(T(n), n=0..10);

%t 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_ *)

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

%Y Row sums give A000142.

%Y Cf. A001754, A125811, A260665, A263776.

%K nonn,tabf

%O 0,3

%A _Alois P. Heinz_, Nov 14 2015