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

Links

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

Formula

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

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

Crossrefs

Column k=0 of A230695.

Column k=9 of A242784.

Sequence in context: A338987 A174076 A230695 * A214762 A141254 A366706

Adjacent sequences: A177516 A177517 A177518 * A177520 A177521 A177522

Keyword

nonn

Author

R. H. Hardin, May 10 2010

Extensions

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

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

Status

approved