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).

André, D. "Developments de et ." Comptes Rendus Acad. Sci. Paris88,
965-967, 1879.André, D. "Memoire sur les permutations alternées."
J. Math.7, 167-184, 1881.Arnold, V. I. "Bernoulli-Euler
Updown Numbers Associated with Function Singularities, Their Combinatorics and Arithmetics."
Duke Math. J.63, 537-555, 1991.Arnold, V. I. "Snake
Calculus and Combinatorics of Bernoulli, Euler, and Springer Numbers for Coxeter
Groups." Russian Math. Surveys47, 3-45, 1992.Bauslaugh,
B. and Ruskey, F. "Generating Alternating Permutations Lexicographically."
BIT30, 17-26, 1990.Conway, J. H. and Guy, R. K.
In The
Book of Numbers. New York: Springer-Verlag, pp. 110-111, 1996.Dörrie,
H. "André's Derivation of the Secant and Tangent Series." §16
in 100
Great Problems of Elementary Mathematics: Their History and Solutions. New
York: Dover, pp. 64-69, 1965.Honsberger, R. Mathematical
Gems III. Washington, DC: Math. Assoc. Amer., pp. 69-75, 1985.Knuth,
D. E. and Buckholtz, T. J. "Computation of Tangent, Euler, and Bernoulli
Numbers." Math. Comput.21, 663-688, 1967.Millar,
J.; Sloane, N. J. A.; and Young, N. E. "A New Operation on Sequences:
The Boustrophedon Transform." J. Combin. Th. Ser. A76, 44-54,
1996.Ruskey, F. "Information of Alternating Permutations."
http://www.theory.csc.uvic.ca/~cos/inf/perm/Alternating.html.Sloane,
N. J. A. Sequences A000111/M1492,
A000182/M2096, A000364/M4019,
and A001250/M1235 in "The On-Line Encyclopedia
of Integer Sequences."