Permutations, parenthesis words, and Schröder numbers

A different proof for the following result due to West is given: the Schröder number s[inn−1] equals the number of permutations on [1,2,] …, nþat avoid the pattern (3,1,4,2) and its dual (2,4,1,3).     

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.     

On Finite Racks and Quandles

We revisit finite racks and quandles using a perspective based on permutations which can aid in the understanding of the structure. As a consequence we recover old results and prove new ones. We also present and analyze several examples.

Communicated by M. Dixon.     

On types of growth for graph-different permutations

We consider an infinite graph G whose vertex set is the set of natural numbers and adjacency depends solely on the difference between vertices. We study the largest cardinality of a set of permutations of [n] any pair of which differ somewhere in a pair of adjacent vertices of G and determine it completely in an interesting special case. We give estimates for other cases and compare the results in case of complementary graphs. We also explore the close relationship between our problem and the concept of Shannon capacity “within a given type.”     

Erdős–Ko–Rado theorems for permutations and set partitions

Let Sym([n]) denote the collection of all permutations of [n]={1,…,n}. Suppose is a family of permutations such that any two of its elements (when written in its cycle decomposition) have at least t cycles in common. We prove that for sufficiently large n, with equality if and only if is the stabilizer of t fixed points. Similarly, let denote the collection of all set partitions of [n] and suppose is a family of set partitions such that any two of its elements have at least t blocks in common. It is proved that, for sufficiently large n, with equality if and only if consists of all set partitions with t fixed singletons, where B_n is the nth Bell number.     

Permutational isomers on a molecular skeleton with neighbor-excluding ligands

Permutational isomers of ligands substituted on a molecular skeleton are studied under a condition on the ligand placement which excludes a second ligand of the same type at a neighboring skeletal site. General theory to treat such a circumstance is developed to identify a correspondence between isomers and suitable double cosets of groups involving permutations of ligands amongst skeletal sites. Then this theory is illustratively applied for a selection of skeletons, including an experimentally realized hexamalono-buckminsterfullerene skeleton, with 12 ligation locations. An erratum to this article can be found at     

Cross-intersecting families of permutations

For positive integers r and n with r?n, let Pr,n be the family of all sets {(1,y₁),(2,y₂),…,(r,yr)} such that y₁,y₂,…,yr are distinct elements of [n]={1,2,…,n}. Pn,n describes permutations of [n]. For r<n, Pr,n describes permutations of r-element subsets of [n]. Families A₁,A₂,…,Ak of sets are said to be cross-intersecting if, for any distinct i and j in [k], any set in Ai intersects any set in Aj. For any r, n and k?2, we determine the cases in which the sum of sizes of cross-intersecting sub-families A₁,A₂,…,Ak of Pr,n is a maximum, hence solving a recent conjecture (suggested by the author).