# Questions tagged [permutations]

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

**6**

votes

**2**answers

104 views

### Neighboring number of a permutation

For any positive integer $n\in\mathbb{N}$ let $S_n$ denote the set of all bijective maps $\pi:\{1,\ldots,n\}\to\{1,\ldots,n\}$. For $n>1$ and $\pi\in S_n$ define the neighboring number $N_n(\pi)$ ...

**3**

votes

**0**answers

229 views

### A new combinatorial problem for finite groups

In a recent preprint arXiv:1811.10503, I proved that if $a_1,\ldots,a_n$ are distinct elements of a torsion-free additive abelian group $G$, then there is a permutation $\pi\in S_n$ such that all ...

**3**

votes

**2**answers

279 views

### On the sum $\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$

Motivated by Question 316142 of mine, I consider the new sum
$$S(n):=\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$$
for any positive integer $n$, where $S_n$ is the symmetric group of all the ...

**0**

votes

**2**answers

198 views

### Permutations of squares and finite fields

Let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$, and let
$$S(n)=\bigg\{\sum_{k=1}^nk^2\pi(k)^2:\ \pi\in S_n\}.$$
Motivated by Question 316142 of mine, here I ask the following ...

**4**

votes

**0**answers

125 views

### Is there a permutation $\pi\in S_n$ with $\sum\limits_{0<k<n}\frac1{\pi(k)^2-\pi(k+1)^2}=0$ for each $n>7$?

Let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$.
QUESTION: Is it true that for each $n=8,9,\ldots$ we have
$$\sum_{0<k<n}\frac1{\pi(k)^2-\pi(k+1)^2}=0\tag{$*$}$$
for ...

**-1**

votes

**1**answer

263 views

### Odd & even permutations and unit fractions

One more motivated by recent questions of Zhi-Wei Sun.
Let $S_n$ be the group of permutations of $\{1,2,\ldots, n\}$.
Is it true that, for every $n \ge 8$, there is at least one even permutation $\...

**3**

votes

**0**answers

153 views

### A conjectural lower bound for $|\{\sum_{k=1}^nka_k:\ a_1,\ldots,a_n\ \text{are distinct elements of }\ A\}|$

