Gray code for permutations with a fixed number of cycles

We give the first Gray code for the set of n-length permutations with a given number of cycles. In this code, each permutation is transformed into its successor by a product with a cycle of length three, which is optimal. If we represent each permutation by its transposition array then the obtained list still remains a Gray code and this allows us to construct a constant amortized time (CAT) algorithm for generating these codes. Also, Gray code and generating algorithm for n-length permutations with fixed number of left-to-right minima are discussed.     

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 the snake-in-the-box codes for rank modulation under Kendall’s $$\tau $$-metric

For exactly and efficiently representing and storing data in flash memories, the rank modulation scheme has been presented. In this scheme, Gray codes over the permutations are important, which are used to represent information in flash memories. For a Gray code, two consecutive codewords are obtained using one “push-to-the-top” operation. Specially, a snake-in-the-box code under the Kendall’s \(\tau \)-metric is a Gray code, which is capable of detecting one Kendall’s \(\tau \)-error. In this paper, we consider only the Kendall’s \(\tau \)-metric on the permutations. And we answer one open problem proposed by Horovitz and Etzion. That is, we prove that the length of the longest snake in \(S_{2n+2}\) is longer than the length of the longest snake in \(S_{2n+1}\).     

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.     

The X-Class and Almost-Increasing Permutations

In this paper we give a bijection between the class of permutations that can be drawn on an X-shape and a certain set of permutations that appears in Knuth [4] in connection to sorting algorithms. A natural generalization of this set leads us to the definition of almost-increasing permutations, which is a one-parameter family of permutations that can be characterized in terms of forbidden patterns. We find generating functions for almost-increasing permutations by using their cycle structure to map them to colored Motzkin paths. We also give refined enumerations with respect to the number of cycles, fixed points, excedances, and inversions.     

On distance Gray codes

A Gray code of size n is a cyclic sequence of all binary words of length n such that two consecutive words differ exactly in one position. We say that the Gray code is a distance code if the Hamming distance between words located at distance k from each other is equal to d. The distance property generalizes the familiar concepts of a locally balanced Gray code. We prove that there are no distance Gray codes with d = 1 for k > 1. Some examples of constructing distance Gray codes are given. For one infinite series of parameters, it is proved that there are no distance Gray codes.     

Stability and convergence in discrete convex monotone dynamical systems

We study the stable behaviour of discrete dynamical systems where the map is convex and monotone with respect to the standard positive cone. The notion of tangential stability for fixed points and periodic points is introduced, which is weaker than Lyapunov stability. Among others we show that the set of tangentially stable fixed points is isomorphic to a convex inf-semilattice, and a criterion is given for the existence of a unique tangentially stable fixed point. We also show that periods of tangentially stable periodic points are orders of permutations on n letters, where n is the dimension of the underlying space, and a sufficient condition for global convergence to periodic orbits is presented.     

Restricted 123-avoiding Baxter permutations and the Padovan numbers

Baxter studied a particular class of permutations by considering fixed points of the composite of commuting functions. This class is called Baxter permutations. In this paper we investigate the number of 123-avoiding Baxter permutations of length n that also avoid (or contain a prescribed number of occurrences of) another certain pattern of length k. In several interesting cases the generating function depends only on k and is expressed via the generating function for the Padovan numbers.     

Baxter permutations rise again

Baxter permutations, so named by Boyce, were introduced by Baxter in his study of the fixed points of continuous functions which commute under composition. Recently Chung, Graham, Hoggatt, and Kleiman obtained a sum formula for the number of Baxter permutations of 2n ? 1 objects, but admit to having no interpretation of the individual terms of this sum. We show that in fact the kth term of this sum counts the number of (reduced) Baxter permutations that have exactly k ? 1 rises.     

Descent pattern avoidance

We extend the notion of consecutive pattern avoidance to considering sums over all permutations where each term is a product of weights depending on each consecutive pattern of a fixed length. We study the problem of finding the asymptotics of these sums. Our technique is to extend the spectral method of Ehrenborg, Kitaev and Perry. When the weight depends on the descent pattern we show how to find the equation determining the spectrum. We give two length 4 applications. First, we find the asymptotics of the number of permutations with no triple ascents and no triple descents. Second, we give the asymptotics of the number of permutations with no isolated ascents or descents. Our next result is a weighted pattern of length 3 where the associated operator only has one non-zero eigenvalue. Using generating functions we show that the error term in the asymptotic expression is the smallest possible.     

Suballowable sequences and geometric permutations

We define suballowable sequences of permutations as a generalization of allowable sequences. We give a characterization of allowable sequences in the class of suballowable sequences, prove a Helly-type result on sets of permutations which form suballowable sequences, and show how suballowable sequences are related to problems of geometric realizability. We discuss configurations of points and geometric permutations in the plane. In particular, we find a characterization of pairwise realizability of planar geometric permutations, give two necessary conditions for realizability of planar geometric permutations, and show that these conditions are not sufficient.     

On locally balanced gray codes

We consider locally balanced Gray codes.We say that a Gray code is locally balanced if every “short” subword in its transition sequence contains all letters of the alphabet |1, 2,..., n~. The minimal length of these subwords is the window width of the code. We show that for each n ≥ 3 there exists a Gray code with window width at most n + 3?log n?.     

An arithmetic of complete permutations with constraints, I: an exposition of the general theory

We develop an arithmetic of complete permutations of symmetric, integral bases; this arithmetic is comparable to that of perfect systems of difference sets with which there are several interrelations. Super-position of permutations provides the addition of this arithmetic. Addition if facilitated by complete permutations with a certain “splitting” property, allowing them to be pulled apart and reassembled. The split permutations also provide a singular direct product for complete permutations in conjunction with the multiplication (direct product) of the arithmetic which itself derives from that for perfect systems of difference sets.

We pay special attention to complete permutations satisfying constraints both fixed and variable; this is equivalent to embedding partial complete permutations in complete permutations. In the sequel, using this arithmetic, we investigate the spectra of certain constraints with respect to central integral bases which are of interest for the purpose of giving further constructions either of complete permutations with constraints or of irregular, extremel perfect systems of difference sets.     

Spatial random permutations with small cycle weights

We consider the distribution of cycles in two models of random permutations, that are related to one another. In the first model, cycles receive a weight that depends on their length. The second model deals with permutations of points in the space and there is an additional weight that involves the length of permutation jumps. We prove the occurrence of infinite macroscopic cycles above a certain critical density.     

Constructions for Permutation Codes in Powerline Communications

A permutation array (or code) of length n and distance d is a set Γ of permutations from some fixed set of n symbols such that the Hamming distance between each distinct x, y ∈ Γ is at least d. One motivation for coding with permutations is powerline communication. After summarizing known results, it is shown here that certain families of polynomials over finite fields give rise to permutation arrays. Additionally, several new computational constructions are given, often making use of automorphism groups. Finally, a recursive construction for permutation arrays is presented, using and motivating the more general notion of codes with constant weight composition.     

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 a Gray Code for P-Sequences

P-sequences are used for coding binary trees and they are also an alternative representation for well-formed parentheses strings. We present here the first Gray code and loopless generating algorithm for P-sequences, and extend them in a Gray code and a new loopless generating algorithm for well-formed parentheses strings. Ranking and unranking algorithms are also discussed.