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.     

Some highly symmetric authentication perpendicular arrays

A set S of permutations of k objects is -uniform, t-homogeneous if for every pair A, B of t-subsets of the ground set, there are exactly permutations in S mapping A onto B. Arithmetical conditions and symmetries are discussed. We describe the character-theoretic method which is useful if S is contained in a permutation group. A main result is the construction of a 2-uniform, 2-homogeneous set of permutations on 6 objects and of a 3-uniform, 3-homogeneous set of permutations on 9 objects. These are contained in the simple permutation groups PSL ₂(5) and PSL ₂(8), respectively. The result is useful in the framework of theoretical secrecy and authentication (see Stinson 1990, Bierbrauer and Tran 1991).     

Prefix and suffix transreversals on binary and ternary strings

The problem of sorting by a genome rearrangement event asks for the minimum number of that event required to sort the elements of a given permutation. In this paper, we study a variant of the rearrangement event called prefix and suffix transreversal. A transreversal is an operation which reverses the first block before exchanging two adjacent blocks in a permutation. A prefix (suffix) transreversal always reverses and moves a prefix (suffix) of the permutation to another location. Interestingly, we will apply transreversal not on permutations but on strings over an alphabet of fixed size. We determine the minimum number of prefix and suffix transreversals required to sort the binary and ternary strings, with polynomial time algorithms for these sorting problems.     

Compatible additive permutations of finite integral bases

Let be an additive permutation of a finite integral base. It is shown that ifB is symmetric, then there is a unique additive permutation ofB which is compatible with in the sense that ^–1 is also an additive permutation; and that, further, ifB is asymmetric, then there is no additive permutation ofB which is compatible with. Thus, in the symmetric case, there are no additively compatible sets (of permutations) forB of size greater than 3. This contrasts with the situation for completely compatible sets (equivalently, additive sequences of permutations) where for certainB compatible sets of size (resp. length) 4 or less are known, but where nothing is known of sets of greater size (resp. length). It is also noted how this result restricts the possibility of a useful multiplication theorem for the additive analogue of perfect systems of difference sets and graceful graphs.     

Sterling stirling play

In this paper we analyze a recently proposed impartial combinatorial ruleset that is played on a permutation of the set \(\left[ n\right] \). We call this ruleset Stirling Shave. A procedure utilizing the ordinal sum operation is given to determine the nim value of a given normal play position. Additionally, we enumerate the number of permutations of \(\left[ n\right] \) which are \(\mathcal {P}\)-positions. The formula given involves the Stirling numbers of the first-kind. We also give a complete analysis of the Misère version of Stirling Shave using Conway’s genus theory. An interesting by-product of this analysis is insight into how the ordinal sum operation behaves in Misère Play.     

Reconstruction of permutations distorted by reversal errors

The problem of reconstructing permutations on n elements from their erroneous patterns which are distorted by reversal errors is considered in this paper. Reversals are the operations reversing the order of a substring of a permutation. To solve this problem, it is essential to investigate structural and combinatorial properties of a corresponding Cayley graph on the symmetric group Sym_n generated by reversals. It is shown that for any n?3 an arbitrary permutation π is uniquely reconstructible from four distinct permutations at reversal distance at most one from π where the reversal distance is defined as the least number of reversals needed to transform one permutation into the other. It is also proved that an arbitrary permutation is reconstructible from three permutations with a probability p₃→1 and from two permutations with a probability as n→∞. A reconstruction algorithm is presented. In the case of at most two reversal errors it is shown that at least erroneous patterns are required in order to reconstruct an arbitrary permutation.     

On periodicity and low complexity of infinite permutations

We define an infinite permutation as a sequence of reals taken up to value, or, equivalently, as a linear ordering of or of . We introduce and characterize periodic permutations; surprisingly, for each period t there is an infinite number of distinct t-periodic permutations. At last, we study a complexity notion for permutations analogous to subword complexity for words, and consider the problem of minimal complexity of non-periodic permutations. Its answer is not analogous to that for words and is different for the right infinite and the bi-infinite case.     

On generation of permutations through decomposition of symmetric groups into cosets

A hardware-oriented algorithm for generating permutations is presented that takes as a theoretic base an iterative decomposition of the symmetric groupS _n into cosets. It generates permutations in a new order. Simple ranking and unranking algorithms are given. The construction of a permutation generator is proposed which contains a cellular permutation network as a main component. The application of the permutation generator for solving a class of combinatorial problems on parallel computers is suggested.     

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.     

