Alternating Permutation

An alternating permutation is an arrangement of the elements , ..., such that no element has a magnitude between and is called an alternating (or zigzag) permutation. The determination of the number of alternating permutations for the set of the first integers is known as André's problem.

The numbers of alternating permutations on the integers from 1 to for , 2, ... are 1, 2, 4, 10, 32, 122, 544, ... (OEIS A001250). For example, the alternating permutations on integers for small are summarized in the following table.

		alternating permutations
1	1
2	2	,
3	4	, , ,
4	10	, , , , ,
		, , , ,

For , every alternating permutation can be written either forward or reversed, and so must be an even number . The quantity can be simply computed from the recurrence equation

(1)

where and pass through all integral numbers such that

(2)

, and

(3)

The numbers are sometimes called the Euler zigzag numbers, and the first few are given by 1, 1, 1, 2, 5, 16, 61, 272, ... (OEIS A000111).

The even-numbered s are called Euler numbers , secant numbers , or zig numbers (1, 1, 5, 61, 1385, ...; OEIS A000364), and the odd-numbered ones are sometimes called tangent numbers or zag numbers (1, 2, 16, 272, 7936, ...; OEIS A000182).

Curiously, the secant and tangent Maclaurin series can be written in terms of the s as

			(4)
			(5)

or combining them,

(6)