Sets of permutations that generate the symmetric group pairwise

The paper contains proofs of the following results. For all sufficiently large odd integers n, there exists a set of ²n−1 permutations that pairwise generate the symmetric group Sn. There is no set of ²n−1+1 permutations having this property. For all sufficiently large integers n with n≡2mod4, there exists a set of ²n−2 even permutations that pairwise generate the alternating group An. There is no set of ²n−2+1 permutations having this property.     

Boltzmann sampling of ordered structures

Boltzmann models from statistical physics, combined with methods from analytic combinatorics, give rise to efficient algorithms for the random generation of combinatorials objects. This paper proposes a Boltzmann sampler for ordered structures constructed with the box operator, which is an extension of the cartesian product. Under an abstract real-arithmetic computation model, our algorithm is of linear complexity for free generation. For generation of objects of a targetted size, provided a small tolerance, the complexity remains linear for many classes of structures. As an illustration we show how to generate alternating permutations, and our implementation makes possible to generate random objects of sizes up to 10⁷ on a standard machine.     

Symmetric Permutations Avoiding Two Patterns

Symmetric pattern-avoiding permutations are restricted permutations which are invariant under actions of certain subgroups of D ₄, the symmetry group of a square. We examine pattern-avoiding permutations with 180° rotational-symmetry. In particular, we use combinatorial techniques to enumerate symmetric permutations which avoid one pattern of length three and one pattern of length four. Our results involve well-known sequences such as the alternating Fibonacci numbers, triangular numbers, and powers of two.     

The Advanced Australian Shuffle

The “classical” Australian under-down shuffle starts with a deck of n cards. Then one proceeds as follows: one card under the deck, one on the table, one under the deck, one on the table, etc. One continues until only one card remains. There is an explicit formula to calculate the number of the card in the original deck that survives, and this is the basis of several mathematical magic tricks.     

Parity Alternating Permutations and Signed Eulerian Numbers

This paper introduces subgroups of the symmetric group and studies their combinatorial properties. Their elements are called parity alternating, because they are permutations with even and odd entries alternately. The objective of this paper is twofold. The first is to derive several properties of such permutations by subdividing them into even and odd permutations. The second is to discuss their combinatorial properties; among others, relationships between those permutations and signed Eulerian numbers. Divisibility properties by prime powers are also deduced for signed Eulerian numbers and several related numbers.     

Combinatorial Hopf algebras, noncommutative Hall-Littlewood functions, and permutation tableaux

We introduce a new family of noncommutative analogues of the Hall-Littlewood symmetric functions. Our construction relies upon Tevlin's bases and simple q-deformations of the classical combinatorial Hopf algebras. We connect our new Hall-Littlewood functions to permutation tableaux, and also give an exact formula for the q-enumeration of permutation tableaux of a fixed shape. This gives an explicit formula for: the steady state probability of each state in the partially asymmetric exclusion process (PASEP); the polynomial enumerating permutations with a fixed set of weak excedances according to crossings; the polynomial enumerating permutations with a fixed set of descent bottoms according to occurrences of the generalized pattern 2-31.     

Alternating permutations and symmetric functions

We use the theory of symmetric functions to enumerate various classes of alternating permutations w of {1,2,…,n}. These classes include the following: (1) both w and w⁻¹ are alternating, (2) w has certain special shapes, such as (m−1,m−2,…,1), under the RSK algorithm, (3) w has a specified cycle type, and (4) w has a specified number of fixed points. We also enumerate alternating permutations of a multiset. Most of our formulas are umbral expressions where after expanding the expression in powers of a variable E, Ek is interpreted as the Euler number Ek. As a small corollary, we obtain a combinatorial interpretation of the coefficients of an asymptotic expansion appearing in Ramanujan's “Lost” Notebook.     

Baxter permutations and plane bipolar orientations

We present a simple bijection between Baxter permutations of size n and plane bipolar orientations with n edges. This bijection translates several classical parameters of permutations into natural parameters of orientations, and has remarkable symmetry properties. By specialising it to Baxter permutations avoiding the pattern 3142, we obtain a bijection with non-separable planar maps, which had been described only in an implicit recursive manner so far (up to simple symmetries). A further specialization yields a bijection between permutations avoiding 3142 and 2413 and series-parallel maps.     

Permutations with extremal number of fixed points

We extend Stanley's work on alternating permutations with extremal number of fixed points in two directions: first, alternating permutations are replaced by permutations with a prescribed descent set; second, instead of simply counting permutations we study their generating polynomials by number of excedances. Several techniques are used: Désarménien's desarrangement combinatorics, Gessel's hook-factorization and the analytical properties of two new permutation statistics “DEZ” and “lec.” Explicit formulas for the maximal case are derived by using symmetric function tools.     

