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

Links

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

Formula

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

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

Crossrefs

Column k=21 of A242784.

Sequence in context: A152346 A152336 A152343 * A138619 A372545 A189841

Adjacent sequences: A177526 A177527 A177528 * A177530 A177531 A177532

Keyword

nonn

Author

R. H. Hardin, May 10 2010

Status

approved