|
| |
|
|
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
|
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.
C. Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint arXiv:1410.2657 [math.CO], 2014.
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 [math.CO], 2001. 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
|
|
|
AUTHOR
|
Miklos Bona (bona(AT)math.ufl.edu)
|
|
|
EXTENSIONS
|
Minor edits by Vaclav Kotesovec, Aug 24 2014
|
|
|
STATUS
|
approved
|
| |
|
|
