Sets of permutations that generate the symmetric group pairwise

The paper contains proofs of the following results. For all sufficiently large odd integers n, there exists a set of ²n−1 permutations that pairwise generate the symmetric group Sn. There is no set of ²n−1+1 permutations having this property. For all sufficiently large integers n with n≡2mod4, there exists a set of ²n−2 even permutations that pairwise generate the alternating group An. There is no set of ²n−2+1 permutations having this property.     

Pattern avoidance for alternating permutations and Young tableaux

We define a class Ln,k of permutations that generalizes alternating (up-down) permutations and give bijective proofs of certain pattern-avoidance results for this class. As a special case of our results, we give bijections between the set A2n(1234) of alternating permutations of length 2n with no four-term increasing subsequence and standard Young tableaux of shape 〈n³〉, and between the set A2n+1(1234) and standard Young tableaux of shape 〈³n−1,2,1〉. This represents the first enumeration of alternating permutations avoiding a pattern of length four. We also extend previous work on doubly-alternating permutations (alternating permutations whose inverses are alternating) to our more general context.The set Ln,k may be viewed as the set of reading words of the standard Young tableaux of a certain skew shape. In the last section of the paper, we expand our study to consider pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape λ/μ whose reading words avoid 213 is a natural μ-analogue of the Catalan numbers (and in particular does not depend on λ, up to a simple technical condition), and that there are similar results for the patterns 132, 231 and 312.     

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.     

Asymptotics of the moments of the number of cycles of a random A-permutation

We consider random permutations uniformly distributed on the set of all permutations of degree n whose cycle lengths belong to a fixed set A (the so-called A-permutations). In the present paper, we establish an asymptotics of the moments of the total number of cycles and of the number of cycles of given length of this random permutation as n → ∞.     

Complete Intersection Problems for Finite Permutations

We find the maximal number of permutations on a set of n elements such that any pair of permutations has at least t common cycles.     

Independent permutations,as related to a problem of Moser and a theorem of Pólya

We introduce the notion of a set of independent permutations on the domain {0, 1,… n ? 1}, and obtain bounds on the size of the largest such set. The results are applied to a problem proposed by Moser in which he asked for the largest number of nodes in a d-cube of side n such that no n of these nodes are collinear. Independent permutations are also related to the problem of placing n non-capturing superqueens (chess queens with wrap-around capability) on an n × n board. As a special case of this treatment we obtain Pólya's theorem that this problem can be solved if and only if n is not a multiple of 2 or 3.     

Generating coset representatives for permutation groups

A group of symmetries can divide the group of all permutations of n marks into equivalence classes of isomorphs; each class is a coset of the group of symmetries. An algorithm for generating a set of isomorph, or coset, representatives is discussed. It can be used when n! is too large for all permutations to be useful, but the number of equivalence classes is manageable. The group of symmetries can be varied to match many natural notions of similarity. A computation on permutations that is restricted to a set of representatives can then concentrate on the essentially different cases.     

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

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.     

Maximal sets of permutations constructed from projective planes

On the set of n²+n+1 points of a projective plane, a set of n²+n+1 permutations is constructed with the property that any two are a Hamming distance 2n+1 apart. Another set is constructed in which every pair are a Hamming distance not greater than 2n+1 apart. Both sets are maximal with respect to the stated property.     

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.     

A polyominoes-permutations injection and tree-like convex polyominoes

Plane polyominoes are edge-connected sets of cells on the orthogonal lattice Z², considered identical if their cell sets are equal up to an integral translation. We introduce a novel injection from the set of polyominoes with n cells to the set of permutations of [n], and classify the families of convex polyominoes and tree-like convex polyominoes as classes of permutations that avoid some sets of forbidden patterns. By analyzing the structure of the respective permutations of the family of tree-like convex polyominoes, we are able to find the generating function of the sequence that enumerates this family, conclude that this sequence satisfies the linear recurrence an=6an−1−14an−2+16an−3−9an−4+2an−5, and compute the closed-form formula an=²n+2−(n³−n²+10n+4)/2.     

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.     

Shortest string containing all permutations

In this paper, we consider the problem of constructing a shortest string of {1,2,…,n} containing all permutations on n elements as subsequences. For example, the string 1 2 1 3 1 2 1 contains the 6 (=3!) permutations of {1,2,3} and no string with less than 7 digits contains all the six permutations. Note that a given permutation, such as 1 2 3, does not have to be consecutive but must be from left to right in the string.We shall first give a rule for constructing a string of {1,2,…,n} of infinite length and the show that the leftmost n²?2n+4 digits of the string contain all the n! permutations (for n≥3). We conjecture that the number of digits f(n) = n²?2n+4 (for n≥3) is the minimum.Then we study a new function F(n,k) which is the minimum number of digits required for a string of n digits to contain all permutations of i digits, i≤k. We conjecture that F(n,k) = k(n?1) for 4≤k ≤n?1.     

Cyclotomic factors of the descent set polynomial

We introduce the notion of the descent set polynomial as an alternative way of encoding the sizes of descent classes of permutations. Descent set polynomials exhibit interesting factorization patterns. We explore the question of when particular cyclotomic factors divide these polynomials. As an instance we deduce that the proportion of odd entries in the descent set statistics in the symmetric group Sn only depends on the number on 1's in the binary expansion of n. We observe similar properties for the signed descent set statistics.     

Probabilistic analysis of an algorithm for the m-planar 3-index assignment problem on single-cycle permutations

Under study is them-planar 3-index assignment problem on single-cycle permutations, which is, in other words, the m peripatetic salesman problem (m-PSP) with different weight functions for each salesman. The problem is NP-hard for m ≥ 1. Some polynomial approximation algorithm is suggested for 1 <m < n/4 with time complexity O(nm ²). The performance ratios of the algorithm are established for the input data (elements of m× n × n matrix) which are assumed to be independent and identically distributed random variables on [a _n , b _n ], where 0 < a _n < b _n . If the distribution function is uniform or dominates (majorizes) the uniform distribution then some conditions on a _n , b _n , and m are obtained for the algorithm to be the asymptotically exact.     

Permutations selon leurs pics,creux, doubles montées et double descentes,nombres d'euler et nombres de Genocchi

We study permutations whose type is given, the type being the sets of the values of the peaks, throughs, doubles rises and double falls. We show that the type of a permutation on n letters is caracterized by a map γ[n]→[n]; the number of possible types is the Catalan number; the number of permutations whose type is associated with γ is the product γ(1)γ(2)·γ(n). This result is a corollary of an explicit bijection between permutations and pairs (γ, ?) where ? is a map dominated by γ. Specifying this bijection tG various classes of permutations provides enumerative formulas for classical numbers, e.g. Euler and Genocchi numbers. It has been proved recently that each enumerative formula of this work is equivalent to a continued fraction expansion of a generating serie.     

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.     

Reconstructing compositions

We consider the problem of reconstructing compositions of an integer from their subcompositions, which was raised by Raykova (albeit disguised as a question about layered permutations). We show that every composition w of n?3k+1 can be reconstructed from its set of k-deletions, i.e., the set of all compositions of n-k contained in w. As there are compositions of 3k with the same set of k-deletions, this result is best possible.     

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.