Incombinatorialmathematics, analternating permutation (orzigzag permutation) of the set {1, 2, 3, ...,n} is apermutation (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 byDé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 numberA_n of alternating permutations of the set {1, ...,n} is calledAndré's problem. The numbersA_n are known asEuler numbers,zigzag numbers, orup/down numbers. Whenn is even the numberA_n is known as asecant number, while ifn is odd it is known as atangent number. These latter names come from the study of thegenerating function for the sequence.

Apermutationc₁, ...,c_n is said to bealternating 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 whichc₁ <c₂ >c₃ < ..., calling the "down-up" permutations that satisfyc₁ >c₂ <c₃ > ... by the namereverse alternating. Other authors reverse this convention, or use the word "alternating" to refer to both up-down and down-up permutations.

There is a simpleone-to-one correspondence between the down-up and up-down permutations: replacing each entryc_i withn + 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 theempty set) and 1 (the permutation consisting of a single entry 1) are taken to be alternating.

The determination of the numberA_n of alternating permutations of the set {1, ...,n} is calledAndré's problem. The numbersA_n are variously known asEuler numbers,zigzag numbers,up/down numbers, or by some combinations of these names. The nameEuler numbers in particular is sometimes used for a closely related sequence. The first few values ofA_n are 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, ... (sequenceA000111 in theOEIS).

These numbers satisfy a simple recurrence, similar to that of theCatalan 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 positionk of the largest entryn + 1, one can show that

${\displaystyle 2A_{n+1}=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})A_k{A}_{n-k}}$

for alln ≥ 1.André (1881) used this recurrence to give adifferential equation satisfied by theexponential generating function

${\displaystyle A(x)=\sum _{n=0}^{\mathrm{\infty }}{A}_n\frac{x^n}{n!}}$

for the sequenceA_n. In fact, the recurrence gives:

${\displaystyle 2\sum _{n\ge 1}{A}_{n+1}\frac{x^{n+1}}{(n+1)!}=\sum _{n\ge 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\ge 0}{A}_k\frac{x^k}{k!}\right)\left(\sum _{j\ge 0}{A}_j\frac{x^j}{j!}\right)dx-x}$

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

${\displaystyle 2(A(x)-1-x)=\int A(x{)}^{2}dx-x,}$

which after differentiation becomes${\displaystyle 2\frac{dA}{dx}-2=A^2-1}$.This differential equation can be solved byseparation of variables (using theinitial condition${\displaystyle A(0)=A_0/0!=1}$), and simplified using atangent half-angle formula, giving the final result

${\displaystyle A(x)=\tan \left(\frac{\pi }{4}+\frac{x}{2}\right)=\sec x+\tan x}$,

the sum of thesecant andtangent functions. This result is known asAndré's theorem. 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 theradius of convergence of the seriesA(x) is π/2. This allows one to compute theasymptotic expansion^[3]

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

In 1877Philipp Ludwig von Seidel published an algorithm, which makes it simple to calculateA_n.^[4]

Seidel's algorithm forA_n

1. Start by putting 1 in row 0 and letk denote the number of the row currently being filled
2. Ifk is odd, then put the number on the left end of the rowk − 1 in the first position of the rowk, and fill the row from the left to the right, with every entry being the sum of the number to the left and the number to the upper
3. At the end of the row duplicate the last number.
4. Ifk is even, proceed similar in the other direction.

Seidel's algorithm is in fact much more general (see the exposition of Dominique Dumont^[5]) and was rediscovered several times thereafter.

Similar to Seidel's approach D. E. Knuth and T. J. Buckholtz gave a recurrence equation for the numbersA_2n and recommended this method for computing theBernoulli numbersB_2n andEuler numbersE_2n 'on electronic computers using only simple operations on integers'.^[6]

V. I. Arnold^[7] rediscovered Seidel's algorithm and later Millar, Sloane and Young popularized Seidel's algorithm under the nameboustrophedon transform.

Triangular form:

						1
					1		1
				2		2		1
			2		4		5		5
		16		16		14		10		5
	16		32		46		56		61		61
272		272		256		224		178		122		61

OnlyOEIS: A000657, with one 1, andOEIS: A214267, with two 1s, are in the OEIS.

Distribution with a supplementary 1 and one 0 in the following rows:

						1
					0		1
				−1		−1		0
			0		−1		−2		−2
		5		5		4		2		0
	0		5		10		14		16		16
−61		−61		−56		−46		−32		−16		0

This isOEIS: A239005, a signed version ofOEIS: A008280. The main andiagonal isOEIS: A122045. Themain diagonal isOEIS: A155585. The central column isOEIS: A099023. Row sums: 1, 1, −2, −5, 16, 61.... SeeOEIS: A163747. See the array beginning with 1, 1, 0, −2, 0, 16, 0 below.

The Akiyama–Tanigawa algorithm applied toOEIS: A046978 (n + 1) /OEIS: A016116(n) yields:

1	1	⁠1/2⁠	0	−⁠1/4⁠	−⁠1/4⁠	−⁠1/8⁠
0	1	⁠3/2⁠	1	0	−⁠3/4⁠
−1	−1	⁠3/2⁠	4	⁠15/4⁠
0	−5	−⁠15/2⁠	1
5	5	−⁠51/2⁠
0	61
−61

1. The first column isOEIS: A122045. Itsbinomial transform leads to:

1	1	0	−2	0	16	0
0	−1	−2	2	16	−16
−1	−1	4	14	−32
0	5	10	−46
5	5	−56
0	−61
−61

The first row of this array isOEIS: A155585. The absolute values of the increasing antidiagonals areOEIS: A008280. The sum of the antidiagonals is−OEIS: A163747 (n + 1).

