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

Links

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

Formula

a(n) ~ c * d^n * n!, where d = 0.87361286073825385348141673848..., c = 1.678751353034864037734331900009... . - Vaclav Kotesovec, Aug 28 2014

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

Crossrefs

Column k=0 of A230797.

Column k=10 of A242784.

Sequence in context: A376585 A128652 A152316 * A152326 A152330 A152319

Adjacent sequences: A177517 A177518 A177519 * A177521 A177522 A177523

Keyword

nonn

Author

R. H. Hardin, May 10 2010

Extensions

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

Status

approved