Alternating permutation

Short description: Type of permutation

Not to be confused with Alternating group.

In combinatorial mathematics, an alternating permutation (or zigzag permutation) of the set {1, 2, 3, ..., n} is a permutation (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 An of alternating permutations of the set {1, ..., n} is called André's problem. The numbers An are known as Euler numbers, zigzag numbers, or up/down numbers. When n is even the number An 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.

## Contents

* 1 Definitions
* 2 André's theorem
* 3 Seidel's Algorithm
* 4 Related sequences
* 5 Explicit formula in terms of Stirling numbers of the second kind
* 6 See also
* 7 Citations
* 8 References
* 9 External links

## Definitions

A permutation c1, ..., cn 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 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.

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 zigzag numbers in Bernoulli (1742), Opera Omnia vol. 4, p. 105

The determination of the number An of alternating permutations of the set {1, ..., n} is called André's problem. The numbers An 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 An are 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, ... (sequence A000111 in the 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

2An+1=∑k=0n(nk)AkAn−k

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

A(x)=∑n=0∞Anxnn!

for the sequence An. In fact, the recurrence gives:

2∑n≥1An+1xn+1(n+1)!=∑n≥1∑k=0nAkk!An−k(n−k)!xn+1n+1=∫(∑k≥0Akxkk!)(∑j≥0Ajxjj!)dx−x

where we substitute j=n−k and xn+1n+1=∫xk+jdx. This gives the integral equation

2(A(x)−1−x)=∫A(x)2dx−x,

which after differentiation becomes 2dAdx−2=A2−1. This differential equation can be solved by separation of variables (using the initial condition A(0)=A0/0!=1), and simplified using a tangent half-angle formula, giving the final result

A(x)=tan⁡(π4+x2)=sec⁡x+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 [2]

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[3]

An∼2(2π)n+1n!.

## Seidel's Algorithm

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

1->11221<-->2455161614105<-

Seidel's algorithm for An

1. Start by putting 1 in row 0 and let k denote the number of the row currently being filled
2. If k is odd, then put the number on the left end of the row k − 1 in the first position of the row k, 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. If k 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 numbers A2n and recommended this method for computing the Bernoulli numbers B2n and Euler numbers E2n '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 name boustrophedon 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

Only OEIS: A000657, with one 1, and OEIS: 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 is OEIS: A239005, a signed version of OEIS: A008280. The main andiagonal is OEIS: A122045. The main diagonal is OEIS: A155585. The central column is OEIS: A099023. Row sums: 1, 1, −2, −5, 16, 61.... See OEIS: A163747. See the array beginning with 1, 1, 0, −2, 0, 16, 0 below.

The Akiyama–Tanigawa algorithm applied to OEIS: 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 is OEIS: A122045. Its binomial 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 is OEIS: A155585. The absolute values of the increasing antidiagonals are OEIS: A008280. The sum of the antidiagonals is −OEIS: A163747 (n \+ 1).

2. The second column is 1 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 is 1 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 to OEIS: 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 are OEIS: A000111 could be the numerator of a trigonometric function.

OEIS: A163747 is an autosequence of the first kind (the main diagonal is OEIS: 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 is 0 −2 0 10... = 2 × OEIS: A122045(n + 1).

−OEIS: A163982 is an autosequence of the second kind, like for instance OEIS: 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, here 2 −2 8 −92..., is the double of the first upper one, here OEIS: A099023. The sum of the antidiagonals is 2 0 −4 0... = 2 × OEIS: A155585(n \+ 1). OEIS: A163747 − OEIS: A163982 = 2 × OEIS: A122045.

## Related sequences

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

B2n=(−1)n−12n42n−22nA2n−1

for n > 0\.

If Zn 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 Zn = 2An for n ≥ 2\. The first few values of Zn are 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, ... (sequence A001250 in the 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:[8]

E(0,0)=1
E(n,0)=0for n>0
E(n,k)=E(n,k−1)+E(n−1,n−k).

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

The numbers A2n 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 the OEIS).

Secant numbers are related to the signed Euler numbers (Taylor coefficients of hyperbolic secant) by the formula E2n = (−1)nA2n. (En = 0 when n is odd.)

Correspondingly, the numbers A2n+1 with odd indices are called tangent numbers or zag numbers. The first few values are 1, 2, 16, 272, 7936, ... (sequence A000182 in the OEIS).

## Explicit formula in terms of Stirling numbers of the second kind

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

Ar=−4rar∑k=1r(−1)kS(r,k)k+1(34)(k)

where

ar={(−1)r−12(1+2−r)if r is odd(−1)r2if r is even,

(x)(n)=(x)(x+1)⋯(x+n−1) denotes the rising factorial, and S(r,k) denotes Stirling numbers of the second kind.

## See also

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

## Citations

1. ↑ Jessica Millar, N. J. A. Sloane, Neal E. Young, "A New Operation on Sequences: the Boustrouphedon Transform" Journal of Combinatorial Theory, Series A 76(1):44–54 (1996)
2. ↑ 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)
3. ↑ "A survey of alternating permutations", Combinatorics and graphs, Contemporary Mathematics, 531, Providence, RI: American Mathematical Society, 2010, pp. 165–196, doi:10.1090/conm/531/10466
4. ↑ Seidel, L. (1877), "Über eine einfache Entstehungsweise der Bernoullischen Zahlen und einiger verwandten Reihen", Sitzungsber. Münch. Akad. 4: 157–187
5. ↑ Dumont, D. (1981), "Matrices d'Euler-Seidel", Séminaire Lotharingien de Combinatoire B05c, https://www.mat.univie.ac.at/~slc/opapers/s05dumont.html
6. ↑ Knuth, D. E.; Buckholtz, T. J. (1967), "Computation of Tangent, Euler, and Bernoulli Numbers", Mathematics of Computation (American Mathematical Society) 21 (100): 663–688, doi:10.2307/2005010
7. ↑ Arnold, V. I. (1991), "Bernoulli-Euler updown numbers associated with function singularities, their combinatorics and arithmetics", Duke Math. J. 63 (2): 537–555, doi:10.1215/s0012-7094-91-06323-4
8. ↑ Weisstein, Eric W. "Entringer Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EntringerNumber.html
9. ↑ Mendes, Anthony (2007). "A Note on Alternating Permutations". The American Mathematical Monthly 114 (5): 437–440. doi:10.1080/00029890.2007.11920432.
10. ↑ Mező, István; Ramírez, José L. (2019). "The r-alternating permutations". Aequationes Mathematicae. doi:10.1007/s00010-019-00658-5.

## References

* 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, http://gallica.bnf.fr/ark:/12148/bpt6k30457/f961.image .

* André, Désiré (1881), "Sur les permutations alternées", Journal de mathématiques pures et appliquées, 3e série 7: 167–184, http://portail.mathdoc.fr/JMPA/PDF/JMPA_1881_3_7_A10_0.pdf .

* 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. I (2nd ed.). Cambridge University Press.

## External links

* Weisstein, Eric W.. "Alternating Permutation". http://mathworld.wolfram.com/AlternatingPermutation.html.
* Ross Tang, "An Explicit Formula for the Euler zigzag numbers (Up/down numbers) from power series" A simple explicit formula for An.
* "A Survey of Alternating Permutations", a preprint by Richard P. Stanley

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Alternating permutation. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Alternating_permutation&oldid=4297369"