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

**1**

vote

**0**answers

57 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

111 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

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

**16**

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

**2**answers

193 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

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

**1**

vote

**1**answer

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

**0**

votes

**0**answers

84 views

### OEIS A217626: How to determine the precise multiple of 9 to add to an integer to derive indexes of next lexicographic permutation? [closed]

Consider OEIS A217626.
Given an input integer where the digits are in ascending numeric order
12
123
...

**2**

votes

**1**answer

207 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

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

**2**

votes

**3**answers

327 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

195 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

122 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

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

**7**

votes

**1**answer

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

**5**

votes

**2**answers

253 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

261 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

101 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

118 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

186 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

205 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

43 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

308 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

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

**13**

votes

**3**answers

492 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

109 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

193 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} &...

**1**

vote

**0**answers

74 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

75 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

172 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

126 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

139 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

253 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

100 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

372 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

70 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^* = ...

**6**

votes

**0**answers

156 views

### How many permutations do you need to force fixed points?

For simplicity let $k$ be given fixed, and $n$ grows large. We are interested in a small set $M_n={g_1,...,g_m}$ of permutations in $S_n$, s.t for all $a\in S_n$, there is $g_i \in M_n$ with $ag_i$ ...

**0**

votes

**0**answers

29 views

### What is an example of a constructive encoding of binary strings modulo an arbitrary permutation group $G$?

Given a group $G \leq S_n$ we can construct by the axiom of choice a function $f : \{0, 1\}^n \rightarrow \{0, 1\}^{ceil(log_2 |\{0, 1\}^n/G|)}$ such that for any orbit $O$ of binary strings under $G$,...

**3**

votes

**2**answers

179 views

### Length of composition series in a primitive group

Let $G$ be a primitive group acting on a set $\Omega$ with $n$ elements. By Cameron/Liebeck (essentially a consequence of the Classification + O'Nan-Scott), there are two possibilities:
(a) $G$ has a ...

**4**

votes

**1**answer

286 views

### Sets $A$ stable under $(x,f(x))\mapsto x+f(x)$

Let $A$ be a finite set of real numbers or integers. We know how to characterize, broadly speaking, sets $A$ such that $A+A$ is not much larger than $A$ (Freiman's theorem). I have a question that ...

**4**

votes

**2**answers

129 views

### Factorizations in terms of characters

I have asked this in math.SE (https://math.stackexchange.com/questions/2698772/factorizations-in-terms-of-characters) but it was barely viewed.
I have seen mention in different places that the number ...

**0**

votes

**1**answer

59 views

### Sequence Generation with Combinations and Permutations

I am trying to generate a set of genetic sequences with conditions. The problem uses a base 4 numerical notation:
nucleotides = ['A','C','G','T']
From this, I'd ...

**2**

votes

**0**answers

72 views

### First appearance of “structure tree”?

Let $G$ be a transitive permutation group acting on a set $\Omega$. A structure tree $T$ for $(G,\Omega)$ is defined as follows: if $G$ is primitive, then it consists of a root node connected by edges ...

**2**

votes

**0**answers

69 views

### Permutation factorizations according to number of generated orbits

Let $\pi$ be a permutation in $S_n$ with cycle type $\lambda$.
How many factorizations into two factors $\pi=\sigma_1\sigma_2$ are there, such that the subgroup $\langle \sigma_1,\sigma_2\rangle$ ...

**5**

votes

**0**answers

99 views

### 'Permutation Coupling' for Markov Chains

Suppose I have a Markov chain (discrete time, finite state space) on $[N] = \{1, 2, \cdots, N\}$, with Markov kernel given by a doubly stochastic matrix $P$. The double-stochasticity guarantees that ...

**30**

votes

**1**answer

1k views

### Mysterious symmetry - in search for a bijection

I have a mysterious symmetry that I have not managed to prove.
First some definitions (see picture below)
Fix a partition that fit in a staircase shape with $n$ rows.
There are $Catalan(n)$ such ...