Alternating permutation

Graphic representation of all up-down permutations of length five, starting with the permutation (1,3,2,5,4) (top left) and ending with the permutation (4,5,2,3,1) (bottom right ).

An alternating permutation (also called zigzag permutation ) is in combinatorics a permutation of the first natural numbers , in which there is no number between the preceding and the following number in terms of size. If the sequence begins with an increase, one speaks of an up-down permutation , and it begins with a decrease from a down-up permutation . Alternating permutations have a number of mirror symmetries . Each alternating permutation of odd length corresponds to a full partially ordered binary tree and each alternating permutation of even length corresponds to an almost full such tree. The numbers of alternating permutations of fixed length appear as coefficients in the Maclaurin series of the secant and the tangent function and are closely related to the Euler and Bernoulli numbers . ${\displaystyle n}$

definition

${\displaystyle {\begin{array}{ccccccccccccccccccc}&&\!\!6\!\!&&&&\!\!7\!\!&&&&\!\!4\!\!&&&&\!\!\\&\!\!\diagup \!\!&&\!\!\diagdown \!\!&&\!\!\diagup \!\!&&\!\!\diagdown \!\!&&\!\!\diagup \!\!&&\!\!\diagdown \!\!&&\!\!&\\\!\!5\!\!&&&&\!\!3\!\!&&&&\!\!1\!\!&&&&\!\!2\!\!\end{array}}}$ Illustration of an up-down permutation of the numbers from 1 to 7

If the symmetric group of all permutations of the set , then a permutation is called alternating if in its tuple representation ${\displaystyle S_{n}}$ ${\displaystyle \{1,\ldots ,n\}}$ ${\displaystyle \pi \in S_{n}}$

${\displaystyle \pi =(\pi (1),\pi (2),\ldots ,\pi (n))}$

the numbers are always alternately larger and smaller than the previous number. So it has to be for either ${\displaystyle \pi (2),\ldots ,\pi (n)}$ ${\displaystyle j=2,\ldots ,n-1}$

${\displaystyle \pi (j-1)<\pi (j)>\pi (j+1)}$

or

${\displaystyle \pi (j-1)>\pi (j)<\pi (j+1)}$

be valid. If the sequence of numbers begins with an increase, i.e. , what is called an up-down permutation , it begins with a decrease, i.e. a down-up permutation . More generally, alternating permutations of ordered finite sets , for example alphabets , can also be considered, but the analysis of the mathematical properties can be limited to the first natural numbers. ${\displaystyle \pi (2)>\pi (1)}$ ${\displaystyle \pi (2)<\pi (1)}$ ${\displaystyle n}$

Examples

${\displaystyle n}$	Up-Down Permutations	Down-up permutations	number
2	(1.2)	(2.1)	2
3	(1,3,2), (2,3,1)	(2,1,3), (3,1,2)	4th
4th	(1,3,2,4), (1,4,2,3), (2,3,1,4), (2,4,1,3), (3,4,1,2)	(2,1,4,3), (3,1,4,2), (3,2,4,1), (4,1,3,2), (4,2,3,1)	10

The permutation

${\displaystyle \pi =(3,5,2,4,1,6)\in S_{6}}$

is an up-down permutation because it holds . The permutation ${\displaystyle 3<5>2<4>1<6}$

${\displaystyle \pi =(5,1,4,2,6,3)\in S_{6}}$

however, is a down-up permutation, since . The permutation ${\displaystyle 5>1<4>2<6>3}$

${\displaystyle \pi =(4,5,2,3,6,1)\in S_{6}}$

is not an alternating permutation, because it contains two consecutive increases. ${\displaystyle 2<3<6}$

The table opposite lists all alternating permutations of the symmetrical groups from degrees two to four.

Symmetries

Ascents and descents

