Home Original page

Alternating Permutation

An alternating permutation is an arrangement of the elements c_1, ..., c_n such that no element c_i has a magnitude between c_(i-1) and c_(i+1) is called an alternating (or zigzag) permutation. The determination of the number of alternating permutations for the set of the first n integers {1,2,...,n} is known as André's problem.

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

nZ_nalternating permutations
11{1}
22{1,2}, {2,1}
34{1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}
410{1,3,2,4}, {1,4,2,3}, {2,1,4,3}, {2,3,1,4}, {2,4,1,3},
{3,1,4,2}, {3,2,4,1}, {3,4,1,2}, {4,1,3,2}, {4,2,3,1}

For n>1, every alternating permutation Z_n can be written either forward or reversed, and so must be an even number A_n=Z_n/2. The quantity A_n can be simply computed from the recurrence equation

2na_n=suma_ra_s,

(1)

where r and s pass through all integral numbers such that

r+s=n-1,

(2)

a_0=a_1=1, and

A_n=n!a_n.

(3)

The numbers A_n 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 A_ns are called Euler numbers |E_(2n)|, secant numbers S_n, or zig numbers (1, 1, 5, 61, 1385, ...; OEIS A000364), and the odd-numbered ones are sometimes called tangent numbers T_n or zag numbers (1, 2, 16, 272, 7936, ...; OEIS A000182).

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

or combining them,

secx+tanx=A_0+A_1x+A_2(x^2)/(2!)+A_3(x^3)/(3!)+A_4(x^4)/(4!)+A_5(x^5)/(5!)+....

(6)

See also

Entringer Number, Euler Number, Euler Zigzag Number, Secant Number, Seidel-Entringer-Arnold Triangle, Tangent Number

Explore with Wolfram|Alpha

References

André, D. "Developments de secx et tanx." Comptes Rendus Acad. Sci. Paris 88, 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. Surveys 47, 3-45, 1992.Bauslaugh, B. and Ruskey, F. "Generating Alternating Permutations Lexicographically." BIT 30, 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. A 76, 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."

Referenced on Wolfram|Alpha

Alternating Permutation

Cite this as:

Weisstein, Eric W. "Alternating Permutation." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/AlternatingPermutation.html

Subject classifications