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

%I #46 Aug 08 2018 17:54:11

%S 1,1,2,6,24,120,719,5027,40168,361080,3606480,39623760,474915803,

%T 6166512899,86227808578,1291868401830,20645144452320,350547210173280,

%U 6302294420371031,119600213982762899,2389140113204434900,50111866901959213980,1101140993932295832120

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

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

%H Alois P. Heinz, <a href="/A177533/b177533.txt">Table of n, a(n) for n = 0..450</a> (terms n = 1..30 from Ray Chandler)

%H R. E. L. Aldred, M. D. Atkinson, D. J. McCaughan, <a href="https://doi.org/10.1016/j.aam.2010.03.005">Avoiding consecutive patterns in permutations</a> Adv. in Appl. Math., 45(3), 449-461, 2010.

%H A. Baxter, B. Nakamura, and D. Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/auto.html">Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes</a>

%H Ira M. Gessel, Yan Zhuang, <a href="http://arxiv.org/abs/1408.1886">Counting permutations by alternating descents </a>, arXiv:1408.1886 [math.CO], 2014. See displayed equation before Eq. (3), and set m=6. - _N. J. A. Sloane_, Aug 11 2014

%H Mingjia Yang, Doron Zeilberger, <a href="https://arxiv.org/abs/1805.06077">Increasing Consecutive Patterns in Words</a>, arXiv:1805.06077 [math.CO], 2018.

%F 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

%F 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

%F 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

%p b:= proc(u, o, t) option remember; `if`(u+o=0, 1,

%p `if`(t<4, add(b(u+j-1, o-j, t+1), j=1..o), 0)+

%p add(b(u-j, o+j-1, 0), j=1..u))

%p end:

%p a:= n-> b(n, 0, 0):

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Oct 07 2013

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

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

%Y Cf. A049774, A117158, A177523.

%Y Column k=31 of A242784.

%K nonn

%O 0,3

%A _R. H. Hardin_, May 10 2010

%E More terms from _Ray Chandler_, Dec 06 2011

%E Minor edits by _Vaclav Kotesovec_, Aug 29 2014

%E a(0)=1 prepended by _Alois P. Heinz_, Aug 08 2018