# Questions tagged [permutations]

Questions related to permutations, bijections from a finite (or sometimes infinite) set to itself.

367
questions

**3**

votes

**0**answers

47 views

### Conjugacy classes in reductive group under adjoint action of parabolic subgroup

Given a reductive group $G$ over a finite field and a parabolic subgroup $P$ , I wonder what are the orbits in $G$ under the adjoint action of $P$. This should be standard, but I can only find results ...

**-2**

votes

**0**answers

56 views

### Distribution of gaps between uniform random variables

Pick $k$ uniform independent random integers $x_1,\dots,x_k\in\{0,1,\dots,2^t-2,2^t-1\}$ and denote $y_{\sigma(i)}=x_i$ where $\sigma$ is a permutation in $S_n$ such that $y_1\leq y_2\leq\dots\leq y_{...

**1**

vote

**0**answers

52 views

### Untruncate permutohedron of order 5

I would like to understand commutation classes of reduced expressions of the longest element in $S_5$ a little better. For this, it makes sense to look at the permutohedron of order 5. Since I am only ...

**7**

votes

**1**answer

175 views

### Induction step in Bóna and Ehrenborg's proof that the generating function of the alternating runs has -1 as a root of a certain multiplicity

This is a crosspost of a question I asked on Mathematics SE four months ago. Periodically bumping it and placing a bounty on it to attract more attention were to no avail. There are some comments ...

**0**

votes

**0**answers

89 views

### How many Shapes are possible to create using Voxels?

Let's suppose I have Big Cube of x cm by y cm by z cm, simmilar to this one:
This big cube is made of tiny little cubes of t cm.
All of this little cubes are transparent, but some of them are red
...

**18**

votes

**1**answer

597 views

### Why 'excedances' of permutations? [closed]

For a permutation $\pi=\pi_1\pi_2\cdots\pi_n$ written in one-line notation, an index $i$ for which $\pi_i > i$ is usually called an 'excedance.' To me, this seems like a mispelling of what should ...

**0**

votes

**0**answers

41 views

### Expected value of minimal shift in permutations

The following occurred to me when playing a game involving shuffling a deck of cards with my children.
Let $S_n$ denote the set of bijective maps (permutations) $\pi:\{1,\ldots, n\}\to\{1, \ldots, n\}...

**0**

votes

**0**answers

36 views

### How to take into account the properties of $M(n)$ numbers and improve the variance of normal distribution?

It is known the normal approximation to $inv(\pi)$:
$$ \left| P\left( \frac{\mathrm{inv}(\pi)-\frac 12{n\choose 2}}{\sqrt{n(n-1)(2n+5)/72}}\leq x\right)-\Phi(x)\right| \leq \frac{C}{\sqrt{n}}, $$
...

**0**

votes

**0**answers

9 views

### Sampling distribution on permutations with multi-dimensional constraints and nesting

Let $\mathcal{X}$ be some space (for argument's sake, a finite, discrete space of large cardinality), and let $D > 1$ be a positive integer.
For $d = 1, \ldots, D$,
Let $\Phi_d: \mathcal{X} \to ...

**0**

votes

**0**answers

20 views

### Algorithm for sampling stratification-constrained permutations

Let $\mathcal{X}$ be some base space, and let $\mathbf{S} =S_1, \ldots, S_N$ be a cover (not a partition, i.e. they can overlap) of $\mathcal{X}$. I will refer to the $S_i$ as strata, and to the cover ...

**0**

votes

**0**answers

79 views

### A permutation statistic and determinantal identity

I'm trying to read this paper, Total positivity, Grassmannians and networks by Postnikov (https://arxiv.org/abs/math/0609764) and I'm stuck on Lemma 5.1, which is essentially an identity about maximal ...

**11**

votes

**2**answers

392 views

### Common basis for permutation matrices

How can I check whether there exists a common basis with respect to which two matrices 𝐴 and 𝐵 are permutation matrices?
More explicitly, let $A$ and $B$ be two unitary matrices whose eigenvalues ...

**0**

votes

**0**answers

38 views

### Labeling points of grid $\mathbb N^k$ by subsets according to some permutation group, “global” upper bound for the sets that could appear

Let $G \le S_n$ be a finite permutation group with generators $g_1, \ldots, g_k$. We look at the action of $G$ on subsets
with $A^g = \{ \alpha^g : \alpha \in A \}$ for $A \subseteq \Omega$
and $g \...

**7**

votes

**2**answers

367 views

### On a statistic for permutations

Given a permutation $\pi$ we can write $\pi=s_{i_1} ... s_{i_l}$ as a product of simple transpositions $s_i=(i,i+1)$ in a minimal way.
Question 1: Is there an "official" name for the permutation ...

**26**

votes

**1**answer

1k views

### Multiplying all the elements in a group

Let $G = \{ g_i | i = 1, ...,n \}$ be a finite group and denote by $G!$ the multiset consisting of all the products of all different elements of $G$ in any order, that is
$$ G! = [ \prod_i g_{\sigma(i)...

**3**

votes

**0**answers

66 views

### Number of orders of distances between points on a line

Points $a_1, a_2, \dots, a_n$ on a line form a set from $n(n-1)/2$ distances between them. Suppose all that distances are different, numerating them from the shortest to the longest one we obtain some ...

**5**

votes

**1**answer

119 views

### Parity of shuffle permutations

A $(p,q)$-shuffle is a permutation $\sigma$ of the set $\{1, \dots, p, p+1, \dots,p+q\}$ such that $$\sigma(1)<\dots<\sigma(p)$$ and $$\sigma(p+1) < \dots<\sigma(p+q)\,.$$
It is known ...

**3**

votes

**1**answer

264 views

### Permuting $n$ points in a $2$-manifold

Given $n$ points on a connected $2$-manifold $M$, I'd like to consider the homotopy classes of paths that "permute" these points.
Edit (Clarifying what I mean by this):
Given a set of $n$ distinct ...

**1**

vote

**0**answers

170 views

### Combinatorial bijection on monotone sequences

Let $(n),\mu$ be the partition of $n$ define $H_g^{m}((n);\mu)$ count's the number of tuples $(\tau_1,\ldots,\tau_r)$ of transposition in symmetric group $S_n$ with the following conditions
$$ (1,2,\...

**12**

votes

**0**answers

264 views

### How many steps on $S_n$ are required to span $V\wedge V$, $V = K^n$?

Let $A$ be a set of generators of $G=S_n$; assume $e\in A$,
$A=A^{-1}$. Let $V = K^n$, $K$ a field. Consider the natural
action of $G$ on $V$ (namely, $g(e_i) = e_{g(i)}$) and on $W = V\wedge V$
(...

**11**

votes

**1**answer

228 views

### How many steps are required for double transitivity?

Let $A$ be a set of generators of $S_n$, or of a doubly transitive
subgroup of $S_n$. Assume $e\in A$, $A=A^{-1}$. What is the least $k$
such that $A^k$ is doubly transitive as a set? That is, what is ...

**1**

vote

**1**answer

90 views

### Calculating the values of a generalization of binomials to permutations

let $$\Pi\binom{n}{k}:=\mathrm{card}\left( \left\lbrace \lbrace \Pi_1^n\,\cdots\,\Pi_k^n\rbrace\,|\,0\leq \pi_{r,c}\in\sum_{i=1}^k\Pi_i^n\ni\pi_{r,c}\leq 1\right\rbrace\right)$$ be the number of sets ...

**2**

votes

**0**answers

60 views

### The notions of “monomial” and “induced monomial” in representation theory

Let $G$ be a group and let $\rho : G \rightarrow V$ over a finite-dimensional vector space.
A matrix $M \in \mathbb C^{ k \times k }$ is monomial if every row and every of column of that matrix has ...

**2**

votes

**1**answer

111 views

### Minimum local permutation data needed to globally merge locally sorted sequences?

We have $k$ blocks of integer sequences $B_1,\dots,B_k$ where $B_i$ is a sequence $$a_{i,1},\dots,a_{i,n_i}$$ with $a_{i,j}\leq a_{i,j+1}$.
Denote the permutation matrix $M_{\ell,\ell'}$ that merges $...

**1**

vote

**1**answer

99 views

### The least common multiple of all degrees of a finite Coxeter group and indecomposable elements in the generalized cycle decomposition

This question is a follow-up of the previous question and especially the last comment therein.
Let $(W,S)$ be a finite Coxeter system with reflections $T$. Let $\ell_T$ be the reflection length. ...

**3**

votes

**1**answer

184 views

### Minimal neighbor distance in permutations

For any positive integer $n$, let $[n]:=\{1,\ldots,n\}$. Let $S_n$ denote the set of permutations (bijections) $\pi:[n]\to [n]$. For any $n>1$ and $\pi\in S_n$ we let the minimal neighbor distance ...

**2**

votes

**0**answers

85 views

### Number of permutations with precedence constraints : DP case [closed]

I have two sets of balls (blacks and whites), each set is numbered from $1$ to $n$, and all are put in a jar. My precedence constraint is expressed as following : to pick a black ball with index $i$, ...

**1**

vote

**1**answer

73 views

### Expected value of maximal distance between neighbors in permutations

For any positive integer $n$, let $[n]:=\{1,\ldots,n\}$. Let $S_n$ denote the set of permutations (bijections) $\pi:[n]\to [n]$. For any $n>1$ and $\pi\in S_n$ we let the maximal neighbor distance ...

**1**

vote

**0**answers

165 views

### Do functions $f: \mathbb R \to \mathbb R$ with these properties exist?

Basically, I am trying to determine how exactly and in which ways everywhere discontinuous bijections $f: \mathbb R \to \mathbb R$ "behave when they are unusual".
More precisely, I am trying to ...

**0**

votes

**0**answers

100 views

### Combinatorics of merging sequences from multinomial coefficients

If you have $m$ sequences $a_{11},\dots,a_{1n_1}$ through $a_{m1},\dots,a_{mn_m}$ each sorted in ascending order (assume there are no duplicates) then there is an unique way to merge them.
How many ...

**5**

votes

**0**answers

165 views

### Sum over permutations involving sign

The problem is to evaluate the following sum over all permutations $\sigma\in S_{d}$ of $\{1,2,...,d\}$:
$\displaystyle\sum_{\sigma\in S_{d}}\text{sgn}(\sigma)\displaystyle\frac{1}{\prod_{i=1}^{d}(\...

**13**

votes

**2**answers

383 views

### Classification of shod Dyck paths

A sequence $[c_0,c_1,...,c_{n-1}]$ with $n \geq 2$ is called a Dyck path in case $c_{n-1}=1$, $c_i \geq 2$ for $i \neq n-1$ and $c_i-1 \leq c_{i+1}$ for each $i$.
For example the Dyck paths for $n=4$ ...

**3**

votes

**1**answer

2k views

### Number of solutions and minimal clues in Sixy Sudoku

Sixy Sudoku is a variation on Latin squares and traditional sudoku played on a $6 \times 6$ grid with an initial clue of several cells filled in with a subset of the digits $1$–$6$. The task is to ...

**4**

votes

**1**answer

287 views

### Enumerating all permutations that are “square roots” of derangements

Is there an algorithm that enumerates all permutations that are "square roots" of derangements, i.e. permutations that, when applied twice, yield a derangement?
Other information about those kind ...

**12**

votes

**2**answers

893 views

### How rare are unholey permutations?

For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$.
Given a permutation $\pi$ of $[n]$, we define the holeyness $D(\pi)$ of $\pi$ as being $...

**4**

votes

**0**answers

201 views

### How frequent are permutations with small interleaving?

For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$.
Let $\pi$ be a permutation of $[n]$. For simplicity, assume that $\pi$ is an $n$-cycle. ...

**6**

votes

**1**answer

284 views

### How wide is the Birkhoff Polytope?

This question is migrated from MSE where it turned out to be much harder than I thought. I still cannot figure this out. Does anyone have any ideas?
Define the width of a polytope $P \subset \mathbb ...

**2**

votes

**0**answers

181 views

### A conjecture on crossing numbers related to primes

For a permutation $\sigma\in S_n$, its crossing number $\text{cr}(\sigma)$ is the number of pairs $\{i,j\}$ with $i,j\in\{1,\ldots,n\}$ such that
$$i<j\le\sigma(i)<\sigma(j)\ \ \text{or}\ \ \...

**2**

votes

**1**answer

208 views

### Necessary and sufficient condition for $(x_1,…,x_n)$ to be a permutation of $(1,…,n)$ - Part II

This thread is following the question posted here and seeks to find a generalization to the test function used in the previous question i.e. $f_a(x_1, \dotsc,x_n)=(x_1+a)\dotsb(x_n+a)$
At first, I ...

**1**

vote

**1**answer

68 views

### Spectral bound for maximum clique $k(G)$ in a permutation graph

Let $\pi \in S_n$ be an arbitrary permutation. By permutation graph, we refer to a simple graph with nodes $[n]$ and edges that connect pairs of nodes that appear sorted in $\pi$. Formally, $G=(V=[n],...

**19**

votes

**4**answers

1k views

### A necessary and sufficient condition for $(x_1,…,x_n)$ to be a permutation of $(1,…,n)$

Is there an easy proof of the following statement?
$\forall$ $n>0 \in \mathbb N$, $ \exists$ $a\geq0 \in \mathbb N$ such that
for any set of integers $(x_1,...,x_n)$ and $1\leq x_i \leq n$:
$(...

**6**

votes

**1**answer

228 views

### Permutations, skew-symmetric forms and degeneracy

Define a skew-symmetric form $(\cdot,\cdot)$ on $\mathbb{R}^{2k}$ by $$(e_i,e_j) = \begin{cases} 1 &\text{if $i<j$},\\ -1 &\text{if $i>j$},\\ 0 & \text{if $i=j$.}\end{cases}$$ Given ...

**4**

votes

**1**answer

313 views

### Is $(\mathbb{R},+)$ isomorphic to a subgroup of $S_\omega$?

Is $(\mathbb{R},+)$ isomorphic to a subgroup of $S_\omega$, the group of permutations of the set of non-negative integers $\omega$?

**14**

votes

**1**answer

502 views

### Simplicial set of permutations

Let $S_k$ be the set of all permutations of $k+1$ elements $0,1,...,k$. introduce boundary maps $d_i : S_k \rightarrow S_{k-1}$ by deleting from permutation $\eta$ element $\eta(i)$ and monotone ...

**6**

votes

**1**answer

299 views

### Is $|\{(j,k):\ 1\le j<k\le\frac{p-1}2:\ \&\ (j^{16}\ \text{mod}\ p)>(k^{16}\ \text{mod}\ p)\}|$ even for each prime $p\equiv1\pmod {16}$?

In my paper http://arxiv.org/abs/1809.07766, I determined the parity of
$$\left|\left\{(j,k):\ 1\le j<k\le\frac{p-1}2\ \&\ (j^2\ \text{mod}\ p)>(k^2\ \text{mod}\ p)\right\}\right|$$
for any ...

**4**

votes

**2**answers

269 views

### Stationary distribution of a Markov process defined on the space of permutations

Let $S$ be the set of $n!$ permutations of the first $n$ integers. Let $p\in(0,1)$. Consider the Markov Process defined on the elements of $S$.
Let $x\in S$. Choose $1\le i <i+1 < n$ uniformly ...

**7**

votes

**1**answer

334 views

### Identity involving sum over permutations

In some work on QFT the following identity has come up:
$$
\sum_{\sigma \in S_n}\sum_{j=1}^n \left(\sum_{l=1}^j w_{\sigma_l}\right)\prod_{i=1,i\neq j}^{n}\frac{1}{\sum_{l=1}^j z_{\sigma_l}-\sum_{l=1}^...

**1**

vote

**0**answers

20 views

### Do small subsets of $S_n$ subgroups cover almost all permutation configurations of $S_n$?

Given integer $m\in[1,n]$ fix a set $\mathcal T$ of permutations in $S_n$. Then there are subgroups $G_1,\dots,G_m$ of $S_n$ so that $\mathcal T$ is covered by cosets of $G_1,\dots,G_m$.
For ...

**1**

vote

**0**answers

91 views

### Are almost all permutation configurations from $S_n$ covered by small subsets subgroups of $S_n$?

Given integer $m\in[1,n]$ fix a set $\mathcal T$ of permutations in $S_n$. Then there are subgroups $G_1,\dots,G_m$ of $S_n$ so that $\mathcal T$ is covered by cosets of $G_1,\dots,G_m$.
Do we ...

**3**

votes

**1**answer

137 views

### Multiplication in $Z(\mathbb{C}S_n)$ [duplicate]

I am trying to multiply two generators of center $Z(\mathbb{C}[S_n])$ of ring algebra of symmetric group of $n$ elements. We know that these generators are given by sums of conjugacy classes in $S_n,$ ...