Universal cycles for permutations

A universal cycle for permutations is a word of length n! such that each of the n! possible relative orders of n distinct integers occurs as a cyclic interval of the word. We show how to construct such a universal cycle in which only n+1 distinct integers are used. This is best possible and proves a conjecture of Chung, Diaconis and Graham.     

Simple permutations and pattern restricted permutations

A simple permutation is one that does not map any non-trivial interval onto an interval. It is shown that, if the number of simple permutations in a pattern restricted class of permutations is finite, the class has an algebraic generating function and is defined by a finite set of restrictions. Some partial results on classes with an infinite number of simple permutations are given. Examples of results obtainable by the same techniques are given; in particular it is shown that every pattern restricted class properly contained in the 132-avoiding permutations has a rational generating function.     

Complementary permutations for abelian groups

Summary LetG be an additively written abelian group and leth: G G be a given function. M. Hall Jr. (1952) and L. Fuchs (1958) already answered the following question. For what functionsh: G G does the functional equation(x) + (x) = h(x) (x G) have as its solution a pair of permutations and ofG? In this paper, we give explicit constructions of such a pair, in a number of cases, in particular whenh(x) x andG is finite. We further determine the finite groupsG where the latter, can be chosen to be automorphisms.In the case whereG is an infinite topological group, we study in how far and can be chosen as Borel measurable permutations, given thath: G G itself is Borel measurable.     

On bijections for pattern-avoiding permutations

By considering bijections from the set of Dyck paths of length 2n onto each of Sn(321) and Sn(132), Elizalde and Pak in [S. Elizalde, I. Pak, Bijections for refined restricted permutations, J. Combin. Theory Ser. A 105 (2004) 207-219] gave a bijection that preserves the number of fixed points and the number of excedances in each σ∈Sn(321). We show that a direct bijection Γ:Sn(321)→Sn(132) introduced by Robertson in [A. Robertson, Restricted permutations from Catalan to Fine and back, Sém. Lothar. Combin. 50 (2004) B50g] also preserves the number of fixed points and the number of excedances in each σ. We also show that a bijection ?^∗:Sn(213)→Sn(321) studied in [J. Backelin, J. West, G. Xin, Wilf-equivalence for singleton classes, Adv. in Appl. Math. 38 (2007) 133-148] and [M. Bousquet-Melou, E. Steingrimsson, Decreasing subsequences in permutations and Wilf equivalence for involutions, J. Algebraic Combin. 22 (2005) 383-409] preserves these same statistics, and we show that an analogous bijection from Sn(132) onto Sn(213) does the same.     

Unfair permutations

We study unfair permutations, which are generated by letting $n$ players draw numbers and assuming that player $i$ draws $i$ times from the unit interval and records her largest value. This model is natural in the context of partitions: the score of the $i$th player corresponds to the multiplicity of the summand $i$ in a random partition, with the roles of minimum and maximum interchanged. We study the distribution of several parameters, namely the position of player $i$, the number of inversions, and the number of ascents. To perform some of the heavy computations, we use the computer algebra package Sigma.     

Ascending sequences in permutations

The problem of the number p(n , r), (1 ?r?n), of permutations on the set {1,…,n} with longest ascending subsequence of given length r is considered. By placing further restrictions on the ascending subsequence, combinatorial identities are obtained which allow the explicit calculation of p(n , r) in some cases.     

Arc permutations

Arc permutations and unimodal permutations were introduced in the study of triangulations and characters. This paper studies combinatorial properties and structures on these permutations. First, both sets are characterized by pattern avoidance. It is also shown that arc permutations carry a natural affine Weyl group action, and that the number of geodesics between a distinguished pair of antipodes in the associated Schreier graph, and the number of maximal chains in the weak order on unimodal permutations, are both equal to twice the number of standard Young tableaux of shifted staircase shape. Finally, a bijection from non-unimodal arc permutations to Young tableaux of certain shapes, which preserves the descent set, is described and applied to deduce a conjectured character formula of Regev.     

Baxter permutations

Chung et al. (1978) have proved that the number of Baxter permutations on [n] is

Viennot (1981) has then given a combinatorial proof of this formula, showing this sum corresponds to the distribution of these permutations according to their number of rises.

Cori et al. (1986), by making a correspondence between two families of planar maps, have shown that the number of alternating Baxter permutations on [2n+δ] is c_n+δc_n where c_n = (2n)!/(n + 1)!n! is the nth Catalan number.

In this paper, we establish a new one-to-one correspondence between Baxter permutations and three non-intersecting paths, which unifies Viennot (1981) and Cori et al. (1986). Moreover, we obtain more precise results for the enumeration of (alternating or not) Baxter permutations according to various parameters. So, we give a combinatorial interpretation of Mallows's formula (1979).     

Counting permutations

We give a direct count of the number of permutations of n objects for which (a) all the cycles have lengths divisible by a fixed integer d, and (b) none of the cycles has length divisible by d.     

On parallel local search for permutations

We investigate some ways in which massively parallel computing devices can be exploited in local search algorithms. We show that the substantial speedups that can be gained from parallel neighbourhood evaluation enables an efficient best improvement local search, and that this in turn enables further speedups through selection and parallel application of a set of independent, improving moves. Our experiments demonstrate a total speedup of up to several hundred times compared to a classical, sequential best improvement search. We also demonstrate how an exchange of good partial solutions between the incumbent and best found solutions improves the efficiency of the Iterated Local Search algorithm.     

Inversion polynomials for 321-avoiding permutations

We prove a generalization of a conjecture of Dokos, Dwyer, Johnson, Sagan, and Selsor giving a recursion for the inversion polynomial of 321-avoiding permutations. We also answer a question they posed about finding a recursive formula for the major index polynomial of 321-avoiding permutations. Other properties of these polynomials are investigated as well. Our tools include Dyck and 2-Motzkin paths, polyominoes, and continued fractions.     

Finite difference calculus for alternating permutations

The finite difference equation system introduced by Christiane Poupard in the study of tangent trees is reinterpreted in the alternating permutation environment. It makes it possible to make a joint study of both tangent and secant trees and calculate the generating polynomial for alternating permutations by a new statistic, referred to as being the greater neighbour of the maximum.     

Five discordant permutations

A permutation π of1,2, …,π is5-discordant if π(i) ≠i, i + 1,i + 2, i + 3, i + 4 modn for 1 ≤i ≤n. A system of recurrences for computing the rook polynomials associated with5-discordant permutations is derived. This system, together with hit polynomials enable the5-discordant permutations to be enumerated.