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

1, 1, 2, 6, 24, 104, 528, 3296, 23168, 179712, 1573632, 15207424, 158880768, 1801996288, 22088716288, 289379395584, 4040899657728, 60045059489792, 944460646318080, 15670973219667968, 273813250221277184, 5024207327266603008, 96554813072964845568

Offset: 0

Author

R. H. Hardin, May 10 2010

Keywords

• nonn

Links

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

Crossrefs

Column k=0 of A230797.

Column k=10 of A242784.

Programs

Maple

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      add(b(u+j-1, o-j, `if`(t=2, 3, 1)), j=1..o) +`if`(t<3,
      add(b(u-j, o+j-1, `if`(t=1, 2, 0)), j=1..u), 0))
    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,
     Sum[b[u + j - 1, o - j, If[t == 2, 3, 1]], {j, 1, o}] + If[t < 3,
     Sum[b[u - j, o + j - 1, If[t == 1, 2, 0]], {j, 1, u}], 0]];
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.87361286073825385348141673848..., c = 1.678751353034864037734331900009... . - Vaclav Kotesovec, Aug 28 2014

Extensions

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