# Questions tagged [permutations]

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

409
questions

**5**

votes

**0**answers

140 views

### Can Matsumoto's theorem for the symmetric group be proved using a monovariant?

This is a question that can be asked for any Coxeter group, but for the sake of simplicity I will restrict myself to symmetric groups. Recall the main definitions:
Let $n$ be a nonnegative integer. ...

**6**

votes

**0**answers

96 views

### Distribution of peaks in permutations, after a sorting operation

Let $S_n$ be the set of permutations on $\{1,2,\dotsc,n\}$.
A peak-value of $\pi$ is some $\pi_i$ such that $\pi_{i-1} < \pi_i > \pi_{i+1}$, where $1<i<n$. Let $PV(\pi)$ denote the set of ...

**6**

votes

**2**answers

179 views

### A convolution-type identity for the “major index”

For a permutation $\pi\in\frak{S}_n$, define the number of descents of $\pi$ as $$\text{des}(\pi)=\vert\{i: \pi(i)>\pi(i+1)\}\vert.$$
The following is a well-known (and interesting) identity:
$$\...

**10**

votes

**1**answer

249 views

### When are immanants irreducible?

For a partition $\lambda$ let $\chi_\lambda$ be the corresponding irreducible representation of the symmetric group $S_n$.
Let $\mathrm{Imm}_\lambda(x) = \sum\limits_{\pi \in S_n} \chi_\lambda(\pi) x_{...

**2**

votes

**0**answers

102 views

### Magic squares as sums of permutation matrices

A magic square of size $n$ and sum $k$ is a $n\times n$ matrix with non-negative integer elements, whose rows and columns all sum to $k$. A permutation matrix is a magic square of sum $1$. Every magic ...

**0**

votes

**0**answers

43 views

### Greatest common length of permutation

Given two permutations $\pi_1$ and $\pi_2$ without their cycle decompositions is there
a good method to compute the largest cycle length common between them in their decompositions?
a good method to ...

**1**

vote

**1**answer

122 views

### Matrix reconstruction puzzle

Say a reconstruction of matrix $A$ is $A'$ and it's defined as
$$
A' = PDP^TA
$$
where $P$ is an orthogonal matrix, $D$ is a diagonal binary (1 or 0) matrix. In a trivial case, when all diagonal ...

**-1**

votes

**1**answer

209 views

### Given the index of two permutations, Is there a direct way to compute the index of their composition? [closed]

Suppose you are given two indexed permutations, (7 followed by 4, for instance)
What is the best way to go about finding their composition, given the indices themselves? I'd imagine that the answer ...

**7**

votes

**1**answer

171 views

### Constructing permutations avoiding a pattern

See here for some theory.
It is fairly easy to explicitly generate all permutations of $n$ elements that have a pattern (just begin with the pattern and add the rest in all possible positions), but ...

**4**

votes

**1**answer

241 views

### Is $\prod_{k=1}^nk^{\sigma(k)}$ a square or a cube for some $\sigma\in S_n$?

Note that for any permutation $\sigma\in S_5$ the product $\prod_{k=1}^5k^{\sigma(k)}$ is neither a square nor a cube.
Question. Let $n>5$ be an integer. Is the product $\prod_{k=1}^nk^{\sigma(k)}$ ...

**0**

votes

**0**answers

243 views

### Is there a permutation $\tau\in S_n$ with $\tau(1)^{\tau(2)}+\cdots+\tau(n-1)^{\tau(n)}+\tau(n)^{\tau(1)}$ a square?

Let $n>1$ be an integer, and let $S_n$ be the symmetric group of all the permutatins of $\{1,\ldots,n\}$.
I'm curious whether there is a permutation $\tau\in S_n$ such that
$$\tau(1)^{\tau(2)}+\...

**4**

votes

**1**answer

108 views

### A close reative of “Inflated” Eulerian polynomials

I came across this post Coefficients of the Inflated Eulerian Polynomial by AULI-GRAHAM-SAVAGE. In particular, the polynomials related to descents interested me
$$P_n(x)=\sum_{\pi\in\mathfrak{S}_n}x^{...

**2**

votes

**0**answers

71 views

### Elements of the Hall basis described via permutations

Good morning,
Suppose that $\mathfrak{g}$ is a free graded Lie algebra generated by the elements $1,\dots, n$, i.e. assume that $\mathfrak{g}_1=\mathrm{span}\{1,\dots, n\}$. Let us focus on the Hall ...

**3**

votes

**1**answer

285 views

### Special permutations of $\{1,2,3,\ldots,n\}$

How do you show that number of permutations of $\{1,2,3,\ldots,n\}$ such that image of no two consecutive numbers is consecutive is
$$n! + \sum_{k = 1}^{n}(-1)^k\sum_{i = 1}^{k}\dbinom{k - 1}{i - 1}\...

**0**

votes

**0**answers

23 views

### Permutation realised as Kronecker product of unitary matrices

Under what circumstances can a permutation of a vector $\pmb{v}$ be achieved with the Kronecker product $U \otimes U$ of two unitary matrices? In other words,
$P \, \pmb{v} = \left( U \otimes U \right)...

**15**

votes

**0**answers

306 views

### a Vandermonde-type of determinants summed over permutations

Let $S_n$ be the symmetric group. Consider
$$D:=\sum_{\sigma\in S_n} \text{sgn}(\sigma)\cdot \det\begin{pmatrix}1 & a_{\sigma(1)}-0 & (a_{\sigma(1)}-0)^2 & \cdots & (a_{\sigma(1)}-0)^{...

**0**

votes

**0**answers

30 views

### Unitary transformation equivalent to permutation

Suppose we have a real, symmetric, positive semi-definite matrix $A$ which we flatten into a vector $\mathrm{vec} \left[ A \right]$. I am interested in solutions to the following equations,
$P \ \...

**4**

votes

**1**answer

160 views

### Number of permutations with combinatorial geometric constraints

We are given a $d$-dimensional hypercube $H$, where each vertex is labeled with an integer $\ell\in\{1, 2, \ldots, 2^d\}$. Let $L$ be this labelling.
Question: How many labelling permutations $L'$ of ...

**2**

votes

**2**answers

218 views

### “Haar-like” measure on $S_\omega$

Let $S_\omega$ be the collection of bijections $f:\omega\to \omega$. Endow $\omega$ with the discrete topology and let $S_\omega$ be endowed with the subspace topology of $\omega^\omega$, where $\...

**7**

votes

**2**answers

307 views

### Random permutations without double rises (avoiding consecutive pattern $\underline{123}$)

A permutation avoiding a consecutive pattern $\underline{123}$ is permutation
$\pi = \pi_1 \pi_2 \ldots \pi_n$ with the property that there does not exists $i \in [1, n-2]$
such that $\pi_i < \pi_{...

**6**

votes

**2**answers

326 views

### Rank of $A\otimes B - B\otimes A$

Let $A$, $B\in\mathbb{R}^{n\times n}$ be full-rank random matrices and define the Kronecker products $P=A\otimes B$ and $Q=B\otimes A$. Through example-based examination, I have found that
$\text{rank}...

**5**

votes

**1**answer

144 views

### Dealing cards numbered $1$ to $n$ into piles

Is anything known about the following?
I hold in my hand a shuffled pack of cards numbered $1$ to $n$. One by one, I place them all, face up, on a table in piles. For each card I deal from my hand, ...

**4**

votes

**1**answer

124 views

### An Indepth Look at Isoperimetry in the Cayley Graph Generated by All Transpositions

Let $\Omega_n$ denote the symmetric/permutation group on $n$ objects.
Let $T_n \subseteq \Omega_n$ denote the set of transpositions.
Drop the $n$-subscripts.
Define the Cayley graph $G = (\Omega, E)$ ...

**7**

votes

**1**answer

254 views

### For which $n$ can $S_n$ act transitively on $n+k$ elements?

It is known that the symmetric group $S_n$ can act transitively on $n+1$ elements if and only if $n=5$.
Are there similar classifications for $S_n$ acting transitively on $n+k$ elements, where $k$ is ...

**14**

votes

**2**answers

308 views

### Ehrhart period collapse for $123\ldots k$-avoiding Birkhoff polytope?

For $1 \leq r \leq n$, let $\mathcal{B}^n_r$ denote the polytope of all real matrices
$$ \pi = \begin{pmatrix} \pi_{1,1} & \pi_{1,2} & \cdots & \pi_{1,n} \\
\pi_{2,1} & \ddots & \...

**1**

vote

**1**answer

149 views

### Ordering and place in sets

Given are $2n$ (not necessarily distinct) subsets of the set $\{1,2,\dots,k\}$, with the first $n$ sets containing $1$. For an ordering $\sigma$ of $1,2,\dots,k$, its score is calculated as follows, ...

**13**

votes

**1**answer

708 views

### Two questions on the permutohedron

The $n$-dimensional permutohedron $P_n$ is the polytope given by the convex hull of all the possible permutations of the vector $(1,2,\dots,n+1)\in\mathbb{R}^{n+1}$. So it has $(n+1)!$ vertexes.
I ...

**9**

votes

**1**answer

193 views

### Matrix obtained by recursive multiplication and a cyclic permutation

Have you ever seen this matrix? Each row is obtained from the previous one by multiplying each element by the corresponding element of the next cyclic permutation of $(a_1,\dots, a_n)$:
$$\left(
\...

**17**

votes

**2**answers

879 views

### A conjecture harmonic numbers

I will outlay a few observations applying to the harmonic numbers that may be interesting to prove (if it hasn't already been proven).
From the Online Encyclopedia of Positive Integers we have:
$a(n)$ ...

**3**

votes

**0**answers

70 views

### Counting sets whose alternation is preserved by a permutation

Say a set $X \subseteq \{1,\ldots,n\}$ is alternating if successive elements of $X$ are of opposite parity. That is to say for any $x \in X$, if $y = \min \{z \in X \mid x < z\}$ then $x \not\...

**1**

vote

**1**answer

144 views

### The number of permutations of given order

I want to count the number of permutations of the given order $k$ in $S_n\;(\sigma^k=id,\sigma^l\neq id\;for\;l<k)$. I found some works about that problem, but they are more general than necessary. ...

**6**

votes

**1**answer

214 views

### Permutation function based on subsets

We have some subsets $A_1,\dots,A_k$ of $A=\{1,2,\dots,n\}$. For each permutation $\sigma$ of $A$, define $f(\sigma) = \sum_{i=1}^k g(\sigma,A_i)$, where if the earliest element of $A_i$
in $\sigma$ ...

**9**

votes

**5**answers

788 views

### The number of ways to merge a permutation with itself

Let $\sigma$ be a permutation of $[k]=\{1,2, \dots , k\}$. Consider all the ordered triples $(\pi, s_{1},s_{2})$, such that $\pi$ is a permutation of length $2k-1$ that is a union of its two ...

**1**

vote

**0**answers

84 views

### Permutation induced by multiplication of finite field elements [closed]

Consider a finite field $\mathbb F$. Let $a \in \mathbb F$. Then multiplication by $a$ induces a permutation on the field elements. $0 \rightarrow 0$, $1 \rightarrow a$, $2 \rightarrow 2a$, etc.
Is ...

**2**

votes

**1**answer

235 views

### Number of 5x5 matrix permutations without repetitions in rows or columns

Context
In the boardgame Azul, your goal is to complete as much as possible of a $5\times5$ board by placing 25 tiles of 5 different colours (5 tiles of each colour) so that no colour appears twice in ...

**2**

votes

**1**answer

180 views

### Number of permutations of a set given arbitrary precedence constraints

I am trying to find a mathematical relationship between the size of a tree (or - in other terms - the cardinality of set or permutations) for a set of elements which are subject to precedence ...

**8**

votes

**0**answers

193 views

### A question related to Young symmetrizers

Let $T$ be an arbitrary Young tableau (i.e., filling of the diagram of an integer partition $\lambda$ of $n$ by the numbers from $1$ to $n$, each appearing once). Let $R(T)$ be the subgroup of ...

**10**

votes

**1**answer

321 views

### Generalization of symmetric functions

A $n$-variable function $f$ is a symmetric function if
$$f(x_1,x_2, \ldots, x_n) = f(x_{\sigma(1)}, x_{\sigma(2)}, \ldots, x_{\sigma(n)})$$
for every permutation $\sigma \in S_n$.
In particular, if $f$...

**12**

votes

**1**answer

321 views

### What's the dimension of the Lie algebra generated by transpositions on $n$ objects?

Define a Lie bracket on the group algebra of the permutation group $S_n$ in the following way:
$$[\sigma, \tau] = \sigma\circ\tau - \tau\circ\sigma,$$
where $\sigma, \tau \in S_n$, and the ...

**4**

votes

**0**answers

97 views

### Words that give rise to an enumeration of elements of the symmetric group

Let $\mathbb{S}_m$ be the symmetric group on $m$ letters. Let $n=m-1$. Let $\mathbf{w}=a_1\cdots a_r$ be a word on the alphabet $\{1,\ldots,n\}$. We say that $\mathbf{w}$ gives rise to an enumeration ...

**3**

votes

**1**answer

142 views

### Detailed proof of $\mathfrak{s}^{-1}\mathrm{End}_V\cong \mathrm{End}_{\Sigma V}$

I asked this question on MSE but I want to ask it again here with some more context sine it received no answers. In Chapter 3 (Algebra) of the book Operads in Algebra, Topology and Physics by Markl, ...

**5**

votes

**1**answer

205 views

### A graph similar to the Bruhat graph, what is it called?

The weak Bruhat graph (or 1-skeleton of the permutohedron) $B_n$ can be constructed as follows:
the vertices of $B_n$ are the permutations of the tuple $(1,...,n)$, two are joined by an edge, if they ...

**4**

votes

**0**answers

226 views

### Distance properties of the permutations of a set of points in a Euclidean space

We are given a set of $n$ distinct points $S=\{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\}$ in a Euclidean space $\mathbb{R}^d$, where the distance between two points $\mathbf{x}_i,\mathbf{x}_j\...

**0**

votes

**0**answers

40 views

### How to construct such a series of “partial” symmetric polynomials?

As we know, a symmetric polynomial is a polynomial P(X1, X2, …, Xn) in n variables, such that if any of the variables are interchanged, one obtains the same polynomial. Formally, P is a symmetric ...

**7**

votes

**0**answers

106 views

### A conjecture on circular permutations of n elements in an abelian group of odd order

In 2013 I formulated the following conjecture in additive combinatorics.
Conjecture. Let $G$ be an additive abelian group of odd order, and let $A$ be a subset of $G$ with $|A|=n>2$. Then, there is ...

**10**

votes

**3**answers

345 views

### Number of permutations with longest increasing subsequences of length at most $n$

Is there a known expression for, or a nontrivial upper bound on, the number of permutations in $S_k$ with longest increasing subsequence of length at most $n$?
Let $l(\sigma)$ denote the length of the ...

**1**

vote

**0**answers

101 views

### A maximization problem with permutations

Consider a partition $f:S_n\rightarrow [n]$ of $S_n$ into $n$ parts. Denote the permutations that map $j$ to $k$ by $s(j,k)$. Set $S(f):=\Sigma_{1\leq i,j\leq n}max_{1\leq k\leq n}|f^{-1}(i)\cap s(j,k)...

**1**

vote

**0**answers

85 views

### Is there a characterization for the finite sequences of natural numbers which are the shifts of a permutation?

Given a natural number $k<n$ and a permutation $\sigma\in S_n$, I will call $k$ a shift of $\sigma$ if there is some $m$ with $\sigma(m)-m\equiv k \mod n$. If one is given a sequence $s=(x_1,...,...

**3**

votes

**0**answers

59 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 ...

**1**

vote

**0**answers

66 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 ...