# Questions tagged [permutations]

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

463
questions

2
votes

0
answers

72
views

### A minimal size of a set of tuples for an upper bound of a distance between any pair of elements

Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates)....

4
votes

1
answer

258
views

### The fraction $\frac{g_{\mu}}{f_{\lambda}}$ is an integer

Let $\lambda=(\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_{\ell(\lambda)}>0)$ be an integer partition of $n\in\mathbb{N}$; i.e., $\lambda_1+\cdots+\lambda_{\ell(\lambda)}=n$.
One may now associate $...

3
votes

1
answer

105
views

### Cycle counts in Ewens measure as $\theta$ diverges

For $w$ a permutation, let $c(w)$ denote the total number of cycles and $c_i(w)$ denote the number of $i$-cycles.
The Ewens measure is a one-parameter probability distribution on permutations where ...

5
votes

1
answer

299
views

### Counting monomials and the Catalan numbers

Given a multi-variable polynomial $F$, denote the number of monomials by $N(F)$. Take for instance, \begin{align*}N(x(x+y)+(x+y)^2-(x-y)^2)=N(x^2+5xy)&=2 \qquad \text{and} \\
N((x+z)(x+y)^2)=N(x^3 ...

0
votes

1
answer

186
views

### A particular permutation on $\mathbb{Z}_n$

Let us consider $\mathbb{Z}_N=\{0,1,\cdots N-1\}$.
Does there exist any permutation $\sigma$ on $\mathbb{Z}_N$ satisfying :
$$\exists p,q\in\mathbb{N}, ~~p,q\neq0 (mod~N) ~~\forall i,j\in \mathbb{Z}...

15
votes

5
answers

1k
views

### Longest increasing subsequence as measure of randomness

Although I am by no means an applied mathematician, I like to occasionally explain applications of the math I teach to real world problems. Right now I am teaching some students about longest ...

3
votes

1
answer

218
views

### Generating function for "descents" and "cycle-types", in tandem

This question is inspired but not directly related to this recent Stanley's MO post.
The descent set $D(w)$ of a permutation $w=a_1 a_2\cdots a_n\in\frak{S}_n$ (the symmetric group on $\{1,\dots,n\}$) ...

9
votes

0
answers

285
views

### Number of sets $S$ for which number of permutations in $S_n$ with descent set $S$ is odd

The descent set $D(w)$ of a permutation $w=a_1 a_2\cdots a_n\in\frak{S}_n$ is
defined by $D(w)=\{ 1\leq i\leq n-1\,:\, a_i>a_{i+1}\}$.
Given a set $S$, let
$\beta_n(S)$ denote the number of ...

2
votes

0
answers

115
views

### Counting permutations with a fixed number of descents and an extra condition

I am computing the volumes of certain polytopes and it turns out that knowing a "closed formula" for the following number would help a lot.
Determine the number of permutations $\sigma\in \...

3
votes

0
answers

176
views

### Permuting subgroups with the same finite index

Suppose that we have a finitely generated residually finite group $G = \langle g_1,\ldots,g_r \rangle$ with polynomial growth. Let $H$ be a subgroup of $G$ with finite index $m$. Let $\phi$ be an ...

3
votes

0
answers

249
views

### Inequalities involving traces of products of hermitian positive semidefinite matrices

$\DeclareMathOperator{\tr}{tr}$
Fix an integer $n \geq 2$. Let $A_1, \dotsc, A_n$ be hermitian positive semidefinite matrices, with each $A_i$ being $m$ by $m$.
Consider the symmetric group $S_n$ on $...

0
votes

0
answers

39
views

### How many lists of tuples that are invariant (as sets) under a full cyclic permutation of one index?

Consider two finite index sets $A=\{1,\ldots,a\}$ and $B=\{1,\ldots,b\}$ and lists $((i_{k},j_k))_{1\leq k\leq n}$ with $i_k\in A$ and $j_k\in B$. Now we pick any $n$-cyclic permutation $\pi$. For ...

1
vote

1
answer

142
views

### Sequence of monotone tuples and permutation condition for rotation

I was doing some counting in $S_n$ symmetric group I encountered the following problem, which also someway related to central factorial number.
So given a $n$ cycle say $(1,2,\ldots,n)$, what are the ...

0
votes

0
answers

68
views

### $\max\left\lbrace(n-i+1)\operatorname{prime}(i); 1 \leqslant i \leqslant n\right\rbrace$ from permutation

Let $P(n)$ of a sequence $s(1),s(2),s(3),...$ be obtained by leaving $s(1),...,s(n)$ fixed and
sorting in descending order if $n$ is prime
sorting in ascending order if $n$ is not prime
every $n$ ...

1
vote

1
answer

65
views

### Cycling through $\{0,1\}^n$ by shifting and applying a $n$-ary function

This question is motivated by Linear Feedback Shift Registers, which cycle through $\{0,1\}^n \setminus \{(0,\ldots,0)\}$ by shifting and applying a small set of XOR operations.
Let $n>1$ be an ...

0
votes

0
answers

79
views

### Prime numbers from another permutation

Related question: Prime numbers from permutation
Let $P(n)$ of a sequence $s(1),s(2),s(3),...$ be obtained by leaving $s(1),...,s(n-1)$ fixed and forward-cyclically permuting every $n$ consecutive ...

9
votes

1
answer

482
views

### Prime numbers from permutation

Let $P(n)$ of a sequence $s(1),s(2),s(3),...$ be obtained by leaving $s(1),...,s(n)$ fixed and reverse-cyclically permuting every $n$ consecutive terms thereafter; apply $P(2)$ to $1,2,3,...$ to get $...

3
votes

1
answer

99
views

### Algorithm to minimize $\operatorname{tr}(PAP^TB)$?

Let say I have two $n$ x $n$ matrices $A$ and $B$ where all elements are real positive values. I want to find some $n$ x $n$ permutation matrix $P$ such that $\operatorname{tr}(P A P ^T B)$ is ...

18
votes

1
answer

538
views

### Fraction of $S_n$ reachable by using every transposition once as $n\to\infty$?

For $n\in \mathbb{N}$ let $S_n$ denote the set of permutations (bijections) $\pi: \{0,\ldots,n-1\}\to \{0,\ldots,n-1\}$. A transposition swaps exactly $2$ elements and is often denoted by $(i \; k)$ ...

2
votes

0
answers

176
views

### Conjecture on A057030

Let $P(n)$ of a sequence $s(1),s(2),s(3),...$ be obtained by leaving $s(1),...,s(n-1)$ fixed and reversing every n consecutive terms thereafter; apply $P(2)$ to $1,2,3,...$ to get $PS(2)$, then apply $...

8
votes

3
answers

368
views

### Latin squares with one cycle type?

Cross posting from MSE, where this question received no answers.
The following Latin square
$$\begin{bmatrix}
1&2&3&4&5&6&7&8\\
2&1&4&5&6&7&8&3\\...

3
votes

1
answer

140
views

### Relation between two permutation metrics

Note: I asked this question a few months ago here, but received no answer.
Consider the following two metrics on permutations of $\{1,2,\dots,n\}$:
$d_\text{swap}(\sigma,\tau)$ is the minimum number ...

0
votes

0
answers

56
views

### Function with $\text{Sym}_k$-orbit as fiber / forgetting ordering of vectors

Fix $n,k >0$. Is there a continuous function
$$ f: \oplus^k \mathbb{R}^n \longrightarrow \mathbb{R}^m$$
for some $m$ so that each fiber is essentially given by an orbit of the permutation group $\...

23
votes

1
answer

844
views

### Symmetric polynomial inequality arising from the fixed-point measure of a random permutation

A somewhat strange elementary polynomial inequality came up recently in my work, and I wonder if anyone has seen other things that are reminiscent of what follows.
Given $n$ non-negative reals $a_1, ...

1
vote

0
answers

37
views

### Permutation of nonnegative integers applied to the numbers $n$ whose binary expansion does not begin with $11$

Let $\operatorname{wt}(n)$ is A000120, number of $1$'s in binary expansion of $n$ (or the binary weight of $n$) and
$$n=2^{b_1}(1+2^{b_2+1}(1+2^{b_3+1}(1+\cdots(1+2^{b_{\operatorname{wt}(n)-1}+1}(1+2^{...

6
votes

0
answers

120
views

### Variant of the pancake problem

For two permutations $\pi,\tau \in S_n$, we say they are related by a prefix reversal if there exists $t$ such that $\tau(i) = \pi(i)$ for $i\ge t$ and $\tau(i) = \pi(t-i)$ for $i<t$. Similarly, we ...

5
votes

1
answer

296
views

### A bijection on permutations

I am looking for a bijection between permutations in $\mathfrak S_n$ with a certain weight and a second set, which arises by interpreting the expression
$$
\frac{1}{2}\left(1 + \exp(q \log\left(\frac{...

1
vote

3
answers

167
views

### Existence of latin squares with an involutory symmetry

Let $M \in \mathbb{N}$ and let $\pi \in S_{M}$ be an involution with at least one fixed point. I'm interested in finding a latin square $A$ of order $M$ such that $A_{i,j} = \pi(A_{j,i})$ for each $i,...

2
votes

2
answers

138
views

### Swaps in a permutation across an index

We are given two positive integers $N$ and $K$ such that $K < N$. We start with an array $A=[1,2,\dots,N]$. We can choose an arbitrary index $i \in \{1,2,\dots,N-1\}$ and we can swap $A[i]$ with $A[...

11
votes

4
answers

675
views

### How many non-isomorphic abelian subgroups of the permutation group $S_n$?

I am interested in how many (pairwise non-isomorphic) subgroups of the permutation group $S_n$ are abelian. ($n \in \mathbb{N}$ arbitrary and possibly big)
Are you aware of any references which treat ...

5
votes

1
answer

240
views

### Combinatorics and symmetry in matrices under row and column swaps

Suppose we have a $m\times n$ matrix and a sequence of numbers with which to fill the matrix, $\{c_1,c_2 \dots c_k \}$. I like to think of the numbers as colors, hence the notation. How many unique ...

2
votes

0
answers

63
views

### Prime numbers made of permutations of digits of consecutive positive integers

I posted this question in MSE some weeks ago and got no answer to any of the questions, so I post it here to see if someone could help.
Following the spirit of this question, I developed a program to ...

3
votes

2
answers

291
views

### Relation graph isomorphism to discrete logarithm

$\DeclareMathOperator\ora{ora}$Let $A_0$ be the adjacency matrix of graph $G$ and $P_0$
permutation matrix of multiplicative order $\rho$.
Let $X$ be positive integer and $B_0=P_0^X A_0 P_0^{-X}$.
Q1 ...

3
votes

0
answers

135
views

### Combinatorial interpretation of inverse modulo $2$ binomial transform of A284005

My question is related to the following:
Sum with products turned into subsequences
We have an identity
$$a(n, -1) = \sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}(-1)^{\operatorname{wt}(n)-\...

1
vote

0
answers

108
views

### Number of $k$-cycles in a random Mallows permutation

It is well-known that for uniform random permutations, the number of $k$ cycles for fixed $k$ is distributed as a Poisson random variable with mean $1/k$.
I am looking for similar results on the ...

0
votes

1
answer

115
views

### Prime constellations equivalent up to permutation

This question generalizes Symmetry in Hardy-Littlewood k-tuple conjecture. Say two prime constellations are equivalent up to permutation if they consist of the same multiset of prime gaps. One can ...

0
votes

0
answers

103
views

### A determinant involving the cotangent function

Let $n>1$ be odd. In my 2019 preprint On some determinants involving the tangent function, I proved that
$$\det\left[\tan\pi\frac{aj+bk}n\right]_{1\le j,k\le n-1}=\left(\frac{-ab}n\right)n^{n-2}$$
...

4
votes

0
answers

139
views

### Identities involving derangements and roots of unity

For a positive integer $n$, a derangement of $\{1,\ldots,n\}$ is a permutation $\tau$ of $\{1,\ldots,n\}$ with $\tau(j)\not=j$ for all $j=1,\ldots,n$. For convenience, we let $D(n)$ denote the set of ...

7
votes

0
answers

172
views

### Explaining $\left(a-1\right)^n \cdot n! \mid a^{n-1} \prod_{i=1}^n \left(a^i-1\right)$ by a free $S_n$-action

Here is an olympiad-level problem on elementary number theory:
Let $a$ be an integer and $n$ a positive integer. Prove that
\begin{align}
\left(a-1\right)^n \cdot n! \mid a^{n-1} \prod_{i=1}^n \left(...

0
votes

0
answers

50
views

### Hamming distance globally and Euclidean distance locally to a cycle

Given a permutation matrix 'the question is to decide if there is a permutation matrix representing a cycle within Hamming distance $d$ from given matrix'. Is there an efficient algorithm for it?
...

1
vote

0
answers

51
views

### Effect on finite transformation semigroup under a particular modification of the generators

The following question arises in connection with problems in automata theory related to the road problem. Let $f_1, f_2: [N] \to [N]$ be maps such that the transformation semigroup $S = \langle f_1, ...

2
votes

1
answer

110
views

### Operation including tensor product or Kronecker product transforming matrix $A$ into matrix $B$

Given two matrices $A$ and $B$:
What transformation needs to be applied to transform matrix $A$ into matrix $B$?
...

4
votes

1
answer

277
views

### Why is the sum of X-ray's of permutations linearly distributed?

Let $\mathfrak{S}_n$ be the set of permutations, on $\{1,2,\dots,n\}$, and the binary matrix $A$ is the corresponding permutation matrix for element $\pi\in\mathfrak{S}_n$.
Given a permutation matrix $...

3
votes

1
answer

158
views

### Does $\{\tau(1)\tau(2)+\cdots+\tau(n-1)\tau(n)+\tau(n)\tau(1):\ \tau\in S_n\}$ contain a unique multiple of $n^2$ for each $n\ge6$?

Motivated by Question 397575, here I pose a related question.
Question.
Does the set $$T_n:=\{\tau(1)\tau(2)+\cdots+\tau(n-1)\tau(n)+\tau(n)\tau(1):\ \tau\in S_n\}$$ contain a unique multiple of $n^2$ ...

5
votes

2
answers

253
views

### Permutations $\pi\in S_{p-1}$ with $\frac1{\pi(1)\pi(2)}+\frac1{\pi(2)\pi(3)}+\cdots+\frac1{\pi(p-2)\pi(p-1)}+\frac1{\pi(p-1)\pi(1)}\equiv0\pmod{p^2}$

A well known congruence of Wolstenholme states that
$$\frac1{1^2}+\frac1{2^2}+\cdots+\frac1{(p-1)^2}\equiv0\pmod{p}$$ for any prime $p>3$. For each $n=3,4,\ldots$ we clearly have
$$\frac1{1\times2}+...

0
votes

0
answers

88
views

### On reduced systems of residues modulo positive odd integers

In 2013 I formulated the followig conjecture on reduced systems of residues modulo positive odd integers.
Conjecture. For any odd integer $n>1$, there are integers $a_1,\ldots,a_{\varphi(n)}$ such ...

4
votes

1
answer

206
views

### "Permutation matrix" but non-zero entries are replaced by $e^{ix}$

Birkhoff–von Neumann theorem states that a polytope formed by a set of doubly-stochastic matrices has extreme points that are permutation matrices.
I am wondering if there is a similar theorem for a ...

3
votes

1
answer

169
views

### Is the Cayley distance on permutation (matrices) equivalent to the Riemannian metric on $O(n)$?

Denote by $d_C(\sigma,\mu)$ the minimal number of transpositions needed to go from a permutation $\sigma$ to a permutation $\mu$. E.g. if $d_C(\sigma,\mu)=0$, then $\sigma=\mu$, if $d_C(\sigma,\mu)=1$,...

2
votes

0
answers

258
views

### Infinite sum of iterated integrals of matrix products

Originally asked over at Stackexchange (https://math.stackexchange.com/questions/4169812/infinite-sum-of-iterated-integrals-of-matrix-products), but this forum was deemed more appropriate.
The problem:...

3
votes

1
answer

134
views

### Probability permutation in turned to cycle

Let $M$ be a $0/1$ square matrix having one $1$ per row and column (permutation matrix).
If you permute the columns and rows independently what is the probability resulting permutation matrix is a ...