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

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

Author

Alois P. Heinz, Nov 05 2013

Keywords

• nonn

Comments

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

Examples

			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.
		

Links

• 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

Crossrefs

Column k=0 of A231210.

Cf. A049774, A177479.

Programs

Maple

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

Mathematica

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

Formula

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