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

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A022558 Number of permutations of length n avoiding the pattern 1342. 4
1, 1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662, 3475090, 22214707, 144640291, 956560748, 6411521056, 43478151737, 297864793993, 2059159989914, 14350039389022, 100726680316559, 711630547589023, 5057282786190872, 36132861123763276, 259423620328055093 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Differs from A117156 which counts permutations avoiding the *consecutive* pattern 1342. - Ray Chandler, Dec 06 2011

Number of permutation of length n avoiding the pattern 3142 (see Stankova (1994) below). - Alexander Burstein, Aug 09 2013

REFERENCES

Miklos Bona, Exact enumeration of 1342-avoiding permutations; A close link with labeled trees and planar maps, J. Combinatorial Theory, A80 (1997), 257-272.

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.48.

Z. E. Stankova, Forbidden subsequences, Discrete Math., 132 (1994), no. 1-3, 291-316.

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..200

M. Bona, [math/9702223] Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps

FORMULA

a(n) = (7n^2-3n-2)/2 * (-1)^{n-1} + 3 sum_{i=2,...,n} 2^{i+1} * (2i-4)!/{i!(i-2)!} * binomial{n-i+2. 2} * (-1)^{n-i}.

G.f.: 32x/(1+20x-8x^2-(1-8x)^(3/2)). - Emeric Deutsch, Mar 13 2004

Recurrence: n*a(n) = (7*n-22)*a(n-1) + 4*(2*n-1)*a(n-2). - Vaclav Kotesovec, Oct 07 2012

a(n) ~ 2^(3*n+6)/(243*sqrt(Pi)*n^(5/2)). - Vaclav Kotesovec, Oct 07 2012

EXAMPLE

a(4)=23 because obviously all permutations of length 4 with the exception of 1342 avoid 1342.

MATHEMATICA

Table[SeriesCoefficient[32*x/(1+20*x-8*x^2-(1-8*x)^(3/2)), {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Oct 07 2012 *)

PROG

(PARI) x='x+O('x^66); Vec( 32*x/(1+20*x-8*x^2-(1-8*x)^(3/2)) ) \\ Joerg Arndt, May 04 2013

CROSSREFS

Essentially the same as A004040.

Cf. A117158.

Sequence in context: A174193 A238639 A226995 * A004040 A216040 A005802

Adjacent sequences:  A022555 A022556 A022557 * A022559 A022560 A022561

KEYWORD

nonn,easy

AUTHOR

Miklos Bona (bona(AT)math.ufl.edu)

EXTENSIONS

More terms from Emeric Deutsch, Mar 13 2004

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified April 18 14:05 EDT 2014. Contains 240720 sequences.