Difference between revisions of "Alternating permutation"
(Created page with 'An '''alternating permutation''' of the integers <math>1, 2, \ldots, n</math> is a permutation of these integers that alternately increases and decreases. For example, <…') |
(No difference)
|
Latest revision as of 11:50, 6 August 2009
An alternating permutation of the integers 
is a permutation of these integers that alternately increases and decreases. For example, 
and 
are alternating permutations of 
, but 
is not. Note that alternating permutations are completely different than members of the alternating group, whose elements are even permutations.
We may distinguish between "up-down" and "down-up" alternating permutations: is an up-down permutation, while is a down-up permutation. Up-down permutations have descent set 
while down-up permutations have descent set 
.
There is no general consensus about whether the phrase "alternating permutation" should refer to up-down permutations, down-up permutations, or both.
Counting alternating permutations
The number of up-down alternating permutations of length 
is the same as the number of down-up alternating permutations of length , and this number is denoted 
(though this convention is not universal). These numbers have various names, including Euler numbers, up-down numbers, and secant and tangent numbers. These latter names are the result of the remarkable generating function (or equivalently Taylor series) identity
![\[\sum_{n = 0}^\infty \frac{E_n}{n!} x^n = \sec x + \tan x .\]](http://latex.artofproblemsolving.com/8/4/2/8424df2c12af44751dc98eea5a291e5e4a1de4dc.png)
One can compute these numbers via the recursion
![\[E_{n + 1} = \frac{1}{2} \sum_{i = 0}^n \binom{n}{i} E_i E_{n - i}.\]](http://latex.artofproblemsolving.com/0/b/7/0b752d49529f6e4a15c9f95b5ef0450c544ff2ad.png)
Proof of these formulas
This article is a stub. Help us out by expanding it.
