Alternating permutation

Not to be confused with alternating group.

In combinatorial mathematics, an alternating permutation of the set {1, 2, 3, ..., n} is an arrangement of those numbers into an order c₁, ..., c_n such that no element c_i is between c_i − 1 and c_i + 1 for any value of i and c₁< c₂. In other words, c_i < c_i+ 1 if i is odd and c_i > c_i+ 1 if i is even. For example, the five alternating permutations of {1, 2, 3, 4} are:

• 1, 3, 2, 4       because       1 < 3 > 2 < 4
• 1, 4, 2, 3       because       1 < 4 > 2 < 3
• 2, 3, 1, 4       because       2 < 3 > 1 < 4
• 2, 4, 1, 3       because       2 < 4 > 1 < 3
• 3, 4, 1, 2       because       3 < 4 > 1 < 2

This type of permutation was first studied by Désiré André in the 19th century.

If the condition c₁ < c₂ is dropped, so we only require that no element c_i is between c_i − 1 and c_i + 1, then the permutation is called a zigzag permutation. By exchanging 1 with n, 2 with n − 1, etc., each zigzag permutation with c₁> c₂ can be paired uniquely with an alternating permutation.

Related integer sequences

The determination of the number, A_n, of alternating permutations of the set {1, ..., n} is called André's problem. If Z_n denotes the number of zigzag permutations of {1, ..., n} then it is clear from the pairing given above that Z_n = 2A_n for n ≥ 2. The numbers A_n are known as Euler zigzag numbers or up/down numbers. The first few values of A_n are 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, ... (sequence A000111 in OEIS). The first few values of Z_n are 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, ... (sequence A001250 in OEIS).

The Euler zigzag numbers are related to Entringer numbers, from which the zigzag numbers may be computed. The n^th zigzag number is equal to the Entringer number E(n, n), and these Entringer numbers can be defined recursively as follows:

$E(0,0) = 1$

$E(n,0) = 0 \qquad \mbox{for } n > 0$

$E(n,k) = E(n, k-1) + E(n-1, n-k)$.

The numbers A_2n with even indices are called secant numbers or zig numbers. The first few values are 1, 1, 5, 61, 1385, 50521, ... (sequence A000364 in OEIS). They appear as numerators in the Maclaurin series of sec x. Specifically,

$\sec x = 1 + \frac{1}{2!}x^2 + \frac{5}{4!}x^4 + \cdots = \sum_{n=0}^\infty A_{2n} {x^{2n} \over ({2n})!}.$

Secant numbers are related to Euler numbers by the formula E_2n = (−1)ⁿA_2n. (E_n = 0 when n is odd.)

Correspondingly, the numbers A_2n+1 with odd indices are called tangent numbers or zag numbers. The first few values are 1, 2, 16, 272, 7936, ... (sequence A000182 in OEIS). They appear as numerators in the Maclaurin series of tan x. Specifically,

$\tan x = \frac{1}{1!}x + \frac{2}{3!}x^3 + \frac{16}{5!}x^5 + \cdots = \sum_{n=0}^\infty A_{2n+1} {x^{2n+1} \over ({2n+1})!}.$

Tangent numbers are related to Bernoulli numbers by the formula

$B_{2n} =(-1)^{n-1}\frac{2n}{4^{2n}-2^{2n}} A_{2n-1}$

for n > 0.

Adding these series together gives the exponential generating function of the sequence A_n:

$\sum_{n=0}^\infty A_n {x^n \over n!} = \sec x + \tan x = \tan\left({x \over 2} + {\pi \over 4}\right).$

$A_n = i^{n+1}\sum _{k=1}^{n+1} \sum _{j=0}^k {k\choose{j}} \frac{(-1)^j(k-2j)^{n+1}}{2^ki^kk}$

André's theorem

In some contexts, one defines the terms alternating permutation and reverse-alternating permutation so that the former are arrangements of the set { 1, 2, 3, ..., n} into a sequence a₁, ..., a_n satisfying

$a_1 > a_2 < a_3 > a_4 < \cdots \,$

and the latter satisfy

$a_1 < a_2 > a_3 < a_4 > \cdots. \,$

(A bijection between alternating and reverse-alternating permutations is given by

$a_i \mapsto n+1-a_i.) \,$

Let E_n be the number of alternating permutations of the set { 1, 2, 3, ..., n}. The first several of these numbers are

$E_0 = 1,\quad E_1=1,\quad E_2=1,\quad E_3=2,\quad E_4=5,\quad E_5=16,\quad E_6=61,\quad E_7=272,\quad \ldots$

André's theorem states:

The exponential generating function of the numbers E_n is

$f(x) = \sum_{n=0}^\infty E_n \frac{x^n}{n!} = \sec x + \tan x.$

The radius of convergence of this series can be seen to be positive by noticing that E_n is bounded above by n!. In fact, the radius is π/2.

Proof

