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

1, 1, 2, 6, 24, 119, 709, 4928, 39144, 349776, 3472811, 37928331, 451891992, 5832672456, 81074690424, 1207441809209, 19181203110129, 323753459184738, 5785975294622694, 109149016813544376, 2167402030585724571, 45190632809497874161, 987099099863360190632

Offset

0,3

Comments

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

Links

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

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 , 2014. See displayed equation before Eq. (3), and set m=5. - N. J. A. Sloane, Aug 11 2014

Kaarel Hänni, Asymptotics of descent functions, arXiv:2011.14360 [math.CO], Nov 29 2020, p. 14.

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

Mingjia Yang, An experimental walk in patterns, partitions, and words, Ph. D. Dissertation, Rutgers University (2020).

Formula

E.g.f.: 1/( Sum_{n>=0} x^(5*n)/(5*n)! - x^(5*n+1)/(5*n+1)! ).

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

Equivalently, r = 1.00718754778601539541899865400272701484... is the root of the equation (5+sqrt(5)) * cos(sqrt((5-sqrt(5))/2)*r/2) + (5-sqrt(5)) * exp(sqrt(5)*r/2) * cos(sqrt((5+sqrt(5))/2)*r/2) - sqrt(2*(5-sqrt(5))) * sin(sqrt((5-sqrt(5))/2)*r/2) - sqrt(2*(5+sqrt(5))) * exp(sqrt(5)*r/2) * sin(sqrt((5+sqrt(5))/2)*r/2) = 0. - Vaclav Kotesovec, Aug 29 2014

E.g.f.: 10*exp((1+sqrt(5))*x/4) / ((5+sqrt(5)) * cos(sqrt((5-sqrt(5))/2)*x/2) + (5-sqrt(5)) * exp(sqrt(5)*x/2) * cos(sqrt((5+sqrt(5))/2)*x/2) - sqrt(2*(5-sqrt(5))) * sin(sqrt((5-sqrt(5))/2)*x/2) - sqrt(2*(5+sqrt(5))) * exp(sqrt(5)*x/2) * sin(sqrt((5+sqrt(5))/2)*x/2)). - Vaclav Kotesovec, Aug 29 2014

In closed form, c = 5*exp((1+sqrt(5))*r/4) / (r*((5 + sqrt(5)) * cos(sqrt((5 - sqrt(5))/2)*r/2) + (5 - sqrt(5)) * exp(sqrt(5)*r/2) * cos(sqrt((5 + sqrt(5))/2)*r/2))) = 1.0280679375675015201596831656779442465978511664638... . Vaclav Kotesovec, Feb 01 2015

Example

E.g.f.: A(x) = 1 + x + 2*x^2/2! + 6*x^3/3! + 24*x^4/4! + 119*x^5/5! + 709*x^6/6! +...
where A(x) = 1/(1 - x + x^5/5! - x^6/6! + x^10/10! - x^11/11! + x^15/15! - x^16/16! + x^20/20! +...).

Mathematica

Table[n!*SeriesCoefficient[1/(Sum[x^(5*k)/(5*k)!-x^(5*k+1)/(5*k+1)!, {k, 0, n}]), {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Dec 11 2013 *)
FullSimplify[CoefficientList[Series[10*E^((1+Sqrt[5])*x/4) / ((5+Sqrt[5]) * Cos[Sqrt[(5-Sqrt[5])/2]*x/2] + (5-Sqrt[5]) * E^(Sqrt[5]*x/2) * Cos[Sqrt[(5+Sqrt[5])/2]*x/2] - Sqrt[2*(5-Sqrt[5])] * Sin[Sqrt[(5-Sqrt[5])/2]*x/2] - Sqrt[2*(5+Sqrt[5])] * E^(Sqrt[5]*x/2) * Sin[Sqrt[(5+Sqrt[5])/2]*x/2]), {x, 0, 20}], x]*Range[0, 20]!] (* Vaclav Kotesovec, Aug 29 2014 *)

Prog

(PARI) {a(n)=n!*polcoeff(1/sum(m=0, n\5+1, x^(5*m)/(5*m)!-x^(5*m+1)/(5*m+1)!+x^2*O(x^n)), n)}

Crossrefs

Cf. A080635, A049774, A117158, A177533.

Column k=15 of A242784.

Sequence in context: A202233 A202235 A202236 * A005395 A370383 A357920

Adjacent sequences: A177520 A177521 A177522 * A177524 A177525 A177526

Keyword

nonn

Author

R. H. Hardin, May 10 2010

Extensions

More terms from Ray Chandler, Dec 06 2011

a(0)=1 prepended by Alois P. Heinz, Jan 13 2015

Status

approved