|
Search: id:A022558
|
|
|
| A022558 |
|
Number of permutations of length n avoiding the pattern 1342. |
|
+0
3
|
|
| 1, 1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662, 3475090, 22214707, 144640291, 956560748, 6411521056, 43478151737, 297864793993, 2059159989914, 14350039389022, 100726680316559, 711630547589023, 5057282786190872
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
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.
|
|
LINKS
|
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 (deutsch(AT)duke.poly.edu), Mar 13 2004
|
|
EXAMPLE
|
a(4)=23 because obviously all permutations of length 4 with the exception of 1342 avoid 1342.
|
|
CROSSREFS
|
Essentially the same as A004040. Cf. A117158.
Adjacent sequences: A022555 A022556 A022557 this_sequence A022559 A022560 A022561
Sequence in context: A098746 A088929 A004040 this_sequence A005802 A061552 A053488
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
Miklos Bona (bona(AT)math.ufl.edu)
|
|
EXTENSIONS
|
More terms from Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 13 2004
|
|
|
Search completed in 0.002 seconds
|
