A177529 Number of permutations of {1,...,n} avoiding adjacent step pattern up, down, up, down, up.

1, 1, 2, 6, 24, 120, 659, 4186, 31457, 264834, 2465550, 25334981, 283322383, 3430384284, 44803783445, 626719448981, 9347396890481, 148174002240074, 2486833885400060, 44052337160572208, 821495697573151302, 16085109561896603059, 329939476998354570978

Offset: 0

Author

R. H. Hardin, May 10 2010

Keywords

• nonn

Links

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

Crossrefs

Column k=21 of A242784.

Programs

Maple

b:= proc(u, o, t) option remember; `if`(t>5, 0, `if`(u+o+t<6, (u+o)!,
      add(b(u-j, o+j-1, [1, 3, 1, 5, 1][t]), j=1..u)+
      add(b(u+j-1, o-j, [2, 2, 4, 2, 6][t]), j=1..o)))
    end:
a:= n-> `if`(n=0, 1, add(b(j-1, n-j, 1), j=1..n)):
seq(a(n), n=0..25);  # Alois P. Heinz, Oct 21 2013

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[t > 5, 0, If[u + o + t < 6, (u + o)!,
     Sum[b[u - j, o + j - 1, {1, 3, 1, 5, 1}[[t]]], {j, 1, u}] +
     Sum[b[u + j - 1, o - j, {2, 2, 4, 2, 6}[[t]]], {j, 1, o}]]];
a[n_] := b[n, 0, 1];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Apr 19 2022, after Alois P. Heinz *)

Formula

a(n) ~ c * d^n * n!, where d = 0.9323832531422843725281328190771918152..., c = 1.369593476632786981162993013559816... . - Vaclav Kotesovec, Jan 17 2015