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
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.
, , ,
, , , ,
every alternating permutation can be written either forward or reversed, and so must be
an even number .
can be simply computed from the recurrence equation
pass through all integral numbers such that
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.
Book of Numbers. New York: Springer-Verlag, pp. 110-111, 1996.Dörrie,
H. "André's Derivation of the Secant and Tangent Series." §16
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."
N. J. A. Sequences A000111/M1492,
and A001250/M1235 in "The On-Line Encyclopedia
of Integer Sequences."