Longest alternating subsequences of k-ary words

Recently, Stanley [Longest alternating subsequences of permutations, preprint, arXiv/0511419v1] studied the length of the longest alternating subsequence of a permutation in the symmetric group, where a sequence a,b,c,d,… is alternating if a>b<c>d<?. In this paper, we extend this result to the case of k-ary words. More precisely, we find an explicit formula for the generating function of the number of k-ary words of length n according to the length of the longest alternating subsequence.     

Pattern avoidance for alternating permutations and Young tableaux

We define a class Ln,k of permutations that generalizes alternating (up-down) permutations and give bijective proofs of certain pattern-avoidance results for this class. As a special case of our results, we give bijections between the set A2n(1234) of alternating permutations of length 2n with no four-term increasing subsequence and standard Young tableaux of shape 〈n³〉, and between the set A2n+1(1234) and standard Young tableaux of shape 〈³n−1,2,1〉. This represents the first enumeration of alternating permutations avoiding a pattern of length four. We also extend previous work on doubly-alternating permutations (alternating permutations whose inverses are alternating) to our more general context.The set Ln,k may be viewed as the set of reading words of the standard Young tableaux of a certain skew shape. In the last section of the paper, we expand our study to consider pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape λ/μ whose reading words avoid 213 is a natural μ-analogue of the Catalan numbers (and in particular does not depend on λ, up to a simple technical condition), and that there are similar results for the patterns 132, 231 and 312.     

The symmetric and unimodal expansion of Eulerian polynomials via continued fractions

This paper was motivated by a conjecture of Brändén [P. Brändén, Actions on permutations and unimodality of descent polynomials, European J. Combin. 29 (2) (2008) 514-531] about the divisibility of the coefficients in an expansion of generalized Eulerian polynomials, which implies the symmetric and unimodal property of the Eulerian numbers. We show that such a formula with the conjectured property can be derived from the combinatorial theory of continued fractions. We also discuss an analogous expansion for the corresponding formula for derangements and prove a (p,q)-analogue of the fact that the (-1)-evaluation of the enumerator polynomials of permutations (resp. derangements) by the number of excedances gives rise to tangent numbers (resp. secant numbers). The (p,q)-analogue unifies and generalizes our recent results [H. Shin, J. Zeng, The q-tangent and q-secant numbers via continued fractions, European J. Combin. 31 (7) (2010) 1689-1705] and that of Josuat-Vergès [M. Josuat-Vergés, A q-enumeration of alternating permutations, European J. Combin. 31 (7) (2010) 1892-1906].     

Generating the alternating group by cyclic triples

It is shown that a collection of circular permutations of length three on an n-set generates the alternating group A_n if and only if the associated graph is connected. It follows that [$\text{1}\text{2}\text{n}$] circular permutations of length three may generateA_n.     

The mathematics of perfect shuffles

There are two ways to perfectly shuffle a deck of 2n cards. Both methods cut the deck in half and interlace perfectly. The out shuffle O leaves the original top card on top. The in shuffle I leaves the original top card second from the top. Applications to the design of computer networks and card tricks are reviewed. The main result is the determination of the group 〈 I, O 〉 generated by the two shuffles, for all n. If 2n is not a power of 2, and if 2n ≠ 12,24, then 〈 I, O 〉 has index 1, 2, or 4 in the Weyl group B_n (the group of all 2ⁿn! signed n × n permutation matrices). If 2n = 2^k, then 〈 I, O 〉 is isomorphic to a semi-direct product of Z₂^k and Z_k. When 2n = 24, 〈 I, O 〉 is isomorphic to a semi-direct product of Z₂¹¹ and M₁₂, the Mathieu group of degree 12. When 2n = 12, 〈 I, O 〉 is isomorphic to a semi-direct product of Z₂⁶ and the group PGL(2,5) of all linear fractional transformations over GF(5).     

On a Family of Conjectures of Joel Lewis on Alternating Permutations

We prove generalized versions of some conjectures of Joel Lewis on the number of alternating permutations avoiding certain patterns. Our main tool is the perhaps surprising observation that a classic bijection on pattern avoiding permutations often preserves the alternating property.     

Counting involutory, unimodal, and alternating signed permutations

In this work we count the number of involutory, unimodal, and alternating elements of the group of signed permutations B_n, and the group of even-signed permutations D_n. Recurrence relations, generating functions, and explicit formulas of the enumerating sequences are given.     

Explicit determination of generalized symmetric and alternating Galois groups

This paper shows a probabilistic algorithm to decide whether the Galois group of a given irreducible polynomial with rational coefficients is the generalized symmetric group C_p?S_m or the generalized alternating group C_p?A_m. In the affirmative case, we give generators of the group with their action on the set of roots of the polynomial.