Questions tagged [permutations]
Questions related to permutations, bijections from a finite (or sometimes infinite) set to itself.
558
questions
0
votes
1
answer
79
views
Permutations which respect a partial order
I have been studying the following situation, and I have a claim I believe to be true, but am unsure on how to approach it. I would appreciate any references I could look into where others have ...
1
vote
1
answer
111
views
Chromatic number of the insert-and-shift graph on $S_n$
Let $S_n$ be the collection of bijections $\varphi:\{1,\ldots,n\}\to \{1,\ldots,n\}$. In an earlier question, the insert-and-shift graph structure was introduced on $S_n$ and the resulting graph is ...
0
votes
0
answers
33
views
Permutation for the fast computing of the $k$-th partition of $n$ in reverse lexicographic order
Let $a(n)$ be A000041 (i.e., $a(n)$ is the number of partitions of $n$ (the partition numbers)).
Let $b(n)$ be A000070. Here
$$
b(n) = \sum\limits_{i=0}^{n}a(i)
$$
Let $c(n)$ be $k-1$ where $k$ is the ...
1
vote
1
answer
134
views
Permutation graph with insert-and-shift
Motivation. I am working with a database software that allows
you to sort the fields of any given table in the following
peculiar way. Suppose your fields are numbered $1,\ldots, 18$.
Next to every ...
1
vote
0
answers
57
views
Primality testing by reversible computation using the prime number theorem
Suppose we want to build a primality testing algorithm for the numbers limited to the set $A =\{1, ..., 2^n\}$ and $n$ is reasonably large. The prime-number theorem tells us that there are ...
0
votes
0
answers
56
views
Pairs of permutations such that $p(n)<2^k$ iff $n<2^k$
Let $p(n)$ be an arbitrary permutation of natural numbers such that $p(n)<2^k$ iff $n<2^k$.
Let $q(n)$ be an inverse permutation of $p(n)$.
Let
$$
\ell(n)=\left\lfloor\log_2 n\right\rfloor
$$
...
2
votes
2
answers
73
views
Reference request for a subfamily of regular graphs
[Repost of same question math stack exchange which got no answers]
I'm looking for literature on the following family of graphs:
Call a regular graph $G=(V,E)$ (of regularity degree $d$) nice if there ...
4
votes
0
answers
135
views
Permutation generation problem using swaps
This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input.
We're given as input ...
0
votes
0
answers
121
views
Optimal strategy of modified Mastermind game
The following game is a modified version of the popular game Mastermind described here in which you are only given information about the total correct guesses you have made, and nothing about how many ...
4
votes
1
answer
221
views
Permutation of a mixture of (anti)commuting variables and consistency issue regarding the sign
I asked a similar question in PhysicsSE but it seems more like a mathematical issue, so I post here in a more refined form.
I am not confident if the below description of the problem makes sense. ...
4
votes
0
answers
193
views
Infinite groups with 2 automorphism orbits
A group $G$ is called a $k$-orbit group if its automorphism group ${\rm Aut}(G)$ acting naturally on $G$ has precisely $k$ orbits. The only finite 2-orbit groups are the elementary abelian groups $(...
8
votes
0
answers
148
views
Inversions for parity preserving presentations
I've gotten stuck on a slightly random combinatorial question, and I'm doing a bit of a shot in the dark here to see if someone else has thoughts about it. I'm interested in studying a permutation of ...
1
vote
2
answers
202
views
Relationship between fixed points and inversions in permutations
Inversions in a permutation $Y$ are defined as pairs where $Y_a < Y_b$ but $a > b$, while fixed points in $Y$ are defined as elements where $Y_a = a$ (i.e., 1-cycles). Let $S_\alpha$ be the set ...
1
vote
0
answers
101
views
Expected value of maximal cycle length in fixed-point free bijections
$\newcommand{\n}{\{1,\ldots,n\}}$
$\newcommand{\FF}{\text{FF}}$
$\newcommand{\lc}{\text{lc}}$
Motivation. A group of my son's peers decided to have a few days of Secret Santa before last year's ...
5
votes
1
answer
200
views
Non-adjacent permutations
Suppose we have an $N$ by $M$ table. Suppose that $x=(a,b)$ and $y=(c,d)$ are two locations in the table, specified by their row and column indexes. We say that (x,y) is horizontally adjacent if $c=...
2
votes
0
answers
81
views
Splitting natural numbers into subsets with sums equal to A066258
Let $F(n)$ be A000045 i.e. Fibonacci numbers. Here
$$
F(n) = F(n-1) + F(n-2), \\
F(0) = 0, F(1) = 1
$$
Let $a(n)$ be A066258 i.e.
$$
a(n) = F(n)^2F(n+1)
$$
Let $b(n)$ be A345253 i.e. maximal ...
2
votes
0
answers
59
views
Eulerian polynomial from Bruhat interval - h* of something?
Let $\sigma \in S_n$ be a fixed permutation.
Consider the polynomial
$$
P_{\sigma}(t) = \sum_{\substack{\pi \in S_n \\ \pi \leq \sigma}} t^{\textrm{des}(\pi)}
$$
where $\leq$ denotes Bruhat order, and ...
1
vote
0
answers
78
views
How can one build a min-2-wise independent small sample space from min-3-wise permutations?
I have been studying a polynomial-size set of permutations from one of my lectures. The below image, taken from the lecture notes PDF, illustrates how to construct min-3-wise permutations.
My ...
1
vote
0
answers
71
views
Slightly modified program for the A345253 such that specific partial sums equal A066258
Let $F(n)$ be A000045 i.e. Fibonacci numbers. Here
$$
F(n) = F(n-1) + F(n-2), \\
F(0) = 0, F(1) = 1
$$
Let $a(n)$ be A345253 i.e. maximal Fibonacci tree: arrangement of the positive integers as ...
3
votes
1
answer
347
views
Why is the permutation from inverses of $1/p$ mod elements of $\{2,\dotsc,p-1\}$ always product of 3-cycles?
Let $p$ be an odd prime and for $2 \le q<p$, let
$\genfrac(){}{}1 p_q$ be the unique integer $t \bmod q$ such that $pt=1 \bmod q$. If we write $pt=1+\alpha_qq$, then the map
$$\lambda_p:q-1 \...
30
votes
0
answers
790
views
Interpretation of "1089-number trick" in terms of symmetric group action on cohomology group?
I tried posting the following on math.stackexchange, but no answers. I can of course delete if inappropriate.
The "1089 number trick" (see e.g. here) says that if you take a three-digit ...
9
votes
0
answers
160
views
Are there fast rank and unrank algorithms for integer vectors under the action of a permutation group?
We are distributing $m$ indistinguishable balls in $k$ numbered boxes $S=\{1,2,\ldots,k\}$. A distribution is a tuple of nonnegative integers $a=(a_1,\ldots,a_k)$ whose sum is $m$. We also have a ...
2
votes
1
answer
57
views
Left-shift cycle generating maps $f:\{0,1\}^{c_0}\to\{0,1\}$ for fixed length $c_0$
This is a strengthening of an older question.
Is there a positive integer $c_0$ with the following property?
For every integer $n\geq c_0$ there is a function $f:\{0,1\}^{c_0}\to\{0,1\}$ such that ...
6
votes
1
answer
347
views
Maximizing a sum minus its maximal summand
This is a followup to a question that appeared on m.SE:
Maximize $\displaystyle f(\pi)=\left(\sum_{i=1}^{n}{i\pi_i}\right)-\max_{1\le i\le n}{(i\pi_i)}$ over permutations $\pi\in S_n$.
The problem ...
0
votes
0
answers
138
views
Dark side of the self-inverse permutation
Let
$$
\ell(n) = \left\lfloor\log_2 n\right\rfloor
$$
Let
$$
f(n) = 2^{\ell(n)}
$$
Let $p_1(n)$ be an arbitrary self-inverse permutation of the non-negative integers such that $p_1(n)<2^k$ iff $n&...
1
vote
0
answers
79
views
cycle types of all words in a permutation group
I have been working with permutation groups. For a given $G\subset S_n$, what I have been computing depends only on the conjugacy class of $G$.
Say all permutation groups in this question are ...
21
votes
1
answer
1k
views
Bubblesort with a twist: a tricky termination
Consider an $n$-tuple $\left(a_1, a_2, \ldots, a_n\right)$ of real numbers. We are allowed to perform the following two moves:
S-moves: We pick two adjacent entries $a_i$ and $a_{i+1}$ satisfying $...
1
vote
1
answer
231
views
Solve permutation matrix equations of the form: $X^T A X = B_1$ and $X A X^T = B_2$
I have a hard time solving the following two matrix equations for unknown permutation matrix $X \in \mathbb{R}^{n \times n}$:
$$X^T A X = B_1$$
$$X A X^T = B_2$$
where, $A$, $B_1$ and $B_2$ are all $n ...
0
votes
0
answers
113
views
Subgraphs of the Permutohedron
I've been looking at connected induced subgraphs permutohedrons (viewed as graphs). I was wondering if there's any research into this subject. Also if you have good sources about the permutohedron I ...
2
votes
0
answers
89
views
Unexpected recursion for the A193231 (blue code of $n$)
Let $a(n)$ be A193231, blue code of $n$ i.e. self-inverse permutation of non-negative integers such that $a(n)<2^k$ iff $n<2^k$ and
$$
a(n\operatorname{XOR}k) = a(n) \operatorname{XOR} a(k)
$$
...
1
vote
1
answer
105
views
Property of some permutations of non-negative integers such that $a(n)<2^k$ iff $n<2^k$
Let
$$
\ell(n) = \left\lfloor\log_2 n\right\rfloor
$$
Let
$$
f(n) = 2^{\ell(n)}
$$
Let $q_1(n)$ and $q_2(n)$ be an arbitrary self-inverse permutations of non-negative integers (that is, $q_i(q_i(n)) ...
0
votes
1
answer
101
views
Permutation of the natural numbers from operation related to binary expansion of $n$
Let
$$
\ell(n) = \left\lfloor\log_2 n\right\rfloor
$$
Let $T(n,k)$ be a $(k+1)$-th bit from the right side in the binary expansion of $n$. Here
$$
T(n, k) = \left\lfloor\frac{n}{2^k}\right\rfloor \...
2
votes
0
answers
49
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
141
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 ...
3
votes
0
answers
78
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
176
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
213
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
118
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
51
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
180
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
98
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
115
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
86
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
141
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
106
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
107
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
173
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
350
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
130
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 $...