|
| |
|
|
A049774
|
|
Number of permutations of n elements not containing the consecutive pattern 123.
|
|
13
| |
|
|
1, 1, 2, 5, 17, 70, 349, 2017, 13358, 99377, 822041, 7477162, 74207209, 797771521, 9236662346, 114579019469, 1516103040833, 21314681315998, 317288088082405, 4985505271920097, 82459612672301846, 1432064398910663705
(list; graph; refs; listen; history; 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. [From Paul Barry (pbarry(AT)wit.ie), 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
| M. Aigner, Catalan and other numbers: a recurrent theme, Algebraic combinatorics and computer science, 347-390, Springer Italia, Milan, 2001.
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
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].
|
|
|
FORMULA
| G.f.: 1/sum(i>=0, x^(3*i)/(3*i)! - x^(3*i+1)/(3*i+1)! ).
Equivalently, 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 (munarini(AT)mate.polimi.it), 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 (pauldhanna(AT)juno.com), 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
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
|
|
|
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.
Sequence in context: A101971 A162037 A183239 * 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 (vladeta(AT)eunet.rs), Apr 14 2001
|
| |
|
|
