# .

# Alternating permutation

In combinatorial mathematics, an **alternating permutation** of the set {1, 2, 3, ..., *n*} is an arrangement of those numbers into an order *c*_{1}, ..., *c*_{n} such that no element *c*_{i} is between *c*_{i − 1} and *c*_{i + 1} for any value of *i* and *c*_{1}< *c*_{2}. In other words, *c*_{i} < *c*_{i+ 1} if *i* is odd and *c*_{i} > *c*_{i+ 1} if *i* is even. 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

3, 4, 1, 2 because 3 < 4 > 1 < 2

This type of permutation was first studied by Désiré André in the 19th century.^{[1]}

If the condition *c*_{1}< *c*_{2} is dropped, so we only require that no element *c*_{i} is between *c*_{i − 1} and *c*_{i + 1}, then the permutation is called a **zigzag permutation**. By exchanging 1 with *n*, 2 with *n* − 1, etc., each zigzag permutation with *c*_{1}> *c*_{2} can be paired uniquely with an alternating permutation.

Related integer sequences

The determination of the number, *A*_{n}, of alternating permutations of the set {1, ..., *n*} is called **André's problem**. If *Z*_{n} denotes the number of zigzag permutations of {1, ..., *n*} then it is clear from the pairing given above that *Z*_{n} = 2*A*_{n} for *n* ≥ 2. The numbers *A*_{n} are known as **Euler zigzag numbers** or **Up/down numbers**. The first few values of *A*_{n} are 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, ... (sequence A000111 in OEIS). The first few values of *Z*_{n} are 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, ... (sequence A001250 in OEIS).

The numbers *A*_{2n} with even indices are called **secant numbers** or **zig numbers**. The first few values are 1, 1, 5, 61, 1385, 50521, ... (sequence A000364 in OEIS). They appear as numerators in the Maclaurin series of sec *x*. Specifically,

\( \sec x = 1 + \frac{1}{2!}x^2 + \frac{5}{4!}x^4 + \cdots = \sum_{n=0}^\infty A_{2n} {x^{2n} \over ({2n})!}. \)

Secant numbers are related to Euler numbers by the formula *E*_{2n} = (−1)^{n}*A*_{2n}. (*E*_{n} = 0 when *n* is odd.)

Correspondingly, the numbers *A*_{2n+1} with odd indices are called **tangent numbers** or **zag numbers**. The first few values are 1, 2, 16, 272, 7936, ... (sequence A000182 in OEIS). They appear as numerators in the Maclaurin series of tan *x*. Specifically,

\( \tan x = \frac{1}{1!}x + \frac{2}{3!}x^3 + \frac{16}{5!}x^5 + \cdots = \sum_{n=0}^\infty A_{2n+1} {x^{2n+1} \over ({2n+1})!}. \)

Tangent numbers are related to Bernoulli numbers by the formula

\( B_{2n} =(-1)^{n-1}\frac{2n}{4^{2n}-2^{2n}} A_{2n-1} \)

for n > 0.

Adding these series together gives the exponential generating function of the sequence An:

\( \sum_{n=0}^\infty A_n {x^n \over n!} = \sec x + \tan x = \tan\left({x \over 2} + {\pi \over 4}\right). \)

\( A_n = i^{n+1}\sum _{k=1}^{n+1} \sum _{j=0}^k {k\choose{j}} \frac{(-1)^j(k-2j)^{n+1}}{2^ki^kk} \)

See also

Boustrophedon transform

Fence (mathematics), partially ordered sets that have alternating permutations as their linear extensions

References

^ Jessica Millar, N.J.A. Sloane, Neal E. Young, "A New Operation on Sequences: the Boustrouphedon Transform" J. Combinatorial Theory, Series A 76(1):44–54 (1996)

André, D. "Développements de sec x et tan x." Comptes Rendus Acad. Sci., Paris 88, 965–967, 1879.

André, D. "Mémoire sur les permutations alternées." J. Math. 7, 167–184, 1881.

Further reading

Weisstein, Eric W., "Alternating Permutation" from MathWorld.

External links

Ross Tang, "An Explicit Formula for the Euler zigzag numbers (Up/down numbers) from power series" A simple explicit formula for An.

Retrieved from "http://en.wikipedia.org/"

All text is available under the terms of the GNU Free Documentation License