With an alternating permutation, ascents and descents alternate. In the case of an up-down permutation, the following applies to odd and even , and vice versa in the case of down-up permutations. An alternating permutation of even length accordingly has as many ascents as descents. An up-down permutation of odd length has one more rise than descents, and a down-up permutation of odd length has one more descent than climbs. Furthermore, alternating permutations have the following two types of mirror symmetries . ${\displaystyle \pi (i+1)>\pi (i)}$ ${\displaystyle i}$ ${\displaystyle \pi (i+1)<\pi (i)}$ ${\displaystyle i}$

Horizontal symmetry

Horizontal (above) and vertical (below) mirror symmetries between up-down permutations (blue) and down-up permutations (red), each of odd and even lengths

If you read a permutation from right to left, you get the corresponding reverse permutation . The reverse of an up-down permutation is again an up-down permutation if is odd and a down-up permutation if is even. Analogously, the reverse of a down-up permutation is again a down-up permutation if it is odd and an up-down permutation if it is even. The image ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

${\displaystyle (\pi (1),\ldots ,\pi (n))\mapsto (\pi (n),\ldots ,\pi (1))}$

thus represents an involution of the set of up-down or down-up permutations, if is odd, and a bijection between the two sets, if is even. ${\displaystyle n}$ ${\displaystyle n}$

Vertical symmetry

Replacing the number in a permutation for each number results in the corresponding complementary permutation . The complement of an up-down permutation is always a down-up permutation and vice versa. The image ${\displaystyle j=1,\ldots ,n}$ ${\displaystyle \pi (j)}$ ${\displaystyle n-\pi (j)+1}$

${\displaystyle (\pi (1),\ldots ,\pi (n))\mapsto (n-\pi (1)+1,\ldots ,n-\pi (n)+1)}$

thus represents a bijection for each between the set of up-down permutations and the set of down-up permutations. ${\displaystyle n}$

number

Recursive representation

Number of down-up permutations of n numbers starting with the number k

${\displaystyle {}_{n}\!\diagdown \!\!{}^{k}}$	1	2	3	4th	5	6th	7th	total
2	0	1						1
3	0	1	1					2
4th	0	1	2	2				5
5	0	2	4th	5	5			16
6th	0	5	10	14th	16	16		61
7th	0	16	32	46	56	61	61	272

Number of up-down permutations of n numbers starting with the number k

${\displaystyle {}_{n}\!\diagdown \!\!{}^{k}}$	1	2	3	4th	5	6th	7th	total
2	1	0						1
3	1	1	0					2
4th	2	2	1	0				5
5	5	5	4th	2	0			16
6th	16	16	14th	10	5	0		61
7th	61	61	56	46	32	16	0	272

Because of the above symmetry, there are as many up-down as down-up permutations. Since these two sets are disjoint, one can restrict oneself to one of the two types when counting. Now designates the number of down-up permutations of the length , as well as the number of down-up permutations of the length that begin with the number , then applies ${\displaystyle n\geq 2}$ ${\displaystyle A_{n}}$ ${\displaystyle n}$ ${\displaystyle A_{n,k}}$ ${\displaystyle n}$ ${\displaystyle k}$

${\displaystyle A_{n}=\sum _{k=1}^{n}A_{n,k}}$.

The figures are for odd and (positive) Euler numbers called, the numbers are called Entringer numbers (sequence A008282 in OEIS ). Each of the down-up permutations of length and starting number is obtained by increasing all numbers from to by one and adding the number in front of an up-down permutation of length that begins at most with the number . After each up-down permutation is created by vertical mirroring of a down-up permutation, the recurrence is obtained for the number with and ${\displaystyle A_{n}}$ ${\displaystyle n}$ ${\displaystyle A_{n,k}}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n-1}$ ${\displaystyle k-1}$ ${\displaystyle k}$ ${\displaystyle n-1}$ ${\displaystyle k}$ ${\displaystyle A_{n,k}}$ ${\displaystyle n\geq 3}$ ${\displaystyle k=2,\ldots ,n}$

${\displaystyle A_{n,k}=\sum _{j=1}^{k-1}A_{n-1,n-j}}$,

where and is set for all . This recurrence is allowed ${\displaystyle A_{2,2}=1}$ ${\displaystyle A_{n,1}=0}$ ${\displaystyle n}$

