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\...
- 26.8k
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 ...
- 43
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 ...
- 5,742
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, ...
- 1
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 ...
- 43.6k
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 (...
- 43.6k
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 ...
- 39
-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 ...
- 269
-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 ...
- 23
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$...
- 4,666
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 ...
- 24k
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 $...
- 16.3k
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 ...
- 21
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 ...
- 436
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 $...
- 101
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 ...
- 29.1k
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]...
- 3,667
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,693
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.
...
- 2,881
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]$ ...
- 1,105
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 ...
- 12.3k
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 ...
- 43.6k
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.
...
- 13.5k
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,790
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, ...
- 2,790
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,790
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, ...
- 2,790
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 ...
- 41
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 ...
- 2,790
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 ...
- 2,790
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 $...
- 2,790
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 ...
- 2,790
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 $...
- 103
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$$
- 3,794
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 ...
- 17
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 ...
- 22.7k
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 ...
- 22.7k
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 ...
- 2,790
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 ...
- 2,790
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 =...
- 111
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 ...
- 16.3k
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 ...
- 29.1k
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 ...
- 163