Alternating permutation
An alternating permutation of the set \{1, 2, \dots, n\} is a permutation \pi = \pi_1 \pi_2 \dots \pi_n in which the inequalities between consecutive terms alternate throughout, either starting with a descent (down-up alternating: \pi_1 > \pi_2 < \pi_3 > \pi_4 < \dots) or a rise (up-down alternating: \pi_1 < \pi_2 > \pi_3 < \pi_4 > \dots).[1] These are also known as zigzag permutations due to their oscillating pattern when plotted.[1] The number of alternating permutations of each type on n elements is given by the Euler zigzag number E_n, which counts both down-up and up-down varieties separately but symmetrically.[1] These numbers arise as the coefficients in the Taylor series expansion \sum_{n=0}^\infty E_n \frac{x^n}{n!} = \sec x + \tan x, connecting them to trigonometric functions and the (unsigned) Euler numbers.[1] For small n, the values are E_1 = 1, E_2 = 1, E_3 = 2, E_4 = 5, E_5 = 16, and E_6 = 61.[1] Alternating permutations were first investigated by Leonhard Euler in the mid-18th century as part of his work on Euler-Bernoulli numbers and series expansions, though a complete enumeration was provided by Désiré André in 1879 using a bijection with certain lattice paths.[1] They play a central role in enumerative combinatorics, with asymptotic estimates showing E_n \sim \frac{4}{\pi} \left( \frac{2}{\pi} \right)^n n! as n \to \infty.[1] Beyond enumeration, alternating permutations appear in diverse areas, including the structure of complete binary increasing trees, the volumes of certain polytopes like the zigzag order polytope, and the analysis of longest alternating subsequences in random permutations from the symmetric group S_n, where the expected length is asymptotically \frac{4n+1}{6}.[1][2] Generalizations, such as k-alternating permutations requiring larger jumps of at least k in the alternating pattern, extend these concepts to broader permutation classes.[2]Definitions
Up-Down Permutations
A permutation \pi of = \{1, 2, \dots, n\} is an up-down alternating permutation if it satisfies \pi(1) < \pi(2) > \pi(3) < \pi(4) > \cdots for all relevant consecutive positions up to n-1, with the inequality directions alternating and starting with an ascent.\] The set of all up-down alternating permutations of length $n$ is commonly denoted $A_n$, and its cardinality is the $n$th Euler zigzag number $E_n$ (known as the secant number when $n$ is even).\[ For n = 0, there is exactly one such permutation, the empty permutation.$$] Representative examples illustrate the structure for small values of n. For n=1, the sole up-down alternating permutation is $1. For n=2, it is $1\, 2. For n=3, the up-down alternating permutations are $1\, 3\, 2 and $2\, 3\, 1.[$$Down-Up Permutations
A down-up alternating permutation (also known as a reverse alternating permutation) of the set = \{1, 2, \dots, n\} is a permutation \pi = \pi_1 \pi_2 \dots \pi_n satisfying \pi_1 > \pi_2 < \pi_3 > \pi_4 < \dots for $1 \leq i \leq n-1, where the inequalities alternate starting with a descent. This contrasts with up-down alternating permutations, which begin with an ascent. The set of all down-up alternating permutations of $$ is often denoted B_n, and its cardinality |B_n| is the nth Euler zigzag number E_n, which coincides with the number of up-down alternating permutations; when n is odd, E_n is known as the nth Euler tangent number.[3] For n = 0, there is exactly one such permutation, the empty permutation.[4] There exists a simple bijection between the sets of up-down and down-up alternating permutations of $$. Specifically, for an up-down permutation \pi, the map \rho(i) = n + 1 - \pi(i) (the complement map) produces a down-up permutation \rho, and this correspondence is bijective since applying the map twice yields the identity.[3] This bijection flips all comparisons (< becomes > and vice versa), thereby converting the starting ascent of an up-down permutation to a starting descent in the down-up case.[1] Examples of down-up alternating permutations for small n illustrate the pattern. For n=1, the only permutation is (1). For n=2, it is (2,1). For n=3, the two permutations are (2,1,3) and (3,1,2). These satisfy the required inequalities: for (2,1,3), $2 > 1 < 3; for (3,1,2), $3 > 1 < 2.[5]Historical Background
Early Contributions
The early mathematical investigation of alternating permutations originated in the 18th century through Leonhard Euler's analytical work on zigzag numbers, which emerged as coefficients in the Taylor series expansions of the secant and tangent functions. Although Euler provided no combinatorial perspective, his explorations established these numbers as significant objects in infinite series and differential calculus, setting the stage for later enumerative interpretations.[1] In the late 19th century, Désiré André made pivotal contributions by formally defining alternating permutations and resolving key enumeration problems. In a 1879 note in Comptes Rendus, André first linked the zigzag numbers to permutations combinatorially. This was expanded in his 1881 paper "Sur les permutations alternées," where he determined the number of up-down permutations of 2n+1 elements, demonstrating that it equals the (2n+1)th tangent number, thereby offering the first combinatorial realization of these zigzag numbers.[6][5] André's advancements directly extended Euler's foundational results, bridging analytical series to discrete permutation structures within enumerative combinatorics. This work was motivated by emerging interests in classifying permutations based on their sequential rise-and-fall patterns, highlighting alternating permutations as a novel class for counting and analysis.[1]Modern Developments
In the late 20th and early 21st centuries, Richard Stanley provided comprehensive surveys of alternating permutations, highlighting their connections to various combinatorial structures such as posets, binary trees, and Young tableaux.[1] His 1986 Enumerative Combinatorics, Volume 1, established foundational links, including the enumeration of orbits in the partition poset \Pi_n equaling the Euler number E_{n-1}, while later works like the 2009 survey expanded on bijections to complete increasing binary trees and standard Young tableaux of zigzag shapes.[7][1] These overviews underscored the interdisciplinary reach, with the Möbius function of the poset B_{n,2} yielding (-1)^{\lceil n/2 \rceil} E_n.[1] During the 1990s, significant bijections emerged connecting alternating permutations to increasing binary trees and noncrossing partitions. A 1994 bijection by Kuznetsov, Pak, and Postnikov mapped alternating permutations of odd length to complete increasing binary trees, preserving the Euler numbers E_n, with further elaboration by Pak in 2000 linking these trees to Entringer numbers and referencing Knuth's foundational work on permutation-tree correspondences.[8] Concurrently, Simion and Sundaram's work around 1992 introduced simsun permutations, a class enumerated by Euler numbers and related to alternating permutations through connections to noncrossing partitions and alternating sign matrices, establishing enumerative equivalences via descent sets and encodings. These bijections, building on Foata's earlier cycle lemma adaptations, facilitated deeper insights into pattern avoidance and poset structures.[1] Key advancements include the bijections by Foata and Schützenberger in the 1970s, which related alternating permutations to André permutations (a variant introduced by them), with cd-index refinements developed in subsequent works such as those by Purtill in the 1990s. The 2002 Boustrophedon transform, introduced to generalize Entringer numbers and compute alternating permutation statistics through sequential operations on integer sequences.[1][9] Post-2000 research focused on algorithmic efficiency, with Marchal's 2012 algorithm enabling uniform random generation of alternating permutations in O(n \log n) time using a rejection-based quicksort variant, improving upon prior quadratic methods.[10] Alternating permutations also found connections to statistical mechanics through alternating sign matrices (ASMs), which generalize permutation matrices and enumerate configurations in the six-vertex model.[11] Post-2000 developments, including limit shape analyses and polytope volumes for ASMs, revealed asymptotic behaviors akin to those in dimer models, with the number of ASMs of order n given by \prod_{k=0}^{n-1} \frac{(3k+1)!}{(n+k)!}, linking back to Euler zigzags via refinements.[1][11] These ties have influenced studies in integrable systems and random matrix theory.Enumeration
Euler Zigzag Numbers
The Euler zigzag numbers, denoted E_n and also known as the Euler up/down numbers or André numbers, count the number of up-down alternating permutations of the set = \{1, 2, \dots, n\}, which satisfy \pi(1) < \pi(2) > \pi(3) < \pi(4) > \cdots.[1] By the involution that maps \pi_i to n+1 - \pi_i, which reverses all inequalities, the number of down-up alternating permutations (satisfying \pi(1) > \pi(2) < \pi(3) > \pi(4) < \cdots) is also E_n.[1] Consequently, the total number of alternating permutations is $2E_n for n \geq 2.[4] The sequence of Euler zigzag numbers begins E_0 = 1, E_1 = 1, E_2 = 1, E_3 = 2, E_4 = 5, E_5 = 16, E_6 = 61, E_7 = 272, E_8 = 1385, E_9 = 7936, E_{10} = 50521, and is cataloged as OEIS A000111.[4] The even-indexed terms E_{2n} are known as secant numbers, while the odd-indexed terms E_{2n+1} are tangent numbers, reflecting their roles in the Taylor expansions of \sec x and \tan x.[1] Asymptotically, E_n \sim \frac{2^{n+2} n!}{\pi^{n+1}} as n \to \infty.[4]Recurrence Relations
The Euler zigzag number E_n, counting up-down alternating permutations of length n, satisfies several recurrence relations that facilitate their computation. These relations arise both from the exponential generating function \sum_{n=0}^\infty E_n \frac{x^n}{n!} = \sec x + \tan x and from combinatorial decompositions based on the structure of the permutations. The sequence begins with E_0 = 1, E_1 = 1, and subsequent terms are E_2 = 1, E_3 = 2, E_4 = 5, E_5 = 16, which can be verified using the recurrences below.[4] One fundamental recurrence, derived from the differential equation satisfied by the generating function, is E_n = \sum_{i=0}^{n-2} \binom{n-2}{i} E_i E_{n-1-i} for n \geq 2. This relation follows from the second-order differential equation A''(x) = A(x) A'(x) for the exponential generating function A(x), by extracting coefficients via the Cauchy product and integration by parts. For example, applying it to n=3 yields \binom{1}{0} E_0 E_2 + \binom{1}{1} E_1 E_1 = 1 \cdot 1 \cdot 1 + 1 \cdot 1 \cdot 1 = 2, matching E_3 = 2; for n=4, it gives \binom{2}{0} E_0 E_3 + \binom{2}{1} E_1 E_2 + \binom{2}{2} E_2 E_1 = 1 \cdot 1 \cdot 2 + 2 \cdot 1 \cdot 1 + 1 \cdot 1 \cdot 1 = 5, confirming E_4 = 5.[4] An equivalent symmetric form, also obtained from the generating function via differentiation of A'(x) = \sec x \cdot A(x) and coefficient extraction, is $2 E_{n+1} = \sum_{k=0}^n \binom{n}{k} E_k E_{n-k} for n \geq 0. This can be verified for small n: for n=1, the right side is \binom{1}{0} E_0 E_1 + \binom{1}{1} E_1 E_0 = 2, so E_2 = 1; for n=3, it is \binom{3}{0} E_0 E_3 + \binom{3}{1} E_1 E_2 + \binom{3}{2} E_2 E_1 + \binom{3}{3} E_3 E_0 = 2 + 3 + 3 + 2 = 10, yielding E_4 = 5.[1] Combinatorially, for down-up alternating permutations, a recurrence can be obtained by considering the position j of the maximum element n, which must occur in an odd position j (1-based indexing, as odd positions are local maxima). The elements to the left of n form a down-up alternating permutation of length j-1, and the elements to the right form an up-down alternating permutation of length n-j, with the binomial coefficient accounting for choosing the elements in each segment. This yields E_{n+1} = \sum_{\substack{j=1 \\ j \ odd}}^n \binom{n}{j-1} E_{j-1} E_{n-j+1} Wait, actually, the exact form needs adjustment to match the standard; however, an equivalent relation is the symmetric form above. The recurrences for up-down and down-up permutations are structurally identical, as the two classes are equinumerous via the involution of complementing the permutation values (mapping \pi_i to n+1 - \pi_i), which swaps the inequality directions while preserving the alternating property. This equivalence holds for all n \geq 0, though the secant numbers E_{2m} and tangent numbers E_{2m+1} distinguish even and odd cases in generating function contexts.[1]Generating Functions
Ordinary Generating Function
The ordinary generating function for the Euler zigzag numbers E_n, which count the number of up-down alternating permutations of length n, is defined as A(x) = \sum_{n=0}^\infty E_n x^n, where E_0 = 1, E_1 = 1, E_2 = 1, E_3 = 2, E_4 = 5, E_5 = 16, and so on.[1] This power series encodes the enumeration data directly without factorial scaling. The sequence E_n satisfies the recurrence E_n = \sum_{k=0}^{n-2} \binom{n-2}{k} E_k E_{n-1-k} for n \geq 2, with initial conditions E_0 = 1 and E_1 = 1.[4] A closed-form representation of A(x) is given by the infinite continued fraction A(x) = 1 + \cfrac{x}{1 - x - \cfrac{x^2}{1 - 2x - \cfrac{3x^2}{1 - 3x - \cfrac{6x^2}{1 - 4x - \cfrac{10x^2}{1 - 5x - \ddots}}}}} where the linear coefficients are the positive integers $1, 2, 3, 4, \dots and the quadratic coefficients are the triangular numbers $1, 3, 6, 10, \dots. This form was conjectured empirically by Paul D. Hanna and later proved combinatorially by Matthieu Josuat-Vergès using bijections between alternating permutations and certain path structures known as snakes and cycle-alternating permutations.[4] Due to the super-exponential asymptotic growth E_n \sim \frac{2^{n+2} n!}{\pi^{n+1}}, the radius of convergence of A(x) is zero, so it serves primarily as a formal power series for algebraic manipulations rather than for analytic purposes.[1] For comparison, the related exponential generating function \sum_{n=0}^\infty E_n \frac{x^n}{n!} = \sec x + \tan x admits a simple closed form and satisfies the differential equation y' = \frac{1}{2} (y^2 + 1) with y(0) = 1.[1]Exponential Generating Function
The exponential generating function (EGF) for the Euler zigzag numbers E_n, which count the number of up-down alternating permutations of $$, is given by A(x) = \sum_{n=0}^{\infty} E_n \frac{x^n}{n!} = \sec x + \tan x. This closed form arises from the series expansions of the secant and tangent functions, where the coefficients align with the known values of E_n, such as E_0 = 1, E_1 = 1, E_2 = 1, E_3 = 2, and E_4 = 5. Unlike the ordinary generating function, the EGF normalizes by n!, reflecting the labeled nature of permutations as combinatorial objects on finite sets.[1][12] Combinatorially, this EGF emerges from a recursive decomposition of alternating permutations. Specifically, the numbers E_n satisfy the recurrence E_{n+1} = \frac{1}{2} \sum_{k=0}^n \binom{n}{k} E_k E_{n-k} for n \geq 1, with initial conditions E_0 = 1 and E_1 = 1. This relation corresponds to inserting the largest element n+1 into an alternating permutation of $$ in one of two possible positions that preserve the alternating property. In the framework of combinatorial species, this describes the species of up-down alternating permutations as a structure composed of two substructures prefixed by a singleton, with the factor of $1/2 accounting for the decomposition. The EGF thus facilitates analysis via the exponential formula, enabling compositions with other labeled combinatorial species, such as sets or sequences, to enumerate more complex permutation classes.[1][13] Differentiating the EGF yields the differential equation $2 A'(x) = A(x)^2 + 1, \quad A(0) = 1, whose unique power series solution is \sec x + \tan x. This DE provides a differential perspective on the growth of E_n, with applications in asymptotic analysis; for instance, the radius of convergence is \pi/2, reflecting the first singularity of the trigonometric functions. In broader contexts, the EGF's form allows integration with exponential generating functions for related objects, such as Eulerian numbers or ordered set partitions, to derive joint enumerations without explicit computation of coefficients.[1]Explicit Formulas
Formula with Stirling Numbers
The Euler number E_n, counting the number of alternating permutations of , admits an explicit expression in terms of Stirling numbers of the second kind S(n, m), which enumerate the partitions of an n-set into m non-empty unlabeled subsets. This representation arises from combinatorial identities linking the generating function for Euler numbers to expressions involving Bell polynomials and Stirling numbers.[14]Integral and Trigonometric Forms
The Euler numbers E_n, which enumerate alternating permutations, admit explicit integral representations that facilitate asymptotic analysis and connections to special functions. These forms arise from the generating function \sec x + \tan x = \sum_{n=0}^\infty E_n \frac{x^n}{n!}, allowing coefficient extraction via contour integration in the complex plane.[15] A fundamental integral representation is obtained using Cauchy's integral formula applied to the generating function. Specifically, E_n = \frac{n!}{2\pi i} \oint_C \frac{\sec z + \tan z}{z^{n+1}} \, dz, where C is a simple closed contour encircling the origin in the positive direction, within the radius of convergence \pi/2. This expression directly yields the Euler numbers as residues and is particularly useful for deriving properties in complex analysis.[15] For even-indexed Euler numbers (secant numbers), a real integral form involves the hyperbolic secant function: E_{2n} = (-1)^n 2^{2n+1} \int_0^\infty t^{2n} \sech(\pi t) \, dt, \quad n = 0, 1, 2, \dots. This representation links the secant numbers to moments of the sech distribution and enables evaluation through Fourier transforms or other analytic methods.[15] Additional trigonometric integral forms for secant numbers derive from the half hyperbolic secant distribution. One such expression is E_{2r} = (-1)^r \int_0^1 \left[ \frac{2}{\pi} \log \left( \tan \frac{\pi}{4} (x+1) \right) \right]^{2r} \, dx, which expresses E_{2r} as a moment integral involving the logarithm of the tangent function. A related form substitutes the inverse hyperbolic sine: E_{2r} = (-1)^r \int_0^1 \left[ \frac{2}{\pi} \sinh^{-1} \left( \tan \frac{\pi x}{2} \right) \right]^{2r} \, dx. These integrals highlight connections to trigonometric substitutions and are derived from cumulative distribution functions in probability.[16] These integral and trigonometric expressions complement discrete combinatorial formulas by offering continuous analytic tools for studying growth rates and limits of E_n.[15]Algorithms and Constructions
Seidel's Algorithm
Seidel's algorithm provides an iterative method for computing the Euler zigzag numbers E_n, which count the number of alternating permutations of length n, through the construction of a triangular array known as Seidel's triangle. Developed by L. Seidel in 1877, the approach uses Entringer numbers E_{n,k} as entries, where E_{n,k} denotes the number of down-up alternating permutations of [n+1] beginning with k+1. The triangle enables efficient calculation of E_n up to moderate n, as each row builds upon the previous via a simple recurrence relation.[1] The procedure begins with the zeroth row consisting of a single entry E_{0,0} = 1. For n \geq 1, the nth row has n+1 entries starting with E_{n,0} = 0, and subsequent entries are computed using the recurrence E_{n,k} = E_{n,k-1} + E_{n-1,n-k} for $1 \leq k \leq n. This recurrence reflects the combinatorial structure of alternating permutations, where each entry aggregates contributions from adjacent positions in the prior row, corresponding to choices in building the permutation by placing elements while preserving the up-down or down-up pattern. The Euler zigzag number is given by E_n = E_{n,n}, the final entry of the nth row, and the total number of down-up permutations of $$ is the sum of the entries in row n-1. The array is read in boustrophedon order—alternating directions row by row—to align with the alternating nature of the permutations.[1] For example, the first few rows of Seidel's triangle are:- Row 0: 1
- Row 1: 0, 1
- Row 2: 0, 1, 1
- Row 3: 0, 1, 2, 2