Alternating permutation

Not to be confused with the alternating group.

In combinatorial mathematics, an alternating permutation (or zigzag permutation) of the set {1, 2, 3, ..., n} is an arrangement of those numbers so that each entry is alternately greater or less than the preceding entry. 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, and
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]

Different authors use the term alternating permutation slightly differently: some require that the second entry in an alternating permutation should be larger than the first (as in the examples above), others require that the alternation should be reversed (so that the second entry is smaller than the first, then the third larger than the second, and so on), while others call both types by the name alternating permutation.

The determination of the number A_n of alternating permutations of the set {1, ..., n} is called André's problem. The numbers A_n are known as Euler numbers, zigzag numbers, or up/down numbers. When n is even the number A_n is known as a secant number, while if n is odd it is known as a tangent number. These latter names come from the study of the generating function for the sequence.

Definitions

A permutation $c 1, ..., c n$ is said to be alternating if its entries alternately rise and descend. Thus, each entry other than the first and the last should be either larger or smaller than both of its neighbors. Some authors use the term alternating to refer only to the "up-down" permutations for which $c 1 < c 2 > c 3 < ...$ , calling the "down-up" permutations that satisfy $c 1 > c 2 < c 3 > ...$ by the name reverse alternating. Other authors reverse this convention, or use the word "alternating" to refer to both up-down and down-up permutations.

There is a simple one-to-one correspondence between the down-up and up-down permutations: replacing each entry $c i$ with $n + 1 - c i$ reverses the relative order of the entries.

By convention, in any naming scheme the unique permutations of length 0 (the permutation of the empty set) and 1 (the permutation consisting of a single entry 1) are taken to be alternating.

André's theorem

The determination of the number A_n of alternating permutations of the set {1, ..., n} is called André's problem. The numbers A_n are variously known as Euler numbers, zigzag numbers, up/down numbers, or by some combinations of these names. The name Euler numbers in particular is sometimes used for a closely related sequence. The first few values of A_n are 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, ... (sequence A000111 in OEIS).

These numbers satisfy a simple recurrence, similar to that of the Catalan numbers: by splitting the set of alternating permutations (both down-up and up-down) of the set { 1, 2, 3, ..., n, n + 1 } according to the position k of the largest entry $n + 1$ , one can show that

2A_{n+1} = \sum_{k=0}^n \binom{n}{k} A_k A_{n-k}

for all $n \geq 1$ . André (1881) used this recurrence to give a differential equation satisfied by the exponential generating function

A(x) = \sum_{n=0}^\infty A_n \frac{x^n}{n!}

for the sequence $A n$ . He then solved this equation, establishing that

A(x) = \sec x + \tan x

where $sec x$ and $tan x$ are the trigonometric functions secant and tangent. This result is known as André's theorem.

It follows from André's theorem that the radius of convergence of the series $A (x)$ is $π$ /2. This allows one to compute the asymptotic expansion

A_n \sim 2 \left(\frac{2}{\pi}\right)^{n + 1} \cdot n!

of the sequence $A n$ .^[2]

Related integer sequences

The odd-indexed zigzag numbers (i.e., the tangent numbers) are closely related to Bernoulli numbers. The relation is given by the formula

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

for n > 0.

If Z_n denotes the number of permutations of {1, ..., n} that are either up-down or down-up (or both, for n < 2) then it follows from the pairing given above that Z_n = 2A_n for n ≥ 2. The first few values of Z_n are 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, ... (sequence A001250 in OEIS).

The Euler zigzag numbers are related to Entringer numbers, from which the zigzag numbers may be computed. The Entringer numbers can be defined recursively as follows:^[3]

E(0,0) = 1

E(n,0) = 0 \qquad \mbox{for } n > 0

E(n,k) = E(n, k-1) + E(n-1, n-k)

The n^th zigzag number is equal to the Entringer number E(n, n).

The numbers A_2n with even indices are called secant numbers or zig numbers: since the secant function is even and tangent is odd, it follows from André's theorem above that they are the numerators in the Maclaurin series of $sec x$ . The first few values are 1, 1, 5, 61, 1385, 50521, ... (sequence A000364 in OEIS).

Secant numbers are related to Euler numbers by the formula E_2n = (−1)ⁿ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).

Citations

↑ 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)
↑ Stanley, Richard P. (2010). "A survey of alternating permutations". Contemporary Mathematics 531: 165–196. Retrieved 11 February 2016.
↑ Weisstein, Eric W. "Entringer Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EntringerNumber.html

References

André, D. "Développements de sec x et tan x." Comptes Rendus Acad. Sci., Paris 88, 965–967, 1879.
André, Désiré (1881), "Sur les permutations alternées", Journal de mathématiques pures et appliquées, 3e série 7: 167–84
Stanley, Richard P. (2011). Enumerative Combinatorics, Volume I, second edition. Cambridge University Press. .

External links

Ross Tang, "An Explicit Formula for the Euler zigzag numbers (Up/down numbers) from power series" A simple explicit formula for A_n.
"A Survey of Alternating Permutations", a preprint by Richard P. Stanley

This article is issued from Wikipedia - version of the Friday, February 12, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.