Permutation tableaux and permutation patterns

In this paper we introduce and study a class of tableaux which we call permutation tableaux; these tableaux are naturally in bijection with permutations, and they are a distinguished subset of the -diagrams of Alex Postnikov [A. Postnikov, Webs in totally positive Grassmann cells, in preparation; L. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005) 319-342]. The structure of these tableaux is in some ways more transparent than the structure of permutations; therefore we believe that permutation tableaux will be useful in furthering the understanding of permutations. We give two bijections from permutation tableaux to permutations. The first bijection carries tableaux statistics to permutation statistics based on relative sizes of pairs of letters in a permutation and their places. We call these statistics weak excedance statistics because of their close relation to weak excedances. The second bijection carries tableaux statistics (via the weak excedance statistics) to statistics based on generalized permutation patterns. We then give enumerative applications of these bijections. One nice consequence of these results is that the polynomial enumerating permutation tableaux according to their content generalizes both Carlitz' q-analog of the Eulerian numbers [L. Carlitz, q-Bernoulli and Eulerian numbers, Trans. Amer. Math. Soc. 76 (1954) 332-350] and the more recent q-analog of the Eulerian numbers found in [L. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005) 319-342]. We conclude our paper with a list of open problems, as well as remarks on progress on these problems which has been made by A. Burstein, S. Corteel, N. Eriksen, A. Reifegerste, and X. Viennot.     

The probability of avoiding consecutive patterns in the Mallows distribution

We use combinatorial and probabilistic techniques to study growth rates for the probability that a random permutation from the Mallows distribution avoids consecutive patterns. The Mallows distribution is a q‐analogue of the uniform distribution weighting each permutation π by , where is the number of inversions in π and q is a positive, real‐valued parameter. We prove that the growth rate exists for all patterns and all q > 0, and we generalize Goulden and Jackson's cluster method to keep track of the number of inversions in permutations avoiding a given consecutive pattern. Using singularity analysis, we approximate the growth rates for length‐3 patterns, monotone patterns, and non‐overlapping patterns starting with 1, and we compare growth rates between different patterns. We also use Stein's method to show that, under certain assumptions on q and σ, the number of occurrences of a given pattern σ is well approximated by the normal distribution.     

Block decomposition of permutations and Schur-positivity

The block number of a permutation is the maximum number of components in its expression as a direct sum. We show that, for 321-avoiding permutations, the set of left-to-right maxima has the same distribution when the block number is assumed to be k, as when the last descent of the inverse is assumed to be at position \(n - k\). This result is analogous to the Foata–Schützenberger equidistribution theorem, and implies that the quasi-symmetric generating function of the descent set over 321-avoiding permutations with a prescribed number of blocks is Schur-positive.     

Explicit Formulae for Some Kazhdan-Lusztig Polynomials

We consider the Kazhdan-Lusztig polynomials P _u,v (q) indexed by permutations u, v having particular forms with regard to their monotonicity patterns. The main results are the following. First we obtain a simplified recurrence relation satisfied by P _u,v (q) when the maximum value of v S_n occurs in position n – 2 or n – 1. As a corollary we obtain the explicit expression for P_{e,3 4 ... n 1 2}(q) (where e denotes the identity permutation), as a q-analogue of the Fibonacci number. This establishes a conjecture due to M. Haiman. Second, we obtain an explicit expression for P_{e, 3 4 ... (n – 2) n (n – 1) 1 2}(q). Our proofs rely on the recurrence relation satisfied by the Kazhdan-Lusztig polynomials when the indexing permutations are of the form under consideration, and on the fact that these classes of permutations lend themselves to the use of induction. We present several conjectures regarding the expression for P _u,v (q) under hypotheses similar to those of the main results.     

A new class of libraries

In this paper we give the stationary measure and a sufficient condition of positive recurrence for a new class of linear libraries. These libraries are built by juxtaposing McCabe's libraries and Tsetlins libraries in an appropriate way: Their policy is not classical, by the fact that instead of a circular permutation, ₁ can be the product of several disjoint circular permutations.     

Light tails and the Hermitian dual polar graphs

