Alternating permutation
An alternating permutation ( called zigzag permutation ) is a permutation of the first combinatorial natural numbers where no number is according to the size between the previous and the following numbers. Begins the sequence with an increase, one speaks of an up -down permutation, it begins with a descent 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 straight length a nearly full such a tree. The numbers of alternating permutations of fixed length occur as coefficients in the Maclaurin series of the secant and the tangent function and are closely related to the Euler and Bernoulli numbers.
- 4.1 Recursive representation
- 4.2 Explicit representation
- 6.1 Differential Equation
- 6.2 Maclaurin series
- 6.3 asymptotics
Definition
Is the symmetric group of all permutations of the set, then is called a permutation alternately when in their Tupeldarstellung
The numbers are alternately larger and smaller than the corresponding previous number. So there must be for either
Or
. apply Begins the sequence of numbers with an increase, is so, then one speaks of an up -down permutation, it begins with a descent, that is true of a down -up permutation. More generally, also alternating permutations of finite sets of ordered, such as alphabets are considered, but the analysis of the mathematical properties can be limited to the first natural numbers.
Examples
The permutation
Is an up-down permutation because it is. The permutation
However, is a down -up permutation, as applies. The permutation
Is not an alternating permutation, because it contains two consecutive rises.
The accompanying table lists all alternating permutations of the symmetric group of degree two to four.
Symmetries
Ascents and descents
When an alternating permutation to change increases with descents from. In an up-down permutation corresponding reverse is also true for odd and even, in Down -Up - permutations. An alternating permutation straight length accordingly has the same number of arrivals and descents. An up-down permutation of odd length in an increase more than descents, a down -up permutation of odd length a descent more than ascents. Furthermore, have alternating permutations on the following two types of mirror symmetries.
Horizontal symmetry
If you read a permutation from right to left, to give the corresponding reverse permutation. The reverse of one up-down permutation is again an up-down permutation if is odd and a down -up permutation if even. Similarly, the reverse a down -up permutation is again a down -up permutation if is odd, and an up-down permutation if even. The figure
Therefore represents an involution of the amount of up-down or down -up permutations, if is odd and a bijection between the two amounts, if even.
Vertical symmetry
If, in a permutation for each number by the number, you get the corresponding complementary permutation. The complement of an up-down permutation is always a down -up permutation and vice versa. The figure
Thus provides for each a bijection between the set of up-down permutations and the amount of down -up permutations dar.
Number
Recursive representation
Based on the above symmetry there are as many up-down- like -down -up permutations. After these two quantities are disjoint, we should restrict ourselves in the count on one of two types. Now denotes the number of down -up permutations of length, and the number of down -up permutations of length that begin with the number, then:
The numbers are called odd, even (positive ) Euler numbers, the numbers are also called Entringen numbers ( sequence A008282 in OEIS ). This gives each of the down -up permutations of length and number of starts by adding, in an up -down permutation of length at most begins with the number, all the numbers from to incremented by one and the number appends the front. After each up-down permutation produced by vertical reflection of a down -up permutation, one obtains with the number and the recurrence
Is set with and for all. This recurrence allows to
Simplify. According mirrored recurrences can also be the number of up-down permutations that begin with the number, derive ( sequence A010094 in OEIS ).
Explicit representation
By resolution of recurrences is now achieved for the number of up-down or down -up permutations of odd length, the explicit sum representation
And straight for the number of up-down or down -up permutations of length the corresponding representation
Overall, one obtains for the number of up-down or down -up permutations of the sequence
And for the total number of alternating permutations of length result
Correspondence to binary trees
Binary trees are considered below, the nodes are labeled with the first natural number. A binary tree is called full if every node is either two or no child nodes. In a partially ordered binary tree all nodes are labeled such that the number of a parent node is always greater than the number of child nodes. Each up-down permutation of odd length now corresponds to a full, partially ordered binary tree with nodes. To construct this correspondence, choose the largest number as the root node of the tree and look at the Teilpermutationen
Left and right of this figure. The two Teilpermutationen are now back up-down permutations each of a subset of the numbers. Of these Teilpermutationen can now again the largest element in each case are selected and recursively a full, partially ordered binary tree are constructed in this way ( see figure). The recursive structure of binary trees, you can now take advantage of in order to derive further recurrences. The root node must have an even index, so that the left subtree and the right subtree node node has. Now there are exactly ways to select the numbers of the left subtree, so that the remaining numbers must be in the right subtree. Substituting, it follows for the number of up-down permutations of odd length, the recurrence
With starting value. Each up-down permutation straight length corresponds to a nearly full, partially ordered binary tree with nodes, in which only the most standing right leaf of the tree is missing. For the number of up-down permutations of even length to obtain the corresponding recurrence
With starting value. Similar to these two cases corresponds to each down -up permutation a with respect to the inverted order partially ordered binary tree is full and even length almost full with an odd length. Due to the mirror symmetry, one obtains for the total number of alternating permutations of length, the recurrence
And after setting the discrete convolution
Generating functions
Differential equation
The exponential generating function of the sequence
Satisfies the ordinary differential equation
With the initial condition, as can be recalculated by employing the above recurrence. By separation of variables, the solution of this initial value problem is obtained as
This classic result of analytic combinatorics, from 1881, goes back to the French mathematician André Désiré.
Maclaurin series
The figures are given for straight Sekantenzahlen and also occur in the Maclaurin series of Sekansfunktion
, while the number for odd numbers are also called tangent and in the series development of the tangent function
Occur. The numbers in doing so are closely related to the Bernoulli numbers.
Asymptotics
For the proportion of alternating permutations in the set of all permutations is valid for asymptotically
This percentage corresponds to the probability that a ( uniformly distributed ) random permutation of length alternation.