Alternating permutation

[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 An of alternating permutations of the set {1, ..., n} is called André's problem.

These latter names come from the study of the generating function for the sequence.

Some authors use the term alternating to refer only to the "up-down" permutations for which c1 < c2 > c3 < ..., calling the "down-up" permutations that satisfy c1 > c2 < c3 > ... 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 ci with n + 1 - ci reverses the relative order of the entries.

The determination of the number An of alternating permutations of the set {1, ..., n} is called André's problem.

The name Euler numbers in particular is sometimes used for a closely related sequence.

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 for all n ≥ 1.

André (1881) used this recurrence to give a differential equation satisfied by the exponential generating function for the sequence An.

This differential equation can be solved by separation of variables (using the initial condition

), and simplified using a tangent half-angle formula, giving the final result the sum of the secant and tangent functions.

A geometric interpretation of this result can be given using a generalization of a theorem by Johann Bernoulli [2] It follows from André's theorem that the radius of convergence of the series A(x) is π/2.

Secant numbers are related to the signed Euler numbers (Taylor coefficients of hyperbolic secant) by the formula E2n = (−1)nA2n.