login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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. 42
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, pp. 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.

Juan S. Auli, Pattern Avoidance in Inversion Sequences, Ph. D. thesis, Dartmouth College, ProQuest Dissertations Publishing (2020), 27964164.

Juan S. Auli, Sergi Elizalde, Consecutive Patterns in Inversion Sequences, arXiv:1904.02694 [math.CO], 2019. See Table 1.

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

Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.

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; Local copy [Pdf file only, no active links].

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

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

Steven Finch, Pattern-Avoiding Permutations [Archived version]

Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]

Ira M. Gessel and Yan Zhuang, Counting permutations by alternating descents , arXiv:1408.1886 [math.CO], 2014. See Eq. (3). - 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 and Doron Zeilberger, Increasing Consecutive Patterns in Words, arXiv:1805.06077 [math.CO], 2018.

Christopher Zhu, Enumerating Permutations and Rim Hooks Characterized by Double Descent Sets, arXiv:1910.12818 [math.CO], 2019.

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}]

(* Second program: *)

b[u_, o_, t_, k_] := b[u, o, t, k] = If[t == k, (u + o)!, If[Max[t, u] + o < k, 0, Sum[b[u + j - 1, o - j, t + 1, k], {j, 1, o}] + Sum[b[u - j, o + j - 1, 1, k], {j, 1, u}]]];

a[n_] := b[0, n, 0, 2] - b[0, n, 0, 3] + 1;

a /@ Range[0, 40] (* Jean-François Alcover, Nov 09 2020, after Alois P. Heinz in A000303 *)

CROSSREFS

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

Column k=0 of A162975.

Column k=3 of A242784.

Equals 1 + A000303. - Greg Dresden, Feb 22 2020

Sequence in context: A263681 A263642 A263682 * A317132 A335926 A139402

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 19:16 EDT 2021. Contains 348155 sequences. (Running on oeis4.)