The permutations tag has no wiki summary.

**1**

vote

**0**answers

88 views

### Combinatorial design for minimization problem over binary strings

Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...

**6**

votes

**1**answer

208 views

### Primitive, non-2-transitive groups with very large orbitals?

Let $G$ be a transitive permutation group on a set $X$ with $n$ elements. Assume that $G$ is primitive, i.e., $G$ preserves no non-trivial partition of $X$. Assume as well that $G$ is not ...

**17**

votes

**5**answers

493 views

### Why is the right permutohedron order (aka weak order) on $S_n$ a lattice?

This is one of those things I never expected to be hard until I tried to prove it. Why is the right permutohedron order (a.k.a. weak Bruhat order, a.k.a. weak order -- not to be confused with the ...

**0**

votes

**0**answers

48 views

### Cycles of Permutation Related to Rectangular Matrix Transposition

let the entries of a rectangular matrix $A\in\mathbb{C}^{m\times n}; m,n\in\mathbb{N}$ be stored in row-order in a linear vector $v$, i.e. $A_{i,j}=v_{i*m+j}$
Question:
How can the first element ...

**9**

votes

**3**answers

533 views

### How do most people write permutations?

I'd like to know how people prefer to write permutations, or elements of the symmetric group $S_n$ for $n\ge0$.
The most natural way to define a permutation in $S_n$ is as a bijection on the set ...

**0**

votes

**1**answer

114 views

### Permutations of letters under some conditions

Let $W(p,q,r,s)$ be the number of permutations of the letters which satisfy the following conditions :
Condition 1 : The letters are consist of $P,Q,R,S$.
Condition 2 : The number of letter ...

**10**

votes

**1**answer

176 views

### Effective Camille Jordan

It is a well-known (and frequently used) theorem of C. Jordan that a proper subgroup $H$ of a finite group $G$ can not intersect every conjugacy class. This is used most frequently for $G=S_n.$ Now, ...

**6**

votes

**1**answer

218 views

### Unimodality of length of longest increasing subsequence

For $w \in S_n$, the symmetric group on $n$ letters, let $\mathrm{is}(w)$ denote the length of the longest increasing subsequence of $w$. Define, $g_n(p) := |\{w \in S_n \colon \mathrm{is}(w) = p\}|$. ...

**3**

votes

**1**answer

276 views

### Combinatorial Technique Needed

The following problem is likely too special for MO.
However I have no clue how to deal with it, so I'll just try. Nevertheless
it is a combinatorial problem and a discussion about general methods
in ...

**1**

vote

**1**answer

69 views

### Probability of seeing m nonzero bits in off any d consecutive bits in a circle of n bits

Suppose n bits are arranged circularly with given condition that random k of them are 1 and rest 0, and all possible d consecutive bits (total n possibilities) are looked at, what is the probability ...

**1**

vote

**2**answers

106 views

### Draws from multiple non-disjoint urns

Let $C = \{1,...,n\}$ be a set of $n$ colors. Let $S_1,...,S_k$ be non-empty subsets of $C$, that is, $S_i \subseteq C$ for all $i \in \{1,...,k\}$. It is helpful to think of the $S_i$ as urns with ...

**9**

votes

**4**answers

829 views

### Number of Permutations?

Edit: This is a modest rephrasing of the question as originally stated below the fold: for $n \geq 3$, let $\sigma \in S_n$ be a fixed-point-free permutation. How many fixed-point-free permutations ...

**13**

votes

**2**answers

524 views

### Laws of Iterated Logarithm for Random Matrices and Random Permutation

The law of iterated logarithm asserts that if $x_1,x_2,\dots$ are i.i.d $\cal N(0,1)$ random variables and $S_n=x_1+x_2+\cdots+x_n$, then
$$\limsup_{n \to \infty} S_n/\sqrt {n \log \log n} = \sqrt 2, ...

**8**

votes

**1**answer

106 views

### GOE Version of Longest Increasing Subsequence

Let $S_n$ be the symmetric group equipped with uniform measure. For any $\pi\in S_n$, let $L_n=L_n(\pi)$ denote the longest increasing subsequence. A celebrated result of Baik, Deift and Johansson ...

**20**

votes

**1**answer

735 views

### How hard is reconstructing a permutation from its differences sequence?

My interest in combinatorially motivated computational problems led me to search for simple problems that turn out to be computationally hard. In this pursuit, I came up with a problem which I hope is ...

**30**

votes

**2**answers

1k views

### A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself

Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...

**7**

votes

**1**answer

292 views

### Non-enumerative proof that there are many simple permutations?

Terence Tao asked for a non-enumerative proof that a positive proportion of permutations are derangements and got a great answer. Inspired by this, I'd like to ask about another family of ...

**4**

votes

**2**answers

341 views

### The proportion between permutations and derangements.

Denote the number of derangements by $D_N$. It's known that $D_N/N! \rightarrow 1/e$. Therefore $N!/e$ is an approximation for $D_N$.
I'm trying to bound the difference between this approximation and ...

**8**

votes

**0**answers

170 views

### A duality on partial permutations

A partial permutation matrix $\pi$ is one with at most one 1 in any row and column (the rest 0s). Given one, we can cross out to the East and South (but not Southeast) of each 1. Some boxes get ...

**1**

vote

**1**answer

220 views

### The distribution of cycle length in random derangement

It is known that for a fixed x $\in \{0,1,...,N-1\}$, the length of the cycle of x in a random permutation in $S_N$ distributes uniformly in
$\{1, . . . ,N\}$.
My question is regarding the length of ...

**0**

votes

**0**answers

95 views

### Notation for substructure, especially for permutations?

Is there a standard notation that expresses substructure?
The specific case that I care about is the following:
Suppose $\sigma,\tau$ are permutations such that $$\sigma(x)\not=x\implies ...

**8**

votes

**1**answer

188 views

### Permutations of prescribed cycle types that multiply to the identity

Suppose that $\lambda_1,\lambda_2,\lambda_3$ are partititions of $n$. When do there exist permutations $\sigma_1,\sigma_2,\sigma_3 \in S_n$ such that
(1) $\sigma_1\sigma_2\sigma_3$ is the identity;
...

**3**

votes

**0**answers

119 views

### Citation for subset complement result

Let $S=\lbrace s_1,\ldots,s_n \rbrace \subset \lbrace1,\ldots,2n\rbrace$. Consider two operations on $S$: the complement $C(S)=\lbrace 1,\ldots,2n \rbrace \setminus S$ and a reflection* ...

**10**

votes

**0**answers

281 views

### 3D generalizations of permutations, RSK correspondence, contingency tables, etc.

I want to gather facts and questions related to 3D generalizations
of permutations, RSK correspondence, contingency tables,
etc. One reason I am interested in this is because it is potentially
related ...

**6**

votes

**2**answers

335 views

### Distribution of distances in permutations

Let's consider all possible permutations of N numbers. Suppose for each permutation we calculate the sum of absolute differences between consecutive elements. Thus, for (1,2,3) one would have ...

**1**

vote

**1**answer

145 views

### Statistics on Lehmer codes

I am looking at words $\alpha_1 \ldots \alpha_n$, where $\alpha_j \in \{ 1, \ldots, j \}$. Thinking of $\alpha_j$ as a height, these words can be interpreted as left-to-right paths on the positive ...

**5**

votes

**1**answer

432 views

### Number of Permutations with k-inversions and with a single clamped value

This question is cross-posted from math.stackexchange because it might be too technical.
Let $S_n$ be the symmetric group. Recall that the number of inversions of a permutation $\sigma\in S_n$ is the ...

**5**

votes

**2**answers

224 views

### Maximum distance within a subset of permutations

I'm modelling a scheduler that accepts a sequence of requests and outputs a sequence of responses, one response per request. It can partially reorder requests, but only within a finite queue. ...

**1**

vote

**2**answers

211 views

### Is it an integer for all positive integer n ? [closed]

I am trying to figure out if the following expression
$$\frac{(n^2 - n)! }{ n! ((n-1)!)^n }$$
is an integer for all positive integer $n.$
I tried the induction, but induction case is running ...

**2**

votes

**2**answers

181 views

### Graph of $S_n$ with respect to transposition

Consider the graph $G_n$, with $V(G_n) = S_n$ (the set of permutations of a set of size $n$) and having an edge $\sigma\sigma'$ iif $\sigma'$ can be obtained from $\sigma$ by applying a transposition. ...

**5**

votes

**2**answers

389 views

### Permuting Racked Pool Balls with a Single Break

Given reasonable physical assumptions (on friction, collisions, etc.), would it be possible to "break" in a pool game such that when all the balls come to rest, the only difference is that the racked ...

**7**

votes

**4**answers

544 views

### Properties of permutations with unknown pattern avoidance descriptions

Background
Many properties of permutations can be stated in terms of classical patterns.
For example:
a permutation is stack-sortable if and only if it avoids 231 (Knuth 1975)
a permutation ...

**17**

votes

**1**answer

400 views

### Salié permutations and fair permutations

In October 2010, I published a Monthly problem that introduced the concept of a fair permutation, which is a permutation $\pi$ such that for every $i$, either $\pi(i) > i$ and $\pi^{-1}(i) > i$, ...

**0**

votes

**1**answer

101 views

### What are the number of possible ways to build up a certain path?

What are the number of possible ways to build up a certain path?
I was working on a graph problem and was trying to find out in how many possible ways can you build/grow a given path. With ...

**2**

votes

**0**answers

148 views

### Permutations & Balanced Distribution

I would like to implement a form of consistent hashing using a set of permutations.
The rules are as follows:
I have Y=~32 buckets and X items. Buckets may be "alive" or "dead". Items are to be ...

**0**

votes

**0**answers

80 views

### Proving that a property holds for random sequences with given marginal distribution by rearrangement

I am currently investigating the property of random sequences with a special marginal distribution function $F(x)$. Given any random sequence $X_1, X_2, \cdots, X_n$, supposing their joint ...

**3**

votes

**1**answer

237 views

### Distances on generalizations of the symmetric group

I'm a computer vision student, and I'm looking for some symmetric group literature guidance. I'm going to provide some context, and finally ask two questions.
The Cayley distance and other distances ...

**2**

votes

**1**answer

380 views

### inversion vector for multiset permutation

The definition of inversion vector for permutation is very well defined. Each permutation can be mapped to a unique inversion vector. So is there a well defined inversion vector for each multiset ...

**0**

votes

**1**answer

193 views

### Sequence of permutations without a fixed point

I need to find $m$ permutations $A_1,..,A_m$ where each $A_i$ is a permutation on $n$ objects such that any of the compositions $A_jA_{j+1}..A_{j+k}$; $1 \leq j \leq n-1$ and $j+k \leq m$ does not ...

**2**

votes

**1**answer

538 views

### Hamming distance approximates Cayley distance on permutations: citation wanted

Suppose we have two permutations x and y, represented as rank vectors. The Hamming distance between them is the number of entries in the two vectors which disagree. The Cayley distance is the minimum ...

**3**

votes

**1**answer

597 views

### Probabilty of two permutations having common elements?

What is the probability of two permutations on set X of size m (i.e. |X|=m) having at least n points of intersection? By this I mean that if two permutations, which I'll call g(x) and h(x), map a ...

**10**

votes

**1**answer

610 views

### Sliding blocks puzzle

Consider a 'game' played on a subset $S$ of an $n^2$ square grid as follows. There are 3 types of pieces, each occupying a square of $S$, 1 green, some red and the rest are blue, a move consists of ...

**10**

votes

**1**answer

435 views

### Analogues of the Knuth and Forgotten equivalences on permutations: have they been studied?

Consider a totally ordered alphabet $A$ of $n$ letters. Let $W$ be the set of all words over $A$ which have no two letters equal. Then, for example, we can define the Knuth equivalence on $W$ as the ...

**2**

votes

**1**answer

187 views

### perfect shuffle of 2n cards

permutation is given by f(i) = 2i if i<=n and 2(i-n)-1 if i>n
where i denotes the position of cards.
eg pack of cards (1,2,3,4)-->(3,1,4,2)
Basically trying to find the multiplicative order of 2 ...

**3**

votes

**0**answers

91 views

### Permutation function repeated application

Suppose we have a function that permutes a string of symbols according to a rule that we define recursively
$f(s_1s_2s_3s_4s_5...)$ = $f(s_1s_3s_5...)+f(s_2s_4s_6...)$ with $f(s_1)=s_1$ (plus denotes ...

**6**

votes

**0**answers

195 views

### Counting Selections of Entries such having an Extremal Permutation of length n^2+1

Let $S_{n^2+1}$ be permutations of length $n^2+1$. By Erdos-Szekeres Theorem. any $s \in S_{n^2+1}$ would have a monotone subsequence(increasing or decreasing)of length $n+1$.
Say a permutation $s$ of ...

**1**

vote

**1**answer

160 views

### Sequence of transpositions that generates the set of permutations

So I think it's possible to create an infinite sequence of transpositions T = { ti, i ≥ 2 ...

**6**

votes

**2**answers

491 views

### Two groups acting on a set.

Suppose we are given a set S of points on which two different groups G and G' (given by sets of generating permutations) act. Is there an efficient algorithm for finding generators the largest pair ...

**1**

vote

**2**answers

269 views

### Complement to part of a permutation matrix

Consider a rectangular $(m \times n)$ matrix $\underline E_1$ with $m < n$ that has only $0$ or $1$ entries. It has exactly one $1$ entry in each row and not more than one $1$ entry in each column. ...

**17**

votes

**4**answers

1k views

### An n!xn! determinant.

Let us consider the matrix $A$ with its rows and columns enumerated by the elements of $S_n$ with $A_{\sigma\tau}=x^{c(\sigma\tau^{-1})}$ where $c()$ is the number of cycles in a permutation's ...