|
| |
|
|
A029759
|
|
Number of permutations which are the union of an increasing and a decreasing subsequence.
|
|
0
| |
|
|
1, 1, 2, 6, 22, 86, 340, 1340, 5254, 20518, 79932, 311028, 1209916, 4707964, 18330728, 71429176, 278586182, 1087537414, 4249391468, 16618640836, 65048019092, 254814326164, 998953992728, 3919041821896, 15385395144092, 60438585676636
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
REFERENCES
| Kremer, Darla; and Shiu, Wai Chee; Finite transition matrices for permutations avoiding pairs of length four patterns. Discrete Math. 268 (2003), no. 1-3, 171-183. MR1983276 (2004b:05006). See Table 1.
|
|
|
LINKS
| M. D. Atkinson, Permutations which are the union of an increasing and a decreasing subsequence, Electronic Journal of Combinatorics: R6 of Volume 5(1).
Wikipedia, Permutation classes avoiding two patterns of length 4.
|
|
|
FORMULA
| G.f.: (1-3*x)/((1-2*x)*sqrt(1-4*x)) [Vincent Vatter, Jun 21 2011]
|
|
|
MAPLE
| f := n->binomial(2*n, n)-sum( 2^(n-m-1)*binomial(2*m, m), m=0.. n-1 );
|
|
|
CROSSREFS
| Sequence in context: A165530 A116707 A116704 * A150255 A107243 A107244
Adjacent sequences: A029756 A029757 A029758 * A029760 A029761 A029762
|
|
|
KEYWORD
| nonn,changed
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
