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

 

Logo

The submissions stack has been unacceptably high for several months now. Please voluntarily restrict your submissions and please help with the editing. (We don't want to have to impose further limits.)

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

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

REFERENCES

C. Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint arXiv:1410.2657, 2014

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.

A. R. Conway, A. J. Guttmann, On 1324-avoiding permutations, Adv. Appl. Math. 64 (2015) 50-69.

W. Mlotkowski, K. A. Penson, A Fuss-type family of positive definite sequences, arXiv:1507.07312 (2015), eq. (36).

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

Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152. See Fig. 11.

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.

A005802, A022558, A061552 are representatives for the three Wilf classes for length-four avoiding permutations (cf. A099952).

Sequence in context: A174193 A238639 A226995 * A004040 A216040 A005802

Adjacent sequences:  A022555 A022556 A022557 * A022559 A022560 A022561

KEYWORD

nonn,easy,changed

AUTHOR

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

EXTENSIONS

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 August 29 02:15 EDT 2015. Contains 261184 sequences.