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

Comments

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

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

Formula

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

Example

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.

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

Crossrefs

Column k=0 of A231210.

Cf. A049774, A177479.

Sequence in context: A275424 A328429 A107268 * A006216 A148337 A149899

Adjacent sequences: A231208 A231209 A231210 * A231212 A231213 A231214

Keyword

nonn

Author

Alois P. Heinz, Nov 05 2013

Status

approved