2. The second column is1 1 −1 −5 5 61 −61 −1385 1385.... Its binomial transform yields:

1	2	2	−4	−16	32	272
1	0	−6	−12	48	240
−1	−6	−6	60	192
−5	0	66	32
5	66	66
61	0
−61

The first row of this array is1 2 2 −4 −16 32 272 544 −7936 15872 353792 −707584.... The absolute values of the second bisection are the double of the absolute values of the first bisection.

Consider the Akiyama-Tanigawa algorithm applied toOEIS: A046978 (n) / (OEIS: A158780 (n + 1) = abs(OEIS: A117575 (n)) + 1 =1, 2, 2,⁠3/2⁠, 1,⁠3/4⁠,⁠3/4⁠,⁠7/8⁠, 1,⁠17/16⁠,⁠17/16⁠,⁠33/32⁠....

1	2	2	⁠3/2⁠	1	⁠3/4⁠	⁠3/4⁠
−1	0	⁠3/2⁠	2	⁠5/4⁠	0
−1	−3	−⁠3/2⁠	3	⁠25/4⁠
2	−3	−⁠27/2⁠	−13
5	21	−⁠3/2⁠
−16	45
−61

The first column whose the absolute values areOEIS: A000111 could be the numerator of a trigonometric function.

OEIS: A163747 is an autosequence of the first kind (the main diagonal isOEIS: A000004). The corresponding array is:

0	−1	−1	2	5	−16	−61
−1	0	3	3	−21	−45
1	3	0	−24	−24
2	−3	−24	0
−5	−21	24
−16	45
−61

The first two upper diagonals are−1 3 −24 402... =(−1)^{n + 1} × OEIS: A002832. The sum of the antidiagonals is0 −2 0 10... = 2 × OEIS: A122045(n + 1).

−OEIS: A163982 is an autosequence of the second kind, like for instanceOEIS: A164555 /OEIS: A027642. Hence the array:

2	1	−1	−2	5	16	−61
−1	−2	−1	7	11	−77
−1	1	8	4	−88
2	7	−4	−92
5	−11	−88
−16	−77
−61

The main diagonal, here2 −2 8 −92..., is the double of the first upper one, hereOEIS: A099023. The sum of the antidiagonals is2 0 −4 0... = 2 × OEIS: A155585(n +1).OEIS: A163747 − OEIS: A163982 = 2 × OEIS: A122045.

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

${\displaystyle B_{2n}=(-1{)}^{n-1}\frac{2n}{4^{2n}-2^{2n}}{A}_{2n-1}}$

for n > 0.

IfZ_n denotes the number of permutations of {1, ...,n} that are either up-down or down-up (or both, forn < 2) then it follows from the pairing given above thatZ_n = 2A_n forn ≥ 2. The first few values ofZ_n are 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, ... (sequenceA001250 in theOEIS).

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:^[8]

${\displaystyle E(0,0)=1}$

${\displaystyle E(n,0)=0\text{for }n>0}$

${\displaystyle E(n,k)=E(n,k-1)+E(n-1,n-k)}$.

Then^th zigzag number is equal to the Entringer numberE(n,n).

The numbersA_2n with even indices are calledsecant numbers orzig numbers: since the secant function iseven and tangent isodd, it follows from André's theorem above that they are the numerators in theMaclaurin series ofsecx. The first few values are 1, 1, 5, 61, 1385, 50521, ... (sequenceA000364 in theOEIS).

Secant numbers are related to the signedEuler numbers (Taylor coefficients of hyperbolic secant) by the formulaE_2n = (−1)ⁿA_2n. (E_n = 0 whenn is odd.)

Correspondingly, the numbersA_2n+1 with odd indices are calledtangent numbers orzag numbers. The first few values are 1, 2, 16, 272, 7936, ... (sequenceA000182 in theOEIS).

The relationships of Euler zigzag numbers with theEuler numbers, and theBernoulli numbers can be used to prove the following^[9][10]

${\displaystyle A_r=-\frac{4^r}{a_r}\sum _{k=1}^r\frac{(-1{)}^{k}S(r,k)}{k+1}{\left(\frac{3}{4}\right)}^{(k)}}$

where

${\displaystyle (x{)}^{(n)}=(x)(x+1)\cdots (x+n-1)}$ denotes therising factorial, and${\displaystyle S(r,k)}$ denotesStirling numbers of the second kind.

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

• André, Désiré (1879),"Développements de séc x et de tang x",Comptes rendus de l'Académie des sciences,88:965–967.

• André, Désiré (1881),"Sur les permutations alternées"(PDF),Journal de mathématiques pures et appliquées, 3e série,7:167–184, archived fromthe original(PDF) on November 22, 2021.

• Henry, Philippe; Wanner, Gerhard (2019). "Zigzags with Bürgi, Bernoulli, Euler and the Seidel–Entringer–Arnol'd triangle".Elemente der Mathematik.74 (4):141–168.doi:10.4171/EM/393..

• Stanley, Richard P. (2011).Enumerative Combinatorics. Vol. I (2nd ed.).Cambridge University Press.

• Weisstein, Eric W."Alternating Permutation".MathWorld.
• Ross Tang, "An Explicit Formula for the Euler zigzag numbers (Up/down numbers) from power series" A simple explicit formula forA_n.
• "A Survey of Alternating Permutations", a preprint byRichard P. Stanley

• Permutations
• Enumerative combinatorics

• Articles with short description
• Short description is different from Wikidata
• Use mdy dates from September 2021
• Use American English from March 2019
• All Wikipedia articles written in American English