Questions tagged [permutations]

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

Filter by
Sorted by
Tagged with
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 ...
NathanLiitt's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Notamathematician's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
user1747134's user avatar
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 $$ ...
Notamathematician's user avatar
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 ...
jojo's user avatar
  • 21
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 ...
Mohammad Al-Turkistany's user avatar
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 ...
wjmccann's user avatar
  • 315
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. ...
Isaac's user avatar
  • 2,727
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 $(...
Glasby's user avatar
  • 1,961
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 ...
Ben Webster's user avatar
  • 43.9k
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 ...
virtuolie's user avatar
  • 173
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 ...
Dominic van der Zypen's user avatar
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=...
Bill Bradley's user avatar
  • 3,809
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 ...
Notamathematician's user avatar
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 ...
Per Alexandersson's user avatar
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 ...
A. H.'s user avatar
  • 15
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 ...
Notamathematician's user avatar
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 \...
CHUAKS's user avatar
  • 755
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 ...
mnmse475's user avatar
  • 301
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 ...
Jukka Kohonen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Alexander Burstein's user avatar
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&...
Notamathematician's user avatar
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 ...
Pierre's user avatar
  • 2,145
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 $...
darij grinberg's user avatar
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 ...
Danish's user avatar
  • 11
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 ...
smoneh's user avatar
  • 11
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) $$ ...
Notamathematician's user avatar
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)) ...
Notamathematician's user avatar
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 \...
Notamathematician's user avatar
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\...
Joseph Van Name's user avatar
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 ...
Honglian's user avatar
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 ...
Dmytro Taranovsky's user avatar
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 ...
Dominic van der Zypen's user avatar
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 (...
Dominic van der Zypen's user avatar
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 ...
rbssmtkr's user avatar
-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?
strijelaš 's user avatar
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 ...
Antonio Lorenzin's user avatar
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 ...
Juan Moreno's user avatar
-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? ...
Math_deep's user avatar
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 ...
Camilo Argoty's user avatar
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 ...
Kaiyue Wen's user avatar
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$...
Petya's user avatar
  • 4,686
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 ...
joro's user avatar
  • 24.2k
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 $...
Roland Bacher's user avatar
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 ...
Talesseed's user avatar
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 ...
Command Master's user avatar
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 $...
SiXUlm's user avatar
  • 101

1
2 3 4 5
12