${\displaystyle A_{n,k}=A_{n,k-1}+A_{n-1,n-k+1}}$

simplify. Correspondingly mirrored recurrences can also be derived for the number of up-down permutations that begin with the number (sequence A010094 in OEIS ). ${\displaystyle k}$

Explicit representation

By resolving the recurrences, the number of up-down or down-up permutations of uneven length can now be explicitly represented

${\displaystyle A_{2n+1}=\sum _{j=1}^{n}\sum _{k=j}^{n}(-1)^{j+n}{\binom {2k}{k-j}}(k+1){\frac {j^{2n}}{2^{k-1}}}}$

and the corresponding representation for the number of up-down or down-up permutations of even length

${\displaystyle A_{2n}=\sum _{j=1}^{n}\sum _{k=j}^{n}(-1)^{j+n}{\binom {2k}{k-j}}{\frac {j^{2n}}{2^{k-1}}}}$.

Overall, this gives the sequence for the number of up-down or down-up permutations ${\displaystyle A_{n}}$

${\displaystyle 1,1,2,5,16,61,272,1385,7936,\ldots }$   (Follow A000111 in OEIS )

and for the total number of alternating permutations of length, the sequence ${\displaystyle 2A_{n}}$ ${\displaystyle n}$

${\displaystyle 1,2,4,10,32,122,544,2770,15872,\ldots }$   (Follow A001250 in OEIS ).

Correspondence on binary trees

Conversion of an up-down permutation into a full, partially ordered binary tree

In the following, binary trees are considered whose nodes are denoted by the first natural numbers . A binary tree is called full if each node has either two or no child nodes . In a partially ordered binary tree , all nodes are marked in such a way that the number of a parent node is always greater than the numbers of the child nodes. Each up-down permutation of odd length now corresponds to a full, partially ordered binary tree with nodes. In order to construct this correspondence, one selects the largest number as the root node of the tree and observes the partial permutations ${\displaystyle \pi \in S_{2n+1}}$ ${\displaystyle 2n+1}$ ${\displaystyle \pi (j)=2n+1}$

${\displaystyle (\pi (1),\ldots ,\pi (j-1))}$   and   ${\displaystyle (\pi (j+1),\ldots ,\pi (2n+1))}$

left and right of this number. The two partial permutations are now again up-down permutations of a subset of the numbers . From these partial permutations the largest element can be selected again and in this way a full, partially ordered binary tree can be built up recursively (see figure). The recursive structure of the binary trees can now be used to derive further recurrences. The root node must have an even index so that the left subtree has nodes and the right subtree has nodes. There are now exactly possibilities to select the numbers of the left subtree, whereby the remaining numbers have to be in the right subtree. If one sets , the recurrence follows for the number of up-down permutations of uneven length ${\displaystyle \{1,\ldots ,2n\}}$ ${\displaystyle j\in \{2,4,\ldots ,2n\}}$ ${\displaystyle j-1}$ ${\displaystyle 2n-j+1}$ ${\displaystyle {\tbinom {2n}{j-1}}}$ ${\displaystyle i=j/2}$

${\displaystyle A_{2n+1}=\sum _{i=1}^{n}{\binom {2n}{2i-1}}A_{2i-1}A_{2n-2i+1}}$

with start value . Each up-down permutation of even length corresponds to an almost full, partially ordered binary tree with nodes, in which only the rightmost leaf of the tree is missing. The corresponding recurrence is obtained for the number of up-down permutations of even length ${\displaystyle A_{1}=1}$ ${\displaystyle \pi \in S_{2n}}$ ${\displaystyle 2n}$

${\displaystyle A_{2n}=\sum _{i=1}^{n}{\binom {2n-1}{2i-1}}A_{2i-1}A_{2n-2i}}$

with start value . Analogous to these two cases, each down-up permutation corresponds to a binary tree that is partially ordered with respect to the reversed order, which is full if the length is odd and almost full if the length is even. Because of the mirror symmetry, the recurrence is obtained for the total number of alternating permutations of the length ${\displaystyle A_{0}=1}$ ${\displaystyle n}$

