Questions tagged [permutations]

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

Filter by
Sorted by
Tagged with
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)....
user avatar
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 $...
user avatar
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 ...
user avatar
  • 1,721
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 ...
user avatar
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}...
user avatar
  • 3,343
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 ...
user avatar
  • 18.8k
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\}$) ...
user avatar
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 ...
user avatar
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 \...
user avatar
  • 1,716
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 ...
user avatar
  • 233
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 $...
user avatar
  • 3,594
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 ...
user avatar
  • 417
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 ...
user avatar
  • 621
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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 $...
user avatar
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 ...
user avatar
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)$ ...
user avatar
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 $...
user avatar
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\\...
user avatar
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 ...
user avatar
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 $\...
user avatar
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, ...
user avatar
  • 543
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^{...
user avatar
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 ...
user avatar
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{...
user avatar
  • 5,009
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,...
user avatar
  • 93
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[...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 23.3k
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)-\...
user avatar
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 ...
user avatar
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 ...
user avatar
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}$$ ...
user avatar
  • 12.8k
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 ...
user avatar
  • 12.8k
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(...
user avatar
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? ...
user avatar
  • 12.8k
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, ...
user avatar
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$? ...
user avatar
  • 125
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 $...
user avatar
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$ ...
user avatar
  • 12.8k
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}+...
user avatar
  • 12.8k
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 ...
user avatar
  • 12.8k
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 ...
user avatar
  • 187
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$,...
user avatar
  • 131
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:...
user avatar
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 ...
user avatar
  • 12.8k

1
2 3 4 5
10