login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A049774 Number of permutations of n elements not containing the consecutive pattern 123. 25
1, 1, 2, 5, 17, 70, 349, 2017, 13358, 99377, 822041, 7477162, 74207209, 797771521, 9236662346, 114579019469, 1516103040833, 21314681315998, 317288088082405, 4985505271920097, 82459612672301846, 1432064398910663705, 26054771465540507273, 495583804405888997218 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Permutations on n letters without double falls. A permutation w has a double fall at k if w(k) > w(k+1) > w(k+2) and has an initial fall if w(1) > w(2).

Hankel transform is A055209. - Paul Barry, Jan 12 2009

Increasing colored 1-2 trees of order n with choice of two colors for the right branches of the vertices of out degree 2 except those vertices on the path from the root to the leftmost leave. - Wenjin Woan, May 21 2011

REFERENCES

F. N. David and D. E. Barton, Combinatorial Chance, Hafner, New York, 1962, pages 156-157.

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983,(5.2.17).

LINKS

Ray Chandler, Table of n, a(n) for n = 0..200

Martin Aigner, Catalan and other numbers: a recurrent theme, in Algebraic Combinatorics and Computer Science, a Tribute to Gian-Carlo Rota, pp.347-390, Springer, 2001.

P. Barry, Constructing Exponential Riordan Arrays from Their A and Z Sequences, Journal of Integer Sequences, 17 (2014), #14.2.6.

Nicolas Basset, Counting and generating permutations using timed languages, HAL Id: hal-00820373, 2013.

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

S. Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns arXiv:math/0505254v1 [math.CO].

S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-123.

Ira M. Gessel, Yan Zhuang, Counting permutations by alternating descents , 2014. See Eq. (3). - N. J. A. Sloane, Aug 11 2014

FORMULA

E.g.f.: 1/sum(i>=0, x^(3*i)/(3*i)! - x^(3*i+1)/(3*i+1)! ).

Equivalently, e.g.f.: exp(x/2) * r / sin(r*x + (2/3)*Pi) where r = sqrt(3)/2. This has simple poles at (3*m+1)*x0 where x0 = Pi/sqrt(6.75) = 1.2092 approximately and m is an arbitrary integer. This yields the asymptotic expansion a(n)/n! ~ x0^(-n-1) * sum((-1)^m * E^(3*m+1) / (3*m+1)^(n+1)) where E = exp(x0/2) = 1.8305+ and m ranges over all integers. - Noam D. Elkies, Nov 15 2001

E.g.f.: sqrt(3)*exp(x/2)/(sqrt(3)*cos(x*sqrt(3)/2) - sin(x*sqrt(3)/2) ); a(n+1) = sum(k=0..n, binomial(n, k)*a(k)*b(n-k) ) where b(n) = number of n-permutations without double falls and without initial falls. - Emanuele Munarini, Feb 28 2003

O.g.f.: A(x) = 1/(1-x-x^2/(1-2*x-4*x^2/(1-3*x-9*x^2/(1-... -n*x-n^2*x^2/(1- ...))))) (continued fraction). - Paul D. Hanna, Jan 17 2006

a(n) = leftmost column term of M^n*V, where M = an infinite tridiagonal matrix with (1,2,3,...) in the super, sub, and main diagonals and the rest zeros. V = the vector [1,0,0,0,...]. - Gary W. Adamson, Jun 16 2011

E.g.f.: A(x)=1/Q(0); Q(k)=1-x/((3*k+1)-(x^2)*(3*k+1)/((x^2)-3*(3*k+2)*(k+1)/Q(k+1))) ; (continued fraction). - Sergei N. Gladkovskii, Nov 25 2011

a(n) ~ n! * exp(Pi/(3*sqrt(3))) * (3*sqrt(3)/(2*Pi))^(n+1). - Vaclav Kotesovec, Jul 28 2013

E.g.f.: T(0)/(1-x), where T(k) = 1 - x^2*(k+1)^2/( x^2*(k+1)^2 - (1-x-x*k)*(1-2*x-x*k)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 17 2013

EXAMPLE

Permutations without double increase and without pattern 123:

a(3) = 5: 132, 213, 231, 312, 321.

a(4) = 17: 1324, 1423, 1432, 2143, 2314, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312, 4321.

MATHEMATICA

Table[Simplify[ n! SeriesCoefficient[ Series[ Sqrt[3] Exp[x/2]/(Sqrt[3] Cos[Sqrt[3]/2 x] - Sin[Sqrt[3]/2 x]), {x, 0, n}], n] ], {n, 0, 40}]

CROSSREFS

Cf. A065429, A080635, A111004, A117158, A177523, A177533.

Column k=0 of A162975.

Column k=3 of A242784.

Sequence in context: A263681 A263642 A263682 * A139402 A143382 A057219

Adjacent sequences:  A049771 A049772 A049773 * A049775 A049776 A049777

KEYWORD

nonn,nice,easy

AUTHOR

Tuwani A. Tshifhumulo (tat(AT)caddy.univen.ac.za)

EXTENSIONS

Corrected and extended by Vladeta Jovovic, Apr 14 2001

Corrected g.f. --> e.g.f. by Vaclav Kotesovec, Feb 15 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified January 23 21:40 EST 2017. Contains 281216 sequences.