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
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Nov 05 2013
STATUS
approved