Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

1
vote
0answers
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
3answers
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
1answer
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
1answer
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
0answers
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
1answer
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
2answers
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
0answers
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
2answers
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
3answers
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
1answer
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
1answer
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
1answer
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
3answers
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
0answers
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
0answers
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
2answers
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
0answers
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
3answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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 ...