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

1, 1, 2, 6, 24, 120, 719, 5027, 40168, 361080, 3606480, 39623760, 474915803, 6166512899, 86227808578, 1291868401830, 20645144452320, 350547210173280, 6302294420371031, 119600213982762899, 2389140113204434900, 50111866901959213980, 1101140993932295832120

Offset

0,3

Comments

a(n) is the number of permutations of length n that avoid the consecutive pattern 123456 (or equivalently 654321).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..450 (terms n = 1..30 from Ray Chandler)

R. E. L. Aldred, M. D. Atkinson, D. J. McCaughan, Avoiding consecutive patterns in permutations Adv. in Appl. Math., 45(3), 449-461, 2010.

A. Baxter, B. Nakamura, and D. Zeilberger, Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes

Ira M. Gessel, Yan Zhuang, Counting permutations by alternating descents , arXiv:1408.1886 [math.CO], 2014. See displayed equation before Eq. (3), and set m=6. - N. J. A. Sloane, Aug 11 2014

Mingjia Yang, Doron Zeilberger, Increasing Consecutive Patterns in Words, arXiv:1805.06077 [math.CO], 2018.

Formula

a(n)/n! ~ 1.005827831279392186... * (1/r)^n, where r = 1.0011988273240623031887... is the root of the equation Sum_{n>=0} (r^(6*n)/(6*n)! - r^(6*n+1)/(6*n+1)!) = 0. - Vaclav Kotesovec, Dec 11 2013

Equivalently, a(n)/n! ~ c * (1/r)^n, where r = 1.00119882732406230318870210972855430833421618931012450844128... is the root of the equation 2 + exp(r/2) * (3 + exp(r)) * cos(sqrt(3)*r/2) = 2 * sqrt(3) * exp(r) * cosh(r/2) * sin(sqrt(3)*r/2), c = sqrt(3) / (2 * r * cosh(r/2) * sin(sqrt(3)*r/2)) = 1.0058278312793921866941324506580803251270892126827302878865925027445... . - Vaclav Kotesovec, Aug 23 2014

E.g.f. (Aldred, Atkinson, McCaughan, 2010): 3/(exp(x/2) * cos(x*sqrt(3)/2+Pi/3) + sqrt(3) * exp(-x/2) * cos(x*sqrt(3)/2+Pi/6) + exp(-x)). - Vaclav Kotesovec, Aug 23 2014

Maple

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t<4, add(b(u+j-1, o-j, t+1), j=1..o), 0)+
      add(b(u-j, o+j-1, 0), j=1..u))
    end:
a:= n-> b(n, 0, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 07 2013

Mathematica

Table[n!*SeriesCoefficient[1/(Sum[x^(6*k)/(6*k)!-x^(6*k+1)/(6*k+1)!, {k, 0, n}]), {x, 0, n}], {n, 1, 20}] (* Vaclav Kotesovec, Dec 11 2013 *)
Rest[CoefficientList[Series[3/(E^(x/2) * Cos[x*Sqrt[3]/2+Pi/3] + Sqrt[3] * E^(-x/2) * Cos[x*Sqrt[3]/2+Pi/6] + E^(-x)), {x, 0, 20}], x] * Range[0, 20]!] (* Vaclav Kotesovec, Aug 23 2014 *)

Crossrefs

Cf. A049774, A117158, A177523.

Column k=31 of A242784.

Sequence in context: A047890 A297204 A071088 * A370384 A122417 A321008

Adjacent sequences: A177530 A177531 A177532 * A177534 A177535 A177536

Keyword

nonn

Author

R. H. Hardin, May 10 2010

Extensions

More terms from Ray Chandler, Dec 06 2011

Minor edits by Vaclav Kotesovec, Aug 29 2014

a(0)=1 prepended by Alois P. Heinz, Aug 08 2018

Status

approved