Alternating permutation

Type of 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. 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 An of alternating permutations of the set {1, , n} is called André's problem. The numbers An are known as Euler numbers, zigzag numbers, or up/down numbers. When n is even the number An 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.

A permutation c1, , cn is said to be alternating if its entries alternately rise and descend. Thus, each entry other than the first and the last should be either larger or smaller than both of its neighbors. Some authors use the term alternating to refer only to the "up down" permutations for which c1 < c2 > c3 < , calling the "down up" permutations that satisfy c1 > c2 < c3 > by the name reverse alternating. Other authors reverse this convention, or use the word "alternating" to refer to both up down and down up permutations. There is a simple one to one correspondence between the down up and up down permutations: replacing each entry ci with n + 1 ci reverses the relative order of the entries. By convention, in any naming scheme the unique permutations of length 0 (the permutation of the empty set) and 1 (the permutation consisting of a single entry 1) are taken to be alternating.

The odd indexed zigzag numbers (i. e., the tangent numbers) are closely related to Bernoulli numbers. The relation is given by the formula

for n > 0. If Zn denotes the number of permutations of {1, , n} that are either up down or down up (or both, for n < 2) then it follows from the pairing given above that Zn = 2An for n ≥ 2. The first few values of Zn are 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042,
The Euler zigzag numbers are related to Entringer numbers, from which the zigzag numbers may be computed. The Entringer numbers can be defined recursively as follows:

The nth zigzag number is equal to the Entringer number E(n, n). The numbers A2n with even indices are called secant numbers or zig numbers: since the secant function is even and tangent is odd, it follows from André's theorem above that they are the numerators in the Maclaurin series of sec x. The first few values are 1, 1, 5, 61, 1385, 50521,
Secant numbers are related to the signed Euler numbers (Taylor coefficients of hyperbolic secant) by the formula E2n = (−1)nA2n. (En = 0 when n is odd.) Correspondingly, the numbers A2n+1 with odd indices are called tangent numbers or zag numbers. The first few values are 1, 2, 16, 272, 7936, .