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,3

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

Example

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;

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 *)

Crossrefs

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

Row sums give: A000142.

Cf. A049774, A177479.

Sequence in context: A101282 A263776 A145879 * A178978 A101895 A260670

Adjacent sequences: A231207 A231208 A231209 * A231211 A231212 A231213

Keyword

nonn,tabf

Author

Alois P. Heinz, Nov 05 2013

Status

approved