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.     

Setwise intersecting families of permutations

A family of permutations A⊂Sn is said to be t-set-intersecting if for any two permutations σ,π∈A, there exists a t-set x whose image is the same under both permutations, i.e. σ(x)=π(x). We prove that if n is sufficiently large depending on t, the maximum-sized t-set-intersecting families of permutations in Sn are cosets of stabilizers of t-sets. The t=2 case of this was conjectured by János Körner. It can be seen as a variant of the Deza-Frankl conjecture, proved in Ellis, Friedgut and Pilpel (2011) [3]. Our proof uses similar techniques to those of Ellis, Friedgut and Pilpel (2011) [3], namely, eigenvalue methods, together with the representation theory of the symmetric group, but the combinatorial part of the proof is harder.     

The peak and descent statistics over ballot permutations

A ballot permutation is a permutation π such that in any prefix of π the descent number is not more than the ascent number. By using a reversal-concatenation map, we (i) give a formula for the joint distribution (pk, des) of the peak and descent statistics over ballot permutations, (ii) connect this distribution and the joint distribution (pk, des) over ordinary permutations in terms of generating functions, and (iii) confirm Spiro's conjecture which finds the equidistribution of the descent statistic for ballot permutations and an analogue of the descent statistic for odd order permutations.     

On the minimum number of completely 3-scrambling permutations

A family P={π₁,…,π_q} of permutations of [n]={1,…,n} is completely k-scrambling [Spencer, Acta Math Hungar 72; Füredi, Random Struct Algor 96] if for any distinct k points x₁,…,x_k∈[n], permutations π_i's in P produce all k! possible orders on π_i(x₁),…,π_i(x_k). Let N^*(n,k) be the minimum size of such a family. This paper focuses on the case k=3. By a simple explicit construction, we show the following upper bound, which we express together with the lower bound due to Füredi for comparison.

     

The Möbius function of permutations with an indecomposable lower bound

We show that the Möbius function of an interval in a permutation poset where the lower bound is sum (resp. skew) indecomposable depends solely on the sum (resp. skew) indecomposable permutations contained in the upper bound, and that this can simplify the calculation of the Möbius sum. For increasing oscillations, we give a recursion for the Möbius sum which only involves evaluating simple inequalities.     

Permutations with Low Discrepancy Consecutive k-sums

Consider the permutation π=(π₁,…, π_n) of 1,2,…, n as being placed on a circle with indices taken modulo n. For given kn there are n sums of k consecutive entries. We say the maximum difference of any consecutive k-sum from the average k-sum is the discrepancy of the permutation. We seek a permutation of minimum discrepancy. We find that in general the discrepancy is small, never more than k+6, independent of n. For g= gcd(n,k)>1, we show that the discrepancy is . For g=1 it is more complicated. Our constructions show that the discrepancy never exceeds k/2 by more than 9 for large n, while it is at least k/2 for infinitely many n.We also give an analysis for the easier case of linear permutations, where we view the permutation as written on a line. The analogous discrepancy is at most 2 for all n,k.     

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.     

Patterns in random permutations avoiding the pattern 321

We consider a random permutation drawn from the set of 321 ‐avoiding permutations of length n and show that the number of occurrences of another pattern σ has a limit distribution, after scaling by n^{m + ?} where m is the length of σ and ? is the number of blocks in it. The limit is not normal, and can be expressed as a functional of a Brownian excursion.     

A bijection between permutations and floorplans, and its applications

A floorplan represents the relative relations between modules on an integrated circuit. Floorplans are commonly classified as slicing, mosaic, or general. Separable and Baxter permutations are classes of permutations that can be defined in terms of forbidden subsequences. It is known that the number of slicing floorplans equals the number of separable permutations and that the number of mosaic floorplans equals the number of Baxter permutations [B. Yao, H. Chen, C.K. Cheng, R.L. Graham, Floorplan representations: complexity and connections, ACM Trans. Design Automation Electron. Systems 8(1) (2003) 55-80]. We present a simple and efficient bijection between Baxter permutations and mosaic floorplans with applications to integrated circuits design. Moreover, this bijection has two additional merits: (1) It also maps between separable permutations and slicing floorplans; and (2) it suggests enumerations of mosaic floorplans according to various structural parameters.     

On the complexity of crossings in permutations

We investigate crossing minimization problems for a set of permutations, where a crossing expresses a disarrangement between elements. The goal is a common permutation π^∗ which minimizes the number of crossings. In voting and social science theory this is known as the Kemeny optimal aggregation problem minimizing the Kendall-τ distance. This rank aggregation problem can be phrased as a one-sided two-layer crossing minimization problem for a series of bipartite graphs or for an edge coloured bipartite graph, where crossings are counted only for monochromatic edges. We contribute the max version of the crossing minimization problem, which attempts to minimize the discrimination against any permutation. As our results, we correct the construction from [C. Dwork, R. Kumar, M. Noar, D. Sivakumar, Rank aggregation methods for the Web, Proc. WWW10 (2001) 613-622] and prove the NP-hardness of the common crossing minimization problem for k=4 permutations. Then we establish a 2−2/k-approximation, improving the previous factor of 2. The max version is shown NP-hard for every k≥4, and there is a 2-approximation. Both approximations are optimal, if the common permutation is selected from the given ones. For two permutations crossing minimization is solved by inspecting the drawings, whereas it remains open for three permutations.     