This paper investigates ciphers where the set of encryption functions is identical to the set of decryption functions, which we call reflection ciphers. Equivalently, there exists a permutation P, named the coupling permutation, such that decryption under k corresponds to encryption under P(k). We study the necessary properties for this coupling permutation. Special care has to be taken of some related-key distinguishers since, in the context of reflection ciphers, they may provide attacks in the single-key setting. We then derive some criteria for constructing secure reflection ciphers and analyze the security properties of different families of coupling permutations. Finally, we concentrate on the case of reflection block ciphers and, as an illustration, we provide concrete examples of key schedules corresponding to several coupling permutations, which lead to new variants of the block cipher prince.     

Decreasing Subsequences in Permutations and Wilf Equivalence for Involutions

In a recent paper, Backelin, West and Xin describe a map φ^* that recursively replaces all occurrences of the pattern k... 21 in a permutation σ by occurrences of the pattern (k−1)... 21 k. The resulting permutation φ^*(σ) contains no decreasing subsequence of length k. We prove that, rather unexpectedly, the map φ^* commutes with taking the inverse of a permutation. In the BWX paper, the definition of φ^* is actually extended to full rook placements on a Ferrers board (the permutations correspond to square boards), and the construction of the map φ^* is the key step in proving the following result. Let T be a set of patterns starting with the prefix 12... k. Let T′ be the set of patterns obtained by replacing this prefix by k... 21 in every pattern of T. Then for all n, the number of permutations of the symmetric group _n that avoid T equals the number of permutations of _n that avoid T′. Our commutation result, generalized to Ferrers boards, implies that the number of involutions of _n that avoid T is equal to the number of involutions of _n avoiding T′, as recently conjectured by Jaggard. Both authors were partially supported by the European Commission's IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe”     

On sorting by 3-bounded transpositions

Heath and Vergara [Sorting by short block moves, Algorithmica 28 (2000) 323-352] proved the equivalence between sorting by 3-bounded transpositions and sorting by correcting skips and correcting hops. This paper explores various algorithmic as well as combinatorial aspects of correcting skips/hops, with the aim of understanding 3-bounded transpositions better.We show that to sort any permutation via correcting hops and skips, ⌊n/2⌋ correcting skips suffice. We also present a tighter analysis of the approximation algorithm of Heath and Vergara, and a possible simplification. Along the way, we study the class H_n of those permutations of S_n which can be sorted using correcting hops alone, and characterize large subsets of this class. We obtain a combinatorial characterization of the set G_n⊆S_n of all correcting-hop-free permutations, and describe a linear-time algorithm to optimally sort such permutations. We also show how to efficiently sort a permutation with a minimum number of correcting moves.     

The Peak Algebra of the Symmetric Group

The peak set of a permutation is the set {i : (i – 1) < (i) > (i + 1)}. The group algebra of the symmetric group S _n admits a subalgebra in which elements are sums of permutations with a common descent set. In this paper we show the existence of a subalgebra of this descent algebra in which elements are sums of permutations sharing a common peak set. To prove the existence of this peak algebra we use the theory of enriched (P, )-partitions and the algebra of quasisymmetric peak functions studied by Stembridge (Trans. Amer. Math. Soc. 349 (1997) 763–788).     

Geometric Permutations

A difference permutation is a structure which serves as an instrument to recognize important properties of permutations. Since special permutations are models for orthoschemes in generalized hyperbolic spaces (Minkowskian spaces) of dimension d there difference permutations give informations on the type of such orthoschemes. In this note with the help of difference permutations especially geometric permutations are explained which describe the structure of the concerning orthoschemes. This knowledge is necessary to count the numbers of orthoscheme types and special chains of orthoschemes as shown in B?hm (http://www.minet.uni-jena.de/preprints/boehm_08/Napiercycles.pdf).     

Forest-Like Permutations

Given a permutation , construct a graph G _π on the vertex set {1, 2,..., n} by joining i to j if (i) i < j and π(i) < π(j) and (ii) there is no k such that i < k < j and π(i) < π(k) < π(j). We say that π is forest-like if G _π is a forest. We first characterize forest-like permutations in terms of pattern avoidance, and then by a certain linear map being onto. Thanks to recent results of Woo and Yong, these show that forest-like permutations characterize Schubert varieties which are locally factorial. Thus forest-like permutations generalize smooth permutations (corresponding to smooth Schubert varieties). We compute the generating function of forest-like permutations. As in the smooth case, it turns out to be algebraic. We then adapt our method to count permutations for which G _π is a tree, or a path, and recover the known generating function of smooth permutations. Received March 27, 2006