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

1, 1, 2, 6, 24, 111, 612, 3906, 28701, 236527, 2167862, 21824925, 239861934, 2854894485, 36602472117, 502718236303, 7365503262033, 114653301213668, 1889769527067410, 32877891905367530, 602116339324675145, 11578253045158664158, 233244225298760907868

Offset

0,3

Links

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

Formula

a(n) ~ c * d^n * n!, where d = 0.91568163084580807076940792182223499091165..., c = 1.44100339681864767911275854344010332196608... . - 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, `if`(t=2, 3, 1)), j=1..o), 0)+
      add(b(u-j, o+j-1, `if`(irem(t, 2)=0, 0, 2)), 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, If[t == 2, 3, 1]], {j, 1, o}] , 0] +
     Sum[b[u - j, o + j - 1, If[EvenQ[t], 0, 2]], {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

Columns k=11,13 of A242784.

Sequence in context: A342284 A174195 A274378 * A152322 A308726 A168490

Adjacent sequences: A177518 A177519 A177520 * A177522 A177523 A177524

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