Binomial posets, Möbius inversion, and permutation enumeration

A unified method is presented for enumerating permutations of sets and multisets with various conditions on their descents, inversions, etc. We first prove several formal identities involving Möbius functions associated with binomial posets. We then show that for certain binomial posets these Möbius functions are related to problems in permutation enumeration. Thus, for instance, we can explain “why” the exponential generating function for alternating permutations has the simple form (1 + sin x)/(cos x). We can also clarify the reason for the ubiquitous appearance of e^x in connection with permutations of sets, and of ξ(s) in connection with permutations of multisets.     

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.     

Restricted 132-Alternating Permutations and Chebyshev Polynomials

A permutation is said to be alternating if it starts with rise and then descents and rises come in turn. In this paper we study the generating function for the number of alternating permutations on n letters that avoid or contain exactly once 132 and also avoid or contain exactly once an arbitrary pattern on k letters. In several interesting cases the generating function depends only on k and is expressed via Chebyshev polynomials of the second kind.AMS Subject Classification: 05A05, 05A15, 30B70, 42C05.     

Asymptotic bounds for permutations containing many different patterns

We say that a permutation σ∈Sn contains a permutation π∈Sk as a pattern if some subsequence of σ has the same order relations among its entries as π. We improve on results of Wilf, Coleman, and Eriksson et al. that bound the asymptotic behavior of pat(n), the maximum number of distinct patterns of any length contained in a single permutation of length n. We prove that by estimating the amount of redundancy due to patterns that are contained multiple times in a given permutation. We also consider the question of k-superpatterns, which are permutations that contain all patterns of a given length k. We give a simple construction that shows that Lk, the length of the shortest k-superpattern, is at most . This may lend evidence to a conjecture of Eriksson et al. that .     

Permutations and successions

Let π = (π(1), π(2),…, π(n)) be a permutation on {1, 2, …, n}. A succession (respectively, ¹-succession) in π is any pair π(i), π(i + 1), where π(i + 1) = π(i) + 1 (respectively, π(i + 1) ≡ π(i) + 1 (mod n)), i = 1, 2, …, n ? 1. Let R(n, k) (respectively, $\text{R}{}^1\text{(n, k)}$) be the number of permutations with k successions (respectively, ¹-successions). In this note we determine R(n, k) and $\text{R}{}^1\text{(n, k)}$. In addition, these notions are generalized to the case of circular permutations, where analogous results are developed.     

Product decompositions of the symmetric group induced by separable permutations

In this paper we consider the rank generating function of a separable permutation π in the weak Bruhat order on the two intervals [id,π] and [π,w₀], where w₀=n,n−1,…,1. We show a surprising result that the product of these two generating functions is the generating function for the symmetric group with the weak order. We then obtain explicit formulas for the rank generating functions on [id,π] and [π,w₀], leading to the rank-symmetry and unimodality of the two graded posets.     

Permutations of separable preference orders

The notion of separability is important in economics, operations research, and political science, where it has recently been studied within the context of referendum elections. In a referendum election on n questions, a voter's preferences may be represented by a linear order on the 2ⁿ possible election outcomes. The symmetric group of degree 2ⁿ, S_2ⁿ, acts in a natural way on the set of all such linear orders. A permutation σ∈S_2ⁿ is said to preserve separability if for each separable order ?, σ(?) is also separable. Here, we show that the set of separability-preserving permutations is a subgroup of S_2ⁿ and, for 4 or more questions, is isomorphic to the Klein 4-group. Our results indicate that separable preferences are rare and highly sensitive to small changes. The techniques we use have applications to the problem of enumerating separable preference orders and to other broader combinatorial questions.     

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.     

Multiple cross-intersecting families of signed sets

A k-signed r-set on[n]={1,…,n} is an ordered pair (A,f), where A is an r-subset of [n] and f is a function from A to [k]. Families A₁,…,Ap are said to be cross-intersecting if any set in any family Ai intersects any set in any other family Aj. Hilton proved a sharp bound for the sum of sizes of cross-intersecting families of r-subsets of [n]. Our aim is to generalise Hilton's bound to one for families of k-signed r-sets on [n]. The main tool developed is an extension of Katona's cyclic permutation argument.     

Lambert or Saccheri quadrilaterals as single primitive notions for plane hyperbolic geometry

With the aim of revealing their purely geometric nature, we rephrase two theorems of S. Yang and A. Fang [S. Yang, A. Fang, A new characteristic of Möbius transformations in hyperbolic geometry, J. Math. Anal. Appl. 319 (2006) 660-664] characterizing Möbius transformations as definability results in elementary plane hyperbolic geometry. We show not only that elementary plane hyperbolic geometry can be axiomatized in terms of the quaternary predicates λ or σ, with λ(abcd) to be read as ‘abcd is a Lambert quadrilateral’ and σ(abcd) to be read as ‘abcd is a Saccheri quadrilateral’, but also that all elementary notions of hyperbolic geometry can be positively defined (i.e. by using only quantifiers (∀ and ∃) and the connectives ∨ and ∧ in the definiens) in terms of λ or σ.