# Questions tagged [permutations]

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

528
questions

1
vote

0
answers

34
views

### Counting permutations of $X^2$ that induce 4 quasigroup operations up to isotopy

Let $X$ be a finite set. Recall that a binary operation $\ast$ on $X$ is said to be a quasigroup operation if there are binary operations $/,\backslash$ where $(x/y)\ast y=(x\ast y)/y=x$ and $x\ast(x\...

2
votes

1
answer

100
views

### Optimization over permutation

The Problem
This is the problem I am working on: Given a set $X = \{x_1, x_2, \cdots , x_n\}$ in a metric space, find an optimal ordering $\pi : X \rightarrow X$ that maximizes the following objective ...

2
votes

0
answers

57
views

### Diameters of permutation groups with transitive generators

Suppose that for a permutation puzzle on $n$ elements we have a subroutine to place any $m>3$ elements in arbitrary positions (possibly scrambling the rest). Can we solve the puzzle (if it is ...

0
votes

0
answers

24
views

### permutations of matrix oriented lements [migrated]

folks,
lets assume i have 16 different objects. that gives me 16! arrangements.
now i place them in a 4 x 4 matrix - which still gives me 16! arrangements.
now lets restrict the movements to vectors, ...

0
votes

0
answers

168
views

### A perfect shuffle on $\mathbb{N}$

Motivation. This weekend I was playing the pair-matching game Memory (also called Concentration in other parts of the world) against my youngest son, and wondered about what constitutes a "good ...

0
votes

1
answer

206
views

### Is there a lop-sided permutation $\pi:\mathbb{N}\to\mathbb{N}$? [closed]

For any $A\subseteq \mathbb{N}$ we let the (lower) density of $A$ be defined by $$d(A) = \liminf_{n\to\infty}\frac{|A\cap\{0,\ldots,n\}|}{n+1}.$$
If $\pi:\mathbb{N}\to\mathbb{N}$ is a permutation (...

3
votes

0
answers

111
views

### How to determine a permutation of $N$ integers with the maximal number of distinct adjacent gcds?

How to determine a permutation of $N$ integers with the maximal number of distinct adjacent gcds?
Given integers $p_1 , p_2 , p_3 , p_4 , p_5 , \ldots p_N$, which permutation of them will have the ...

-4
votes

1
answer

48
views

### What is 30th permutation of elements 1,3,5,7,9? [closed]

The answer is: 31975
But how do I get the answer with a method?

6
votes

1
answer

158
views

### Is there an element in an infinite tensor power of a C*-algebra that is invariant under finite permutations?

Let $A$ be a C*-algebra, and consider the infinite tensor power $A^{\otimes {J}}$, where $J$ is infinite (we consider the minimal or maximal tensor product). To any finite permutation, which is a ...

2
votes

1
answer

80
views

### Consecutive prime numbers in permutations of digits of the first consecutive positive integers

I have been toying for a while with the study of: in how many distinct primes and of which size can we divide permutations of digits of the first positive integers?
In this post I studied how many ...

-1
votes

1
answer

92
views

### A permutation and combination problem about the number of connections in a sequence of n numbers [closed]

There is a sequence of n numbers as 1,2,3,...,n
How many combinations of the connections between two numbers in the sequence without overlaping?
...

1
vote

0
answers

93
views

### The set of combinations has some algebraic structure, similar to the group of permutations? [closed]

The set $S_n$ of permutations over $\{1,2,...,n\}$ has a group structure. What if we take the set $C_{k,n}$ of $k$-combinations of $n$ elements? The first I can say is that $S_n$ acts on $C_{k,n}$. Is ...

0
votes

0
answers

42
views

### Expectation of the operator norm of projection of a random permutation matrix

Assuming I have a fixed dimension $p$ subspace of $\mathbb{R}^d$ orthogonal to $1^d$ and $VV^\top$ with $V \in \mathbb{R}^{d \times p}$ is the orthogonal projection to the subspace.
What bound can I ...

7
votes

0
answers

127
views

### Question about function on permutations

The following question is motivated by my research.
Let's consider a permutation $\sigma$ of the set $\{1, \ldots, n\}$. We define an element $i \in \{1, \ldots, n\}$ to be locally minimal for $\sigma$...

1
vote

0
answers

87
views

### Hard instances for this graph isomorphism algorithm based on powers of weighted adjacency matrices?

In short, I found an algorithm for GI and the only hard instances
I found so far are non-isomorphic strongly regular graphs with
large automorphism groups.
Q1 What are hard instances for the ...

3
votes

0
answers

100
views

### Twisted permutations

We consider a set $E$ with an involution (having perhaps fixed points).
We denote orbits by $\lbrace x,\overline{x}\rbrace$ (with $\overline{x}=x$ in
the case of a fixed point).
We consider sequences $...

2
votes

0
answers

159
views

### Component-wise sums of permutations

Given a set $S$ containing all possible permutations of a vector $v = (1, 2, 3, ..., n-1, n)$, find the size of the set $P$, where $P$ is defined as the set of possible component-wise sums obtained by ...

13
votes

2
answers

292
views

### Expected sorting time of random permutation using random comparators

In sorting networks, a comparator of positions $i < j$ is an operator which takes a permutation, checks if $p_i > p_j$, and if it is the case, swaps $p_i$ and $p_j$.
Using this, we can define ...

0
votes

0
answers

74
views

### Construct a permutation matrix from some eigenvectors and eigenvalues

Given $n$ orthonormal vectors $v_1, \dots, v_n \in \mathbb R^d$, where $d > n$, we can show that there are many orthogonal matrices $X$ of size $d$ such that $v_1, \dots, v_n$ are eigenvectors of $...

1
vote

0
answers

123
views

### 3D generalization of Gaussian q-binomial coefficient

It is known that the coefficient of $q^t$ in Gaussian binomial coefficient $\binom{m+n}m_q$ equals the number of permutations of the multiset $\{0^m, 1^n\}$ with $t$ inversions.
Is there a closed ...

3
votes

1
answer

174
views

### Removing the symmetry maps from a small category of cubes

Let $[1]^n=\{0<1\}^n$ equipped with the product order. I consider the small category $\widehat{\square}$ of the category of partially ordered sets generated by the coface maps $\delta^\epsilon_i:[1]...

1
vote

0
answers

76
views

### All the regular $n$-gons are nested tightly around a unit circle. How to order them to minimize the outer radius, and what is that minimum radius?

Let $u_1,u_2,u_3,\dots$ be a permutation of the integers greater than $2$.
A unit circle is in a regular $u_1$-gon, which is a regular $u_2$-gon, which is in a regular $u_3$-gon, ad infinitum. Each ...

1
vote

1
answer

141
views

### Diagonally dominant matrix via rows permutation

Diagonally dominant matrices are required in many linear algebra algorithms such as the Gauss-Seidel algorithm.
Some matrices can be made diagonally dominant by permuting its rows and others cannot.
...

1
vote

0
answers

68
views

### Do the columns of the distribution of the DenertMaxDifference statistic on permutations eventually become constant?

The well known Denert statistic on permutations $p$ of $[n]$ can be defined as the number of Denert pairs for $p$, namely, the number of pairs $(i,j)$ with $1\le i<j\le n$ and
$j \in [p_i,p_j-1]$ ...

5
votes

2
answers

194
views

### Intersecting permutations

Given a subset $P\subset\mathcal{P}_n$ of the permutations of $1,\dots,n$
Question:
how can a maximal subset $p\subseteq\lbrace1,\dots,n\rbrace$ be determined, whose elements appear in the same ...

10
votes

2
answers

557
views

### Maximal Abelian subgroups of $S_\omega$

Let $S_\omega$ be the group of permutations (bijections) $\varphi:\omega\to\omega$, together with composition as binary operation.
Zorn's Lemma implies that every commutative subgroup of $S_\omega$ is ...

0
votes

0
answers

118
views

### On nilpotent singular $\mathbb F_2^{n\times n}$ matrices

Let $M$ be a $0/1$ matrix over $\mathbb F_2^{n\times n}$ with determinant $0$.
The set of such singular matrices form a semigroup.
The set of nilpotent matrices of size $n\times n$ form a semigroup.
...

0
votes

0
answers

68
views

### Permutation that produces permutations

Let $f(n)$ be A000045, i.e., Fibonacci numbers: $f(n)=f(n-1)+f(n-2)$ for $n>1$ with $f(0)=0$ and $f(1)=1$.
Let $g(n)$ be A072649, i.e., $n$ occurs $f(n)$ times. The sequence begins with
$$1, 2, 3, ...

2
votes

0
answers

76
views

### Uniqueness of the permutation

Let $f(n)$ be A000045(n), i.e., Fibonacci numbers: $f(n)=f(n-1)+f(n-2)$ for $n>1$ with $f(0)=0$ and $f(1)=1$.
Let $g(n)$ be A072649, i.e., $n$ occurs $f(n)$ times. The sequence begins with
$$1, 2, ...

1
vote

0
answers

109
views

### Existence of binary permutations with a given property

Let
$$\ell(n)=\left\lfloor\log_2 n\right\rfloor$$
Let
$$f(n)=n-2^{\ell(n)}$$
Let $a(n)$ be a permutation of the nonnegative integers such that $a(0)=0$, $a(n)=n$ if $n$ is a power of $2$ and ...

2
votes

1
answer

134
views

### Permutation and its binary analog

Let $f(n)$ be A000045(n), i.e., Fibonacci numbers: $f(n)=f(n-1)+f(n-2)$ for $n>1$ with $f(0)=0$ and $f(1)=1$.
Let $g(n)$ be A072649, i.e., $n$ occurs $f(n)$ times. The sequence begins with
$$1, 2, ...

0
votes

2
answers

219
views

### What mathematical formalism might be used to disprove natural selection, on the basis that there are too many independent genetic parameters? [closed]

I have nagging doubts that the random genetic mutation process of natural selection is sufficient to explain evolution, even when coupled with sexual selection (Darwin proposed that evolution is ...

1
vote

0
answers

78
views

### Infiniteness of the pairs of sequences with a given conditions

Let
$$\varphi=\frac{1+\sqrt{5}}{2}$$
Let
$$a_1(n)=\left\lfloor n\varphi \right\rfloor, a_2(n)=n+a_1(n)$$
Let $\operatorname{tr}(n)$ be A007814, i.e., the number of trailing zeros in the binary ...

0
votes

0
answers

45
views

### Stolarsky array and Stolarsky representation

Let $T(n,k)$ be A035506, i.e., Stolarsky array read by antidiagonals. Here we consider that $T(n,k)=0$ for $n<1, k<1$.
Let $a(n)$ be A200714, i.e., Stolarsky representation interpreted as binary ...

11
votes

0
answers

429
views

### What sequence maximizes the final distance?

This problem was created by professor Ronaldo Garcia from Universidade Federal de Goiás (UFG) and he showed it to me at an event in my university. This problem has a lot of history and he told me he ...

1
vote

0
answers

80
views

### Permutation to get Stolarsky representation from lazy Fibonacci (dual Zeckendorf) representation

Let $a_1(n)$ be A200714, i.e., Stolarsky representation interpreted as binary to decimal integers. The sequence begins with
$$0, 1, 3, 2, 7, 5, 6, 15, 4, 11, 13, 14, 31, 10, 9, 23, 12, 27, 29$$
Let $...

0
votes

0
answers

92
views

### Permutation using irreducible fractions

Let
$$f(n,k)=n\operatorname{mod} k, g(n,k)=\left\lfloor\frac{n}{k}\right\rfloor$$
Let $T(n,k)$ be A072030, i.e., array read by antidiagonals: $T(n,k)$ = number of steps in simple Euclidean algorithm ...

4
votes

1
answer

154
views

### A probability problem in the conjugacy classes of symmetric group

Assume that $\sigma\in S_n$ has the cycle type $(p,.,p,1,..,1)$ where $p>2$ is a prime and the numbers of $1$ maybe $0$. If $\sigma_1$ and $\sigma_2$ are chosen uniformly in the conjugacy class of $...

2
votes

1
answer

105
views

### If $n=2m$, what is the order of the permutation $\sigma(k)=2k , \quad \sigma(m+k)=2k-1$

Let $n=2m$. What is the order of the following permutation $\sigma$?
$$1\leq k\leq m \Rightarrow \sigma(k)=2k , \quad \sigma(m+k)=2k-1$$

2
votes

0
answers

116
views

### Young diagrams for the block matrices

Let S_n be the group of permutations of n elements. Consider map S_n -> S_mn of block permutations, and an irreducible representation of S_mn (over complex numbers), corresponding to Young diagram ...

0
votes

1
answer

157
views

### What is the function defined by f(k) = #σ1({1,2,…,k})∩σ2({1,2,…,k})∩{1,2,…,k}, where σ1,σ2 are a uniformly random permutations of size N?

Thanks to David Pechersky excellent answer we know that
expectation of $ | σ({1,2,…,k}) ∩ \{1,2,…,k \} | \rightarrow k^2/N$ for σ uniformly random permutation over $N$.
What about the same ...

1
vote

1
answer

224
views

### What curve is defined by the formula $f(k) ={}$length of intersection of the first $k$ elements for two random permutations?

Let us fix $N$. Note that function $f$ defined below will satisfy $f(0)=0, f(N) = N$ and it is monotonically increasing (not strictly).
The code for the function seems to me more clear way to ...

2
votes

0
answers

68
views

### Closed form for the number of permutations with a given excedance set

Let $q(n)$ be A007814, i.e., number of trailing zeros in the binary representation of $n$. Here
$$q(2n+1)=0, q(2n)=q(n)+1$$
Let $\operatorname{wt}(n)$ be A000120, i.e., number of $1$'s in binary ...

1
vote

1
answer

203
views

### Named sets of permutations

I am looking into interesting subsets of permutations,
and there are several classes of permutations which are named.
For example, there are
Derangements,
Alternating,
Grassmann permutations (at most ...

0
votes

0
answers

108
views

### Two different ways to compute the same sequence (A329369)

Let $p(n,k,m)$ be the $k$-th element of the $n$-th permutation of length $m$ where permutations sorted in lexicographic order. Here $p(n,k,m)=0$ for $n>m!$.
Let
$$f(n,k,m)=[p(n,k,m)> k]$$
and ...

1
vote

0
answers

40
views

### Enumerate all possible sign patterns spanned by matrix column space

Given a $m \times n$ matrix $A$ with $m>n$, I would like to enumerate all possible sign patterns $w$ generated by $Av$ for all $v \in \mathbb{R}^n$. More specifically, if $(Av)_i \geq 0$ then $w_i =...

0
votes

1
answer

83
views

### A property related to permutations with coprime adjacent values

Sequence A76220 of OEIS enumerates (up to $n=25$) the number $a_n$
of permutations $\sigma$ of $\lbrace 1,\ldots,n\rbrace$ such that
$\sigma(i)$ and $\sigma(i+1)$ are coprime for $i=1,\ldots,n-1$.
All ...

2
votes

0
answers

87
views

### Symmetric polynomial constructed from symmetric group

Let $n$ be a positive integer, $S_n$ be the symmetric group. For a permutation $p=[p_1,\dots,p_n]\in S_n$, define $x^p := x_1^{p_1}\cdots x_n^{p_n}$. It can be seen that the following polynomial is ...

1
vote

0
answers

154
views

### Proving a sign rule for $f_{2n}$

If $t_{1},...,t_{n}$ are real numbers, consider the set of indexed linear operators $T(t_{1}),...,T(t_{n})$ on a Hilbert space $\mathcal{H}$ and define its ordering by:
$$\pi[T(t_{1})\cdots T(t_{n})] :...

16
votes

1
answer

473
views

### Conjecture on sum over permutations of products of Catalan numbers

Context
In a recent paper involving entanglement in linear optics, we came across some summations involving Catalan numbers and permutations. In particular, these sums arise when doing integration ...