Questions tagged [permutations]

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

Filter by
Sorted by
Tagged with
3
votes
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
2answers
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
0answers
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
2answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
1answer
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
1answer
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
4answers
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
1answer
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,$ ...

1
2 3 4 5
8