A231210 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of some of the consecutive patterns 123, 1432, 2431, 3421; triangle T(n,k), n>=0, 0<=k<=max(0,n-2), read by rows.

1, 1, 2, 5, 1, 14, 9, 1, 46, 59, 14, 1, 177, 358, 164, 20, 1, 790, 2235, 1589, 398, 27, 1, 4024, 14658, 15034, 5659, 909, 35, 1, 23056, 103270, 139465, 77148, 17875, 2021, 44, 1, 146777, 778451, 1334945, 970679, 341071, 52380, 4442, 54, 1, 1027850, 6315499

Offset: 0

Author

Alois P. Heinz, Nov 05 2013

Keywords

• nonn
• tabf

Examples

			T(3,1) = 1: 123.
T(4,0) = 14: 1324, 1423, 2143, 2314, 2413, 3142, 3214, 3241, 3412, 4132, 4213, 4231, 4312, 4321.
T(4,1) = 9: 1243, 1342, 1432, 2134, 2341, 2431, 3124, 3421, 4123.
T(4,2) = 1: 1234.
T(5,2) = 14: 12354, 12453, 12543, 13452, 13542, 14532, 21345, 23451, 23541, 24531, 31245, 34521, 41235, 51234.
T(5,3) = 1: 12345.
Triangle T(n,k) begins:
:  0 :      1;
:  1 :      1;
:  2 :      2;
:  3 :      5,      1;
:  4 :     14,      9,       1;
:  5 :     46,     59,      14,      1;
:  6 :    177,    358,     164,     20,      1;
:  7 :    790,   2235,    1589,    398,     27,     1;
:  8 :   4024,  14658,   15034,   5659,    909,    35,    1;
:  9 :  23056, 103270,  139465,  77148,  17875,  2021,   44,  1;
: 10 : 146777, 778451, 1334945, 970679, 341071, 52380, 4442, 54, 1;
		

Links

• Alois P. Heinz, Rows n = 0..142, flattened
• A. Baxter, B. Nakamura, and D. Zeilberger, Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes
• S. Kitaev and T. Mansour, On multi-avoidance of generalized patterns

Crossrefs

Columns k=0-2 give: A231211, A231228, A228422.

Row sums give: A000142.

Cf. A049774, A177479.

Programs

Maple

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

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Expand[ Sum[b[u+j-1, o-j, {2, 2, 2}[[t]]]*If[t == 2, x, 1], {j, 1, o}] + Sum[b[u-j, o+j-1, {1, 3, 1}[[t]]]*If[t == 3, x, 1], {j, 1, u}]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0, 1]]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Feb 11 2015, after Alois P. Heinz *)