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.     

Indecomposable permutations, hypermaps and labeled Dyck paths

Hypermaps were introduced as an algebraic tool for the representation of embeddings of graphs on an orientable surface. Recently a bijection was given between hypermaps and indecomposable permutations; this sheds new light on the subject by connecting a hypermap to a simpler object. In this paper, a bijection between indecomposable permutations and labeled Dyck paths is proposed, from which a few enumerative results concerning hypermaps and maps follow. We obtain for instance an inductive formula for the number of hypermaps with n darts, p vertices and q hyperedges; the latter is also the number of indecomposable permutations of Sn with p cycles and q left-to-right maxima. The distribution of these parameters among all permutations is also considered.     

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

Bruhat intervals as rooks on skew Ferrers boards

We characterise the permutations π such that the elements in the closed lower Bruhat interval [id,π] of the symmetric group correspond to non-taking rook configurations on a skew Ferrers board. It turns out that these are exactly the permutations π such that [id,π] corresponds to a flag manifold defined by inclusions, studied by Gasharov and Reiner.Our characterisation connects the Poincaré polynomials (rank-generating function) of Bruhat intervals with q-rook polynomials, and we are able to compute the Poincaré polynomial of some particularly interesting intervals in the finite Weyl groups An and Bn. The expressions involve q-Stirling numbers of the second kind, and for the group An putting q=1 yields the poly-Bernoulli numbers defined by Kaneko.     

The Möbius function of separable and decomposable permutations

We give a recursive formula for the Möbius function of an interval [σ,π] in the poset of permutations ordered by pattern containment in the case where π is a decomposable permutation, that is, consists of two blocks where the first one contains all the letters 1,2,…,k for some k. This leads to many special cases of more explicit formulas. It also gives rise to a computationally efficient formula for the Möbius function in the case where σ and π are separable permutations. A permutation is separable if it can be generated from the permutation 1 by successive sums and skew sums or, equivalently, if it avoids the patterns 2413 and 3142.We also show that the Möbius function in the poset of separable permutations admits a combinatorial interpretation in terms of normal embeddings among permutations. A consequence of this interpretation is that the Möbius function of an interval [σ,π] of separable permutations is bounded by the number of occurrences of σ as a pattern in π. Another consequence is that for any separable permutation π the Möbius function of (1,π) is either 0, 1 or −1.     

Gray Codes,Loopless Algorithm and Partitions

The generation of efficient Gray codes and combinatorial algorithms that list all the members of a combinatorial object has received a lot of attention in the last few years. Knuth gave a code for the set of all partitions of [n] = {1,2,...,n}. Ruskey presented a modified version of Knuth’s algorithm with distance 2. Ehrlich introduced a looplees algorithm for the set of the partitions of [n]; Ruskey and Savage generalized Ehrlich’s results and introduced two Gray codes for the set of partitions of [n]. In this paper, we give another combinatorial Gray code for the set of the partitions of [n] which differs from the aforementioned Gray codes. Also, we construct a different loopless algorithm for generating the set of all partitions of [n] which gives a constant time between successive partitions in the construction process.      

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.     

Signatures of Strings

The parity of a permutation π can be defined as the parity of the number of inversions in π. The signature ε(π) of π is an encoding of the parity in a multiplicative group of order 2: ε(π) = (?1)^inv(π). It is also well known that half of the permutations of a finite set are even and half are odd. In this paper, we explore the natural notion of parity for larger moduli; that is, we define the m-signature of a permutation π to be the number of inversions of π, reduced modulo m. Unlike with the 2-signatures of permutations of sets, the m-signatures of the permutations of a multiset are not typically equi-distributed among the modulo m residue classes, though the distribution is close to uniform. We present a recursive method of calculating the distribution of m-signatures of permutations of a multiset, develop properties of this distribution, and present sufficient conditions for the distribution to be uniform.     

Counting Simsun Permutations by Descents

We count in the present work simsun permutations of length n by their number of descents. Properties studied include the recurrence relation and real-rootedness of the generating function of the number of n-simsun permutations with k descents. By means of generating function arguments, we show that the descent number is equidistributed over n-simsun permutations and n-André permutations. We also compute the mean and variance of the random variable X _n taking values the descent number of random n-simsun permutations, and deduce that the distribution of descents over random simsun permutations of length n satisfies a central and a local limit theorem as n ?? +???.     

On binary reflected Gray codes and functions

The binary reflected Gray code function b is defined as follows: If m is a nonnegative integer, then b(m) is the integer obtained when initial zeros are omitted from the binary reflected Gray code of m.This paper examines this Gray code function and its inverse and gives simple algorithms to generate both. It also simplifies Conder's result that the jth letter of the kth word of the binary reflected Gray code of length n is

     

Coding with injections

A permutation code of length n and minimum distance d is a set Γ of permutations from some fixed set of n symbols such that the Hamming distance between any distinct ${u,v \in \Gamma}$ is at least d. As a generalization, we introduce the problem of packing injections from an m-set, m ≤?n, sometimes called m-arrangements, relative to Hamming distance. We offer some preliminary coding-theoretic bounds, a few design-theoretic connections, and a short discussion on possible applications.     

The maximal-inversion statistic and pattern-avoiding permutations

