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.     

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.     

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.     

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).     

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.     

Quasirandom arithmetic permutations

In [J.N. Cooper, Quasirandom permutations, 2002, to appear], the author introduced quasirandom permutations, permutations of Z_n which map intervals to sets with low discrepancy. Here we show that several natural number-theoretic permutations are quasirandom, some very strongly so. Quasirandomness is established via discrete Fourier analysis and the Erd?s-Turán inequality, as well as by other means. We apply our results on Sós permutations to make progress on a number of questions relating to the sequence of fractional parts of multiples of an irrational. Several intriguing open problems are presented throughout the discussion.     

Sequences generating permutations

Linear recurring sequences generating permutations of the elements of a finite ring are introduced and examined. A complete answer to the discussed problems is given for the second-order sequences over Z_M. The possibilities for applications are also discussed.     

Minimal generalized permutations

In this paper, we obtain the number of the minimal generalized permutations on a finite set. Also, we determine the minimal generalized permutations on a setX of cardinality less than or equal to 4.     

On convex permutations

A selection of points drawn from a convex polygon, no two with the same vertical or horizontal coordinate, yields a permutation in a canonical fashion. We characterise and enumerate those permutations which arise in this manner and exhibit some interesting structural properties of the permutation class they form. We conclude with a permutation analogue of the celebrated Happy Ending Problem.     

Generating indecomposable permutations

An indecomposable permutation π on [n] is one such that π([m])=[m] for no m<n. We consider indecomposable permutations and give a new, inclusive enumerative recurrence for them. This recurrence allows us to generate all indecomposable permutations of length n in transposition Gray code order, in constant amortized time (CAT). We also present a CAT generation algorithm for indecomposable permutations which is based on the Johnson-Trotter algorithm for generating all permutations of length n. The question of whether or not there exists an adjacent transposition Gray code for indecomposable permutations remains open.     

On TDP permutations

A permutation :i| _i , 0i<n is called a TDP permutation ifi–a _i j–a _j (modn) fori j. This paper finds all TDP permutations forn15, discusses the method for generating TDP permutations, and finally by applying MLE method obtains a formula for estimating the number of TDP permutations forn> 15.Project supported by National Natural Science Foundation of China.     

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.