A177479 -id:A177479 - cp's OEIS frontend

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

Alois P. Heinz, Nov 05 2013

			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;

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

Columns k=0-2 give: A231211, A231228, A228422.
Row sums give: A000142.
Cf. A049774, A177479.

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

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

A231211 Number of permutations of [n] avoiding simultaneously consecutive patterns 123, 1432, 2431, and 3421.

Original entry on oeis.org

1, 1, 2, 5, 14, 46, 177, 790, 4024, 23056, 146777, 1027850, 7852184, 64985116, 579191277, 5530869310, 56336971744, 609708912976, 6986749484177, 84510154473170, 1076016705993704, 14385283719409636, 201475033030143477, 2950048762311387430, 45073424916825354064

Offset: 0

Alois P. Heinz, Nov 05 2013

nonn

Number of permutations of [n] avoiding simultaneously consecutive step patterns up, up and up, down, down.

			a(3) = 5: 132, 213, 231, 312, 321.
a(4) = 14: 1324, 1423, 2143, 2314, 2413, 3142, 3214, 3241, 3412, 4132, 4213, 4231, 4312, 4321.
a(5) = 46: 13254, 14253, 14352, ..., 54231, 54312, 54321.
a(6) = 177: 132546, 132645, 142536, ..., 654231, 654312, 654321.

Alois P. Heinz, Table of n, a(n) for n = 0..250
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

Column k=0 of A231210.

Cf. A049774, A177479.

b:= proc(u, o, t) option remember; `if`(t=4, 0, `if`(u+o=0, 1,
      add(b(u+j-1, o-j, [2, 4, 2][t]), j=1..o)+
      add(b(u-j, o+j-1, [1, 3, 4][t]), j=1..u)))
    end:
a:= n-> b(n, 0, 1):
seq(a(n), n=0..30);
# second Maple program
n:=40: c[0,0]:=1: for i to n-1 do c[i,0]:=0 end do: for i to n-1 do for j to i do c[i,j] := c[i,j-1] + c[i-1,i-j] + 1 end do end do: 1, seq(c[k, k]/2, k=1..n-1); # Sergei N. Gladkovskii, Jul 27 2015

b[u_, o_, t_] := b[u, o, t] = If[t == 4, 0, If[u + o == 0, 1,
    Sum[b[u + j - 1, o - j, {2, 4, 2}[[t]]], {j, 1, o}] +
    Sum[b[u - j, o + j - 1, {1, 3, 4}[[t]]], {j, 1, u}]]];
a[n_] := b[n, 0, 1];
a /@ Range[0, 30] (* Jean-François Alcover, Dec 22 2020, after Alois P. Heinz *)

a(n) ~ (1+exp(Pi/2)) * (2/Pi)^(n+1) * n!. - Vaclav Kotesovec, Aug 28 2014

cp's OEIS Frontend

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica