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

1, 1, 2, 6, 24, 120, 720, 4871, 37616, 326376, 3161321, 33647702, 391315387, 4925158550, 66783060318, 969759198692, 15025115932355, 247300462549813, 4310409307848931, 79296721491391389, 1535659536831254219, 31225145160777718876, 665165555262983848987

Offset

0,3

Links

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

Formula

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

Maple

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

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[t > 6, 0, If[u + o + t < 7, (u + o)!,
     Sum[b[u - j, o + j - 1, {1, 3, 1, 3, 6, 1}[[t]]], {j, 1, u}] +
     Sum[b[u + j - 1, o - j, {2, 2, 4, 5, 2, 7}[[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=45 of A242784.

Sequence in context: A147738 A147737 A177539 * A177544 A177540 A068201

Adjacent sequences: A177543 A177544 A177545 * A177547 A177548 A177549

Keyword

nonn

Author

R. H. Hardin, May 10 2010

Extensions

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

Status

approved