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

Author

R. H. Hardin, May 10 2010

Keywords

• nonn

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.

Crossrefs

Cf. A049774, A117158, A177523.

Column k=31 of A242784.

Programs

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

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

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