Alternating permutation

Revision as of 11:50, 6 August 2009 by JBL (talk | contribs) (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, <…')
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

An alternating permutation of the integers $1, 2, \ldots, n$ is a permutation of these integers that alternately increases and decreases. For example, $(2, 5, 1, 4, 3)$ and $(2, 1, 5, 3, 4)$ are alternating permutations of $\{1, 2, 3, 4, 5\}$, but $(3, 4, 5, 1, 2)$ 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: $(2, 5, 1, 4, 3)$ is an up-down permutation, while $(2, 1, 5, 3, 4)$ is a down-up permutation. Up-down permutations have descent set $\{2, 4, 6, \ldots\}$ while down-up permutations have descent set $\{1, 3, 5, \ldots\}$.

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 $n$ is the same as the number of down-up alternating permutations of length $n$, and this number is denoted $E_n$ (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 .\]

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}.\]

Proof of these formulas

This article is a stub. Help us out by expanding it.

Invalid username
Login to AoPS