Here we prove André's theorem by means of a combinatorial argument showing that this generating function satisfies a certain differential equation, and we use the initial condition ƒ(0) = 1. This proof is due to André (1881) and also appears in Stanley (1950, pages 46–7). See also this preprint by Stanley.

The principal combinatorial result that we need is this identity:

$2E_{n+1} = \sum_{k=0}^n \binom n k E_k E_{n-k}\text{ if }n\ge 1.\qquad\qquad(1)$

The proviso that n ≥ 1 is crucial.

A proof of this combinatorial identity runs as follows. To choose an alternating or reverse-alternating permutation of the set { 1, 2, 3, ..., n, n + 1 }, we

• choose a subset of size k of the set { 1, ..., n }, then
• choose a reverse-alternating permutation a₁, ..., a_k of the set { 1, ..., k }, then
• choose a reverse-alternating permutation b₁, ..., b_n−k of the set { k + 1, ..., n }.

Then the permutation

$a_k, a_{k-1}, a_{k-2},\ldots, a_1, n+1, b_1, b_2, b_3,\ldots b_{n-k} \,$

is either alternating or reverse-alternating. The number of ways to choose a permutation of { 1, 2, 3, ..., n, n + 1 } that is either alternating or reverse-alternating is 2 E_n+1, and the number of ways to complete the sequence of steps above is

$\binom n k E_k E_{n-k}. \,$

This needs to be done for each possible value of k to get a complete list, hence we sum from k = 0 to k = n. This completes the proof of the identity (1).

Multiplication of both sides of (1) by xⁿ⁺¹/(n+1)! and summing over n ≥ 1, and then prepending the constant and first-degree terms, yields

$2f(x) = 2E_0 + 2E_1 x + 2\sum_{n=1}^\infty E_{n+1}\frac{x^{n+1}}{(n+1)!} = 2E_0 + 2 E_1 x + \sum_{n=1}^\infty \sum_{k=0}^n \binom n k E_k E_{n-k} \frac{x^{n+1}}{(n+1)!}.$

Differentiating both sides, we get

$2f'(x) = 2E_1 + 2\sum_{n=1}^\infty E_{n+1}\frac{x^n}{n!} = 2E_1 + \sum_{n=1}^\infty \sum_{k=0}^n \binom n k E_k E_{n-k} \frac{x^n}{n!}.$

In the last sum, the index n goes from 1 to ∞, not from 0 to ∞. If we change the lower bound of summation from 1 to 0, we simply add 1 to the sum, and compensate by changing the initial term, 2E₁ = 2, to E₁ = 1, getting

$E_1 + \sum_{n=0}^\infty \sum_{k=0}^n \binom n k E_k E_{n-k} \frac{x^n}{n!} = 1 + \sum_{n=0}^\infty \sum_{k=0}^n \left(E_k \frac{x^k}{k!}\right) \left( E_{n-k} \frac{x^{n-k}}{(n-k)!}\right).$

The last sum is over all pairs of positive integers, so the expression above can be rearranged as

$1 + \sum_{i=0}^\infty \sum_{j=0}^\infty E_i\frac{x^i}{i!}\cdot E_j \frac{x^j}{j!}$

(see Cauchy product).

The expression $E_i\frac{x^i}{i!}$ does not change as j goes from 0 to ∞; hence it can be pulled out of the inside sum, getting

$1 + \sum_{i=0}^\infty\left( E_i\frac{x^i}{i!} \sum_{j=0}^\infty E_j\frac{x^j}{j!} \right).$

Now the second sum does not change as i goes from 0 to ∞; hence it can be pulled out of the outer sum, getting

$1 + \left(\sum_{j=0}^\infty E_j\frac{x^j}{j!} \right)\left(\sum_{i=0}^\infty E_i\frac{x^i}{i!} \right).$

This is

$1 + (f(x))^2. \,$

Consequently we have a differential equation

$2f'(x) = 1 + (f(x))^2. \,$

This can be solved by separation of variables, getting

$f(x) = \tan\left( \frac x 2 + \text{constant} \right).$

We have an initial condition ƒ(0) = 1, so we have

$f(x) = \tan\left( \frac x 2 + \frac\pi4 \right).$

Finally, a standard tangent half-angle trigonometric identity gives us

$f(x) = \sec x + \tan x. \,$

This completes the proof of André's theorem.

See also

• Longest alternating subsequence
• Boustrophedon transform
• Fence (mathematics), partially ordered sets that have alternating permutations as their linear extensions

References

• André, D. "Développements de sec x et tan x." Comptes Rendus Acad. Sci., Paris 88, 965–967, 1879.
• .

Further reading

• Weisstein, Eric W., "Alternating Permutation", MathWorld.

External links

• Ross Tang, "An Explicit Formula for the Euler zigzag numbers (Up/down numbers) from power series" A simple explicit formula for A_n.
• "A Survey of Alternating Permutations", a preprint by Richard P. Stanley