Alternating permutation

In combinatorial mathematics, an alternating permutation (or zigzag permutation) of the set {1, 2, 3, ..., n} is a permutation (arrangement) of those numbers so that each entry is alternately greater or less than the preceding entry. 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, and
• 3, 4, 1, 2        because       3 < 4 > 1 < 2.

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

Different authors use the term alternating permutation slightly differently: some require that the second entry in an alternating permutation should be larger than the first (as in the examples above), others require that the alternation should be reversed (so that the second entry is smaller than the first, then the third larger than the second, and so on), while others call both types by the name alternating permutation.

The determination of the number A_n of alternating permutations of the set {1, ..., n} is called André's problem. The numbers A_n are known as Euler numbers, zigzag numbers, or up/down numbers. When n is even the number A_n is known as a secant number, while if n is odd it is known as a tangent number. These latter names come from the study of the generating function for the sequence.