${\displaystyle 2A_{n+1}=\sum _{i=0}^{n}{\binom {n}{i}}A_{i}A_{n-i}}$

and after setting the discrete convolution ${\displaystyle a_{i}=A_{i}/i!}$

${\displaystyle 2a_{n+1}={\frac {1}{n+1}}\sum _{i=0}^{n}a_{i}a_{n-i}}$.

Generating functions

Differential equation

The exponentially generating function of the sequence ${\displaystyle A_{n}}$

${\displaystyle f(x)=\sum _{n=0}^{\infty }A_{n}{\frac {x^{n}}{n!}}=\sum _{n=0}^{\infty }a_{n}x^{n}}$

satisfies the ordinary differential equation

${\displaystyle 2f'(x)=1+(f(x))^{2}}$

with the initial condition , as can be recalculated by inserting the above recurrence. By separating the variables , the solution of this initial value problem is obtained as ${\displaystyle f(0)=1}$

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

This classic result of analytical combinatorics from 1881 goes back to the French mathematician Désiré André .

Maclaurin series

The numbers are also called secant numbers for even and occur in the Maclaurin series of the secant function ${\displaystyle A_{n}}$ ${\displaystyle n}$

${\displaystyle \sec x=A_{0}+A_{2}{\frac {x^{2}}{2!}}+A_{4}{\frac {x^{4}}{4!}}+\ldots }$

while the numbers for odd are also called tangent numbers and in the series expansion of the tangent function ${\displaystyle n}$

${\displaystyle \tan x=A_{1}x+A_{3}{\frac {x^{3}}{3!}}+A_{5}{\frac {x^{5}}{5!}}+\ldots }$

occurrence. The numbers are closely related to the Bernoulli numbers . ${\displaystyle A_{n}}$ ${\displaystyle B_{n}}$

Asymptotics

For the proportion of the alternating permutations in the set of all permutations, the following applies to asymptotically ${\displaystyle n\to \infty }$

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

This proportion corresponds to the probability that a (uniformly distributed) random permutation of the length is alternating. ${\displaystyle n}$

literature

• Folkmar Bornemann: Concrete Analysis: for students of computer science . Springer, 2008, ISBN 978-3-540-70854-4 .
• Vladimir A. Dobrushkin: Methods in Algorithmic Analysis . CRC Press, 2011, ISBN 978-1-4200-6830-6 (English).
• Philippe Flajolet , Robert Sedgewick : Analytic Combinatorics . Cambridge University Press, 2009, ISBN 978-0-511-80165-5 , doi : 10.1017 / CBO9780511801655 (English).
• Richard P. Stanley: A Survey of Alternating Permutations . 2009, arxiv : 0912.4240 (English).
• Richard P. Stanley : Enumerative Combinatorics . Cambridge University Press, 2011, ISBN 978-1-107-01542-5 (English).

Web links

• Eric W. Weisstein : Alternating Permutation . In: MathWorld (English).
• Eric W. Weisstein : Euler Zigzag Number . In: MathWorld (English).
• Eric W. Weisstein : Entringer Number . In: MathWorld (English).

Individual evidence

1. ^ ^{A b} Stanley: Enumerative Combinatorics . 2011, p. 32 .
2. ↑ Dobrushkin: Methods in Algorithmic Analysis . 2011, p. 430-431 .
3. ↑ Louis Comtet: Advanced Combinatorics . Reidel, Dordrecht 1974, ISBN 90-277-0380-9 , pp. 259 .
4. ^ Bornemann: Concrete Analysis: for students of computer science . 2008, p. 139 .
5. ^ ^{A b} Bornemann: Concrete Analysis: for students of computer science . 2008, p. 140 .
6. ^ ^{A b} Stanley: Enumerative Combinatorics . 2011, p. 47 .
7. ↑ Flajolet, Sedgewick: Analytic Combinatorics . 2009, p. 2 .
8. ^ ^{A b} Bornemann: Concrete Analysis: for students of computer science . 2008, p. 141-142 .