Motivated by Question 315568 of mine, I'm interested in the set
$$S(n):=\bigg\{\sum_{k=1}^n k\pi(k):\ \pi\in S_n\bigg\}.$$
It is easy to see that
$$S(1)=\{1\},\ S(2)=\{4,5\}\ \text{and}\ S(3)=\{10,...

**1**

vote

**1**answer

154 views

### Derangements and unit fractions

Motivated by a recent question of Zhi-Wei Sun and its nice answer by Zhao Shen, here are two related questions.
Let $S_n$ be the group of permutations on $\{1, 2, \ldots, n\}$.
a. For each $n \ge ...

**1**

vote

**0**answers

59 views

### matching two positive-semidefinite matrices

Let $M_1$ and $M_2$ be two real positive-semidefinite matrices. Is there any algorithm to compute a permutation matrix $P$ to minimize $\| M_1-PM_2P^T \|_F^2$ or equivalently to maximize $trace(...

**2**

votes

**0**answers

107 views

### Chen primes and permutations

In 1973 the Chinese mathematician J.-R. Chen proved that there are infinitely many primes $p$ such that $p+2$ is a product of at most two primes. Nowadays such primes $p$ are called Chen primes.
For $...

**19**

votes

**1**answer

611 views

### Permutations $\pi\in S_n$ with $\sum_{k=1}^n\frac1{k+\pi(k)}=1$

Let $S_n$ be the symmetric group of all the permutations of $\{1,\ldots,n\}$.
Motivated by Question 315568 (http://mathoverflow.net/questions/315568), here I pose the following question.
QUESTION: Is ...

**0**

votes

**0**answers

113 views

### Permutations $\pi\in S_n$ with $p_k+p_{\pi(k)}+1$ prime for all $k=1,\ldots,n$

As usual, let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$.
QUESTION: Is my following conjecture true?
Conjecture. For any positive integer $n$, there is a permutation $\pi\...

**1**

vote

**1**answer

208 views

### Odd permutations $\tau\in S_n$ with $\sum_{k=1}^nk\tau(k)$ an odd square

For any positive integer $n$, as usual we let $S_n$ be the symmetric group of all the permutations of $\{1,\ldots,n\}$.
QUESTION: Is it true that for each integer $n>3$ there is an odd permutation ...

**3**

votes

**1**answer

80 views

### Cliques in Cayley graph on $n$-cycles

Let $S\subset S_n$ be the set of all $n$-cycles. I want to know if the Cayley graph $(S_n,S)$ has large dense subgraphs. I'm expecting it to not have super-polynomial size and $1-o(1)$ dense subgraphs....

**17**

votes

**1**answer

2k views

### A mysterious connection between primes and squares

Motivated by two previous questions of mine (cf. Primes arising from permutations and Primes arising from permutations (II)), here I ask a curious question which connects primes with squares.
...

**3**

votes

**0**answers

260 views

### Primes arising from permutations (II)

In Question 315259 (cf. Primes arising from permutations) I asked a question on primes arising from permutations which looks quite challenging.
Here I pose a new question in this direction which does ...

**8**

votes

**1**answer

421 views

### Primes arising from permutations

Recently, Paul Bradley proved in arXiv:1809.01012 that for any positive integer $n$ there is a permutation $\pi_n$ of $\{1,\ldots,n\}$ such that $k+\pi_n(k)$ is prime for every $k=1,\ldots,n$ (cf. ...

**2**

votes

**1**answer

86 views

### The complexity of sorting a list having one free cell

Making a standard bureocracy (using Word tables), I arrived to the following
Problem. Assume that we have a table with $n+1$ rows. The first $n$ rows are filled with names of students (and say ...

**2**

votes

**1**answer

219 views

### On triangular numbers modulo primes

Let $p$ be an odd prime. For $a\in\mathbb Z$ let $\{a\}_p$ denote the least nonnegative residue of $a$ modulo $p$. The list $\{1^2\}_p,\ldots,\{((p-1)/2)^2\}_p$ is a permutation of all the quadratic ...

**3**

votes

**0**answers

32 views

### Maximal number of sets, obtained as intersections of semiintervals of $k$ linear orders

Given a finite set $S$ with $n$ elements, and a fixed small $k$ (say $k=3$), how to find $k$ linear orders $\leq_1, \dots, \leq_k$ on $S$, such that the number of feasible subsets of $S$ is ...

**3**

votes

**4**answers

464 views

### A generalization of Landau's function

For a given $n > 0$ Landau's function is defined as $$g(n) := \max\{ \operatorname{lcm}(n_1, \ldots, n_k) \mid n = n_1 + \ldots + n_k \mbox{ for some $k$}\},$$
the least common multiple of all ...

**4**

votes

**1**answer

209 views

### Number of permutations that are products of disjoint cycles of distinct length

What is the number of permutations $\pi\in S_n$ that are products of disjoint cycles of distinct length? What is the number of permutations that are products of disjoint cycles such that no more than $...

**2**

votes

**1**answer

125 views

### The number of numbers no greater than n that are divisible by all their suffixes

My question: what a formula for finding the number of numbers no greater than n that are divisible by all their suffixes.
e.g: 5, 25, 125, 0125, 70125 are divisors of 70125.
refinement: $\overline{0....

**5**

votes

**0**answers

151 views

### $X$-rays of permutations

Consider the set of permutations $\mathfrak{S}_n$, on $\{1,2,\dots,n\}$, and identify each element $\pi\in\mathfrak{S}_n$ with the corresponding permutation matrix.
There has been some study (e.g. ...

**8**

votes

**1**answer

175 views

### For which primes does this iterated function act transitively? (Sort of a finite analogue of Collatz conjecture.)

Background: I was trying to prove something having to do with cyclic group actions on matroids and was able to show that what I want holds if a particular elementary-looking number-theoretic property ...

**6**

votes

**2**answers

267 views

### On the parity of $|\{(j,k):\ 1\le j<k\le\frac{p-1}2\ \&\ \ j(j+1)\ \text{mod}\ p\,>\,k(k+1)\ \text{mod}\ p\}|$ with $p$ prime

Let $p=2n+1$ be an odd prime, and let $a_1<\ldots<a_{n}$ be all the quadratic residues mod $p$ among $1,\ldots,p-1$. For $a\in\mathbb Z$ let $\{a\}_p$ be the least nonnegative residue of $a$ ...

**0**

votes

**0**answers

40 views

### Is there a formula for computing the parity of a sequence with discrete alphabet?

Suppose we have a sequence of number, whose alphabet is chosen from a discrete set such as (0,1,2). An example of such sequence is 0210122. Now I would like to determine if it is an odd permutation ...

**5**

votes

**2**answers

195 views

### Is there a size 2 generating set of the signed symmetric group $B_n$?

The signed symmetric group $B_n$ is a permutation group where the underlying set is $B_n=\{\sigma \in S_{A_n}| \forall x \in A_n, \sigma(-x)= -\sigma(x)\}$ with $A_n=\{-n,-(n-1),-(n-2),\cdots,-1,1,\...

**7**

votes

**3**answers

306 views

### Distribution of sum of two permutation matrices

Determinant and permanent of sum of two $n\times n$ permutation matrices can be arbitrarily different.
What is the distribution of determinant of sum and difference of two $n\times n$ permutation ...

**1**

vote

**1**answer

104 views

### The number of permutations with a special condition

Suppose we are considering $S_n$. For any permutation, let $h$ be the number of derangement and $N$ be the number of cycles with length no less than 2.
I'm interested in the number of permutations ...

**2**

votes

**1**answer

120 views

### Basis for Annular Skein Algebra

Background/Notation:
Given the Iwahori-Hecke algebra $H_{n}$ (over some ring commutative ring $R$ with identity) with generators $\{T_{1},\ldots T_{n-1}\}$, we know it has basis
$\{T_{w}\}_{w\in S_{...

**1**

vote

**1**answer

196 views

### A permutation with reflection property

Consider permutations $\pi$ of the set $\{1,\dots,n\}$ having the symmetry property $\pi \pi^* \pi = \pi^*$, where $\pi^*$ is the "reflection" $k \mapsto n+1-k$. Are there references or other ...

**0**

votes

**3**answers

223 views

### The number of permutations with specified number of cycles and fixed points

I'm interested in the number of permutations for a specified number of fixed points and cycles.
Suppose we are in $S_n$. For any permutation in $S_n$, let $h$ be the number of changed points (the ...

**0**

votes

**0**answers

49 views

### k-ary bracelets with conserved/fixed indexes

Im using the formula from here:
https://en.wikipedia.org/wiki/Necklace_(combinatorics)#Number_of_bracelets
to calculate the number of unique bracelets, accepting all rotation/mirroring as equivalent,...

**2**

votes

**0**answers

41 views

### Probability Distribution on permutations with factor structure

Say I define a probability measure over the symmetric group $S_n$ as follows:
I specify $n$ positive `potential' functions $G_i : \{1, 2, \cdots, N\} \to (0,\infty)$
I then set
$$\mathbb{P}(\sigma) =...

**12**

votes

**2**answers

326 views

### Cycle generating function of permutations with only odd cycles

Let $\mathrm{ODD}(n)$ be the set of permutations in $\mathfrak{S}_n$ whose cycle lengths are all odd. It is known that
$$ \#\mathrm{ODD}(n) = \begin{cases} ((n-1)!!)^2 &\textrm{ if $n$ is even}; \\...

**3**

votes

**0**answers

109 views

### Dirichlet eta function and Stirling Permutations

The Stirling permutations of order $k$ is a permutation of the multiset $1, 1, 2, 2, ..., k, k$. The Dirichlet $\eta$-function is a function closely related to the Riemann $\zeta$-function.
According ...

**14**

votes

**3**answers

585 views

### Determining if some permutation of a vector satisfies a system of linear equations

Let $A$ be a matrix and $x$ a fixed vector. How can we determine whether or not there exists a permutation matrix $P$ such that $APx=0$? Does this problem reduce to anything well-understood?

**1**

vote

**0**answers

110 views

### A partial ordering on $S_n$

Where $P$ and $Q$ are permutations in $S_n$, let's say $P<Q$ if $P$ is obtained from $Q$ by swapping two numbers which $Q$ places in the correct order. For example, if
$$Q=(1, 3, 6, 5, 4, 2)$$
$$P=...

**6**

votes

**1**answer

198 views

### Can a primitive root-permutation of $A=\{1, 2, \ldots, p-1 \}$ be a cycle of length $p-1$ only for finitely many $p$?

Let $p$ be an odd prime, $g$ a primitive root of $p$ and $A=\{1, 2, \ldots, p-1 \}$.
Obviously, $\sigma_g(p)=\begin{pmatrix}
1 & 2 & \ldots & {p-1} \\
g^1\pmod{p} & g^2\pmod{p} &...

**2**

votes

**0**answers

86 views

### Loopless algorithm for generating permutations (Steinhaus-Johnson-Trotter)

The following is a description of the well-known Steinhaus-Johnson-Trotter algorithm to generate all permutations of an $n$-element ground set using adjacent transpositions.
In fact, it is a loopless ...

**0**

votes

**0**answers

78 views

### Bracelets with beads from different color sets

I would like to count the number of bracelets with $N$ (numbered) beads, where, say, beads with index (i.e. at position) $i \in \{1,...,n\}$ can have a 'color' $c(i) \in \{1,...,k\}$ and beads with ...

**0**

votes

**1**answer

173 views

### root of identity matrix and lexicographic order

I asked a question here order of a permutation and lexicographic order but it seems*** that a very powerful and rich generalization can be made!
Let $A$ be a finite ring together with an arbitrary ...

**1**

vote

**1**answer

129 views

### order of a permutation and lexicographic order

Let $M$ be an $n\times m$ matrix, say with entries in $\left\{0,1\right\}$ ; and let $\mathcal C(M)$ be the $n\times m$ matrix such that there exists $P$, $m\times m$ permutation matrix such that $...

**3**

votes

**1**answer

142 views

### Cycle Structure of a Permutation Based on the Binary Representation

This is a question I posted on math.stackexchange.com before but never got an answer. I am cross-posting it here.
Define a permutation $\sigma$ on the set $X=\{1,2,...,n\}$, $n$ is a natural number ...

**6**

votes

**1**answer

272 views

### A permutation problem

Here I ask a question on permutations of $n$ distinct real numbers.
QUESTION: Let $a_1,a_2,\ldots,a_n\ (n>1)$ be (pairwise) distinct real numbers. Is there a permutation $b_1,\ldots,b_n$ of $a_1,\...

**6**

votes

**0**answers

80 views

### Decomposition of even symmetric polynomials and Euler numbers

Let's denote the even part of a polynomial $p$ by $E[p]$, which means only taking into account the monomials in $p$ which are even in all the arguments. Now let's consider the even part of the ...

**3**

votes

**0**answers

104 views

### Permutation statistics in multiple rows

Usually we study the statistics of a permutation written in one row. Is there any result for the statistics of a permutation written in multiple rows? Let me give an example in order to be more clear: ...

**7**

votes

**1**answer

392 views

### Linear permutations commuting with $x\rightarrow x^{-1}$

Let $F = \operatorname{GF}(2^n)$ be a finite field. Define a permutation $\phi:F \rightarrow F$ by the formula
$$
\phi(x) = x^{-1}, \ x\neq 0; \ \phi(0) =0.
$$
We say that a permutations $\psi$ of $F$ ...

**2**

votes

**0**answers

71 views

### Combinatorial model for twisted involutions in $S_n$

Let $(W,S)$ be a Coxeter group and $*:S \to S$ be an automorphism of the Dynkin diagram of $W$ so that $*^2$ is the identity.
This induces a bijection $*:W \to W$ mapping $w = s_1 \dots s_n$ to $w^* = ...