A177519 Number of permutations of 1..n avoiding adjacent step pattern up, down, down, up.

1, 1, 2, 6, 24, 109, 588, 3654, 26125, 209863, 1876502, 18441367, 197776850, 2297242583, 28739304385, 385195455471, 5507210188401, 83657067537498, 1345556172013026, 22844387886649418, 408258252653717337, 7660885499702743124, 150600621665021781932

Offset: 0

Author

R. H. Hardin, May 10 2010

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..458

Crossrefs

Column k=0 of A230695.

Column k=9 of A242784.

Programs

Maple

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t<3, add(b(u+j-1, o-j, 1), j=1..o), 0)+
      add(b(u-j, o+j-1, `if`(t in [0,3], 0, t+1)), j=1..u))
    end:
a:= n-> b(n, 0, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 07 2013

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, If[t < 3,
     Sum[b[u + j - 1, o - j, 1], {j, 1, o}], 0] +
     Sum[b[u - j, o + j - 1, If[MemberQ[{0, 3}, t], 0, t+1]], {j, 1, u}]];
a[n_] := b[n, 0, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Apr 20 2022, after Alois P. Heinz *)

Formula

a(n) ~ c * d^n * n!, where d = 0.89356257576899599804435763285311831354458355576519..., c = 1.593348415562339201282264582915828860634166516332738... . - Vaclav Kotesovec, Aug 29 2014

Extensions

a(17)-a(22) from Alois P. Heinz, Oct 07 2013

a(0)=1 from Alois P. Heinz, Apr 20 2022