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

1, 1, 2, 6, 24, 114, 648, 4284, 32256, 273616, 2578352, 26725776, 302273664, 3703441104, 48865510848, 690823736064, 10417318281216, 166907223390976, 2831507368842752, 50703852290781696, 955742450175919104, 18916030525704006144, 392213482250102734848

Offset

0,3

Links

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

Formula

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

Maple

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      add(b(u+j-1, o-j, `if`(t in [0, 3], 1, 2)), j=1..o)+`if`(t<3,
      add(b(u-j, o+j-1, `if`(t=2, 3, 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[MemberQ[{0, 3}, t], 1, 2]], {j, 1, o}] + If[t<3,
     Sum[b[u-j, o+j-1, If[t == 2, 3, 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=12 of A242784.

Sequence in context: A068199 A189846 A189283 * A216717 A174072 A224255

Adjacent sequences: A177519 A177520 A177521 * A177523 A177524 A177525

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