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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A022558 Number of permutations of length n avoiding the pattern 1342. 5
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

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

LINKS

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

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

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

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

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.

MAPLE

a := proc (n) options operator, arrow: (1/2)*(-1)^(n-1)*(7*n^2-3*n-2)+3*(sum((-1)^(n-i)*2^(i+1)*factorial(2*i-4)*binomial(n-i+2, 2)/(factorial(i)*factorial(i-2)), i = 2 .. n)) end proc: seq(a(n), n = 1 .. 30); # Emeric Deutsch, Oct 15 2014

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 *)

Table[1/2*(-1)^(n-1) * (-2-3*n+7*n^2) + 1/4*(-1)^n * (1+n) * (-2-13*n+(n+2) * Hypergeometric2F1[-3/2, -n, -2-n, -8]), {n, 0, 20}] (* Vaclav Kotesovec, Aug 24 2014 *)

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

Minor edits by Vaclav Kotesovec, Aug 24 2014

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 November 26 19:11 EST 2014. Contains 250103 sequences.