We define a new combinatorial statistic, maximal-inversion, on a permutation. We remark that the number M(n,k) of permutations in S_n with k maximal-inversions is the signless Stirling number c(n,n−k) of the first kind. A permutation π in S_n is uniquely determined by its maximal-inversion set . We prove it by making an algorithm for retrieving the permutation from its maximal-inversion set. Also, we remark on how the algorithm can be used directly to determine whether a given set is the maximal-inversion set of a permutation. As an application of the algorithm, we characterize the maximal-inversion set for pattern-avoiding permutations. Then we give some enumerative results concerning permutations with forbidden patterns.     

New permutation statistics: Variation and a variant

For each permutation π we introduce the variation statistic of π, as the total number of elements on the right between each two adjacent elements of π. We modify this new statistic to get a slightly different variant, which behaves more closely like Mahonian statistics such as maj. In this paper we find an explicit formula for the generating function for the number of permutations of length n according to the variation statistic, and for that according to the modified version.     

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.     

Permutation codes with specified packing radius

Most papers on permutation codes have concentrated on the minimum Hamming distance of the code. An (n, d) permutation code (or permutation array) is simply a set of permutations on n elements in which the Hamming distance between any pair of distinct permutations (or codewords) is at least d. An (n, 2e + 1) or (n, 2e + 2) permutation code is able to correct up to e errors. These codes have a potential application to powerline communications. It is known that in an (n, 2e) permutation code the balls of radius e surrounding the codewords may all be pairwise disjoint, but usually some overlap. Thus an (n, 2e) permutation code is generally unable to correct e errors using nearest neighbour decoding. On the other hand, if the packing radius of the code is defined as the largest value of e for which the balls of radius e are all pairwise disjoint, a permutation code with packing radius e can be denoted by [n, e]. Such a permutation code can always correct e errors. In this paper it is shown that, in almost all cases considered, the number of codewords in the best [n, e] code found is substantially greater than the largest number of codewords in the best known (n, 2e + 1) code. Thus the packing radius more accurately specifies the requirement for an e-error-correcting permutation code than does the minimum Hamming distance. The techniques used include construction by automorphism group and several variations of clique search They are enhanced by two theoretical results which make the computations feasible.     

An improved list decoding algorithm for the second order Reed–Muller codes and its applications

We propose an algorithm which is an improved version of the Kabatiansky–Tavernier list decoding algorithm for the second order Reed–Muller code RM(2, m), of length n = 2 ^m , and we analyse its theoretical and practical complexity. This improvement allows a better theoretical complexity. Moreover, we conjecture another complexity which corresponds to the results of our simulations. This algorithm has the strong property of being deterministic and this fact drives us to consider some applications, like determining some lower bounds concerning the covering radius of the RM(2, m) code.     

On the Lipschitz constant of the RSK correspondence

We view the RSK correspondence as associating to each permutation π∈Sn a Young diagram λ=λ(π), i.e. a partition of n. Suppose now that π is left-multiplied by t transpositions, what is the largest number of cells in λ that can change as a result? It is natural refer to this question as the search for the Lipschitz constant of the RSK correspondence.We show upper bounds on this Lipschitz constant as a function of t. For t=1, we give a construction of permutations that achieve this bound exactly. For larger t we construct permutations which come close to matching the upper bound that we prove.     

Intersection of Hamming codes avoiding Hamming subcodes

We prove that given a binary Hamming code \({{\mathcal{H}}^n}\) of length n = 2 ^m ? 1, m ≥ 3, or equivalently a projective geometry PG(m ? 1, 2), there exist permutations \({\pi \in \mathcal{S}_n}\) , such that \({{\mathcal{H}}^n}\) and \({\pi({\mathcal{H}}^n)}\) do not have any Hamming subcode with the same support, or equivalently the corresponding projective geometries do not have any common flat. The introduced permutations are called AF permutations. We study some properties of these permutations and their relation with the well known APN functions.     

Self-complementary totally symmetric plane partitions

A totally symmetric plane partition of size n is a plane partition whose three-dimensional Ferrers graph is contained in the box X_n = [1, n] × [1, n] × [1, n] and which is mapped to itself under all permutations of the coordinate axes. The complement of the Ferrers graph of such a plane partition (that is, the set of lattice points in the box X_n that do not belong to the Ferrers graph) is again totally symmetric when viewed from the vantage point of the vertex (n + 1, n + 1, n + 1). A totally symmetric plane partition is self-complementary if it is congruent (in the geometrical sense) to its complement. This cannot occur unless n = 2m is even. In this paper we give several conjectures and a few theorems concerning self-complementary totally symmetric plane partitions. In particular we describe evidence which indicates a close relationship with m by m alternating sign matrices. In an earlier paper we described the close connection between m by m alternating sign matrices and descending plane partitions with no parts exceeding m. We are thus left with three classes of objects which are all apparently interrelated. There remain many unsolved problems, the simplest of which is to prove that any two of the objects have the same cardinality.     

The number of indecomposable codes

A CUPS class of codes is a class that is closed under external direct sums, projections onto components of external direct sums, and formation of equivalent codes. In this paper, formulas are developed to compute the number of indecomposable codes of length n and the number of indecomposable (n, k) codes (both with full support) in a CUPS class $\text{C}$ in terms of the total number of length n and (n, k) codes, respectively, in $\text{C}$. Applications include complete computations of the total number of indecomposable length n codes, the number of indecomposable (n, k) codes, the number of indecomposable (n, k) codes of minimum distance 3 or more, the number of indecomposable length n self-dual codes, and the number of indecomposable length n self-dual codes with minimum distance 4 or more.