alternating permutation

A permutation {{math|c₁, ..., 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 {{math|c₁ < c₂ > c₃ < ...}}, calling the "down-up" permutations that satisfy {{math|c₁ > c₂ < c₃ > ...}} 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 {{math|c_i}} with {{math|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.

File:Bernoulli-zigzag.jpg

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, ... {{OEIS|id=A000111}}.

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 {{math|n + 1}}, one can show that

: $2A\_\{n+1\}\; =\; \backslash sum\_\{k=0\}^n\; \backslash binom\{n\}\{k\}\; A\_k\; A\_\{n-k\}$

for all {{math|n ≥ 1}}. {{harvtxt|André|1881}} used this recurrence to give a differential equation satisfied by the exponential generating function

: $A(x)\; =\; \backslash sum\_\{n=0\}^\backslash infty\; A\_n\; \backslash frac\{x^n\}\{n!\}$

for the sequence {{math|A_n}}. In fact, the recurrence gives:

:$$

2\sum_{n\geq 1} A_{n+1} \frac{x^{n+1}}{(n+1)!}

= \sum_{n\geq 1} \sum_{k=0}^n \frac{A_k}{k!} \frac{A_{n-k}}{(n-k)!} \frac{x^{n+1}}{n+1}

= \int \left(\sum_{k\geq 0}A_k \frac{x^k}{k!}\right) \left(\sum_{j\geq 0}A_j \frac{x^j}{j!}\right) \, dx - x

where we substitute $j\; =\; n-k$ and $\backslash frac\{x^\{n+1\}\}\{n+1\}=\backslash int\; x^\{k+j\}\backslash ,dx$. This gives the integral equation

:$$

2(A(x) - 1 - x) = \int A(x)^2\,dx - x,

which after differentiation becomes $2\backslash frac\{dA\}\{dx\}\; -\; 2\; =\; A^2-1$.

This differential equation can be solved by separation of variables (using the initial condition $A(0)=A\_0/0!=1$), and simplified using a tangent half-angle formula, giving the final result

: $A(x)\; =\; \backslash tan\; \backslash left(\backslash frac\backslash pi4\; +\; \backslash frac\; x2\backslash right)\; =\; \backslash sec\; x\; +\; \backslash tan\; x$,

the sum of the secant and tangent functions. This result is known as André's theorem. A geometric interpretation of this result can be given using a generalization of a theorem by Johann Bernoulli Philippe Henry, Gerhard Wanner, "Zigzags with Bürgi, Bernoulli, Euler and the Seidel–Entringer–Arnol’d triangle", Elemente der Mathematik 74 (4) : 141–168 (2019)

It follows from André's theorem that the radius of convergence of the series {{math|A(x)}} is {{pi}}/2. This allows one to compute the asymptotic expansion{{citation

| last = Stanley | first = Richard P. | author-link = Richard P. Stanley

| arxiv = 0912.4240

| contribution = A survey of alternating permutations

| doi = 10.1090/conm/531/10466

| mr = 2757798

| pages = 165–196

| publisher = American Mathematical Society | location = Providence, RI

| series = Contemporary Mathematics

| title = Combinatorics and graphs

| volume = 531

| year = 2010}}

: $A\_n\; \backslash sim\; 2\; \backslash left(\backslash frac\{2\}\{\backslash pi\}\backslash right)^\{n\; +\; 1\}\; n!\backslash ,.$

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\}\backslash 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, ... {{OEIS|id=A001250}}.

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:Weisstein, Eric W. "Entringer Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EntringerNumber.html

: $E(0,0)\; =\; 1$

: $E(n,0)\; =\; 0\; \backslash qquad\; \backslash 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 {{math|sec x}}. The first few values are 1, 1, 5, 61, 1385, 50521, ... {{OEIS|id=A000364}}.

Secant numbers are related to the signed Euler numbers (Taylor coefficients of hyperbolic secant) 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, ... {{OEIS|id=A000182}}.

The relationships of Euler zigzag numbers with the Euler numbers, and the Bernoulli numbers can be used to prove the following

{{cite journal

| last = Mendes| first = Anthony

| title = A Note on Alternating Permutations

| pages = 437–440

| issue = 5

| journal = The American Mathematical Monthly

| volume = 114

| year = 2007

| jstor = 27642223 | doi = 10.1080/00029890.2007.11920432 }}

{{cite journal

| last1 = Mező| first1 = István

| last2 = Ramírez| first2 = José L.

| title = The r-alternating permutations

| doi = 10.1007/s00010-019-00658-5

| journal = Aequationes Mathematicae

| year = 2019

}}

:$A\_\{r\}=-\backslash frac\{4^\{r\}\}\{a\_\{r\}\}\; \backslash sum\_\{k=1\}^\{r\}\backslash frac\{(-1)^\{k\}\backslash ,\; S(r,k)\}\{k+1\}\backslash left(\backslash frac\{3\}\{4\}\backslash right)^\{(k)\}$

where

:

(-1)^{\frac{r}{2}} & \mbox{if r is even} \end{cases},

$(x)^\{(n)\}=(x)(x+1)\backslash cdots\; (x+n-1)$ denotes the rising factorial, and $S(r,k)$ denotes Stirling numbers of the second kind.

• Longest alternating subsequence
• Boustrophedon transform
• Fence (mathematics), a partially ordered set that has alternating permutations as its linear extensions

{{Reflist}}

• {{Citation

| last = André

| first = Désiré

| author-link = Désiré André

| title = Développements de séc x et de tang x

| journal = Comptes rendus de l'Académie des sciences

| volume = 88

| pages = 965–967

| year = 1879

| url = http://gallica.bnf.fr/ark:/12148/bpt6k30457/f961.image

}}.

• {{Citation

| last = André

| first = Désiré

| author-link = Désiré André

| title = Sur les permutations alternées

| journal = Journal de mathématiques pures et appliquées

| series = 3e série

| volume = 7

| year = 1881

| pages = 167–184

| url = http://portail.mathdoc.fr/JMPA/PDF/JMPA_1881_3_7_A10_0.pdf

| archive-url = https://web.archive.org/web/20211122232221/http://portail.mathdoc.fr/JMPA/PDF/JMPA_1881_3_7_A10_0.pdf

| url-status = dead

| archive-date = November 22, 2021

}}.

• {{cite journal

|last1=Henry |first1=Philippe |last2=Wanner |first2=Gerhard |year=2019

|title=Zigzags with Bürgi, Bernoulli, Euler and the Seidel–Entringer–Arnol’d triangle

|journal=Elemente der Mathematik |volume=74 |issue=4 |pages=141–168 |doi=10.4171/EM/393

}}.

• {{Cite book

| first = Richard P.

| last = Stanley

| author-link = Richard P. Stanley

| title = Enumerative Combinatorics

| volume = I

| edition = 2nd

| publisher = Cambridge University Press

| year = 2011

}}

• {{MathWorld |title=Alternating Permutation|urlname=AlternatingPermutation}}
• [http://www.voofie.com/content/117/an-explicit-formula-for-the-euler-zigzag-numbers-updown-numbers-from-power-series/ Ross Tang, "An Explicit Formula for the Euler zigzag numbers (Up/down numbers) from power series"] A simple explicit formula for A_n.
• [http://www-math.mit.edu/~rstan/papers/altperm.pdf "A Survey of Alternating Permutations"], a preprint by Richard P. Stanley

Category:Permutations

Category:Enumerative combinatorics