Questions tagged [permutations]

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

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

1
2 3 4 5
9