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 ...
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 ...
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 ...
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
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 ...
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 ...
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 $$ ...
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
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
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 $(...
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 ...
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
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=...
26 votes
6 answers
2k views

Why is the right permutohedron order (aka weak order) on $S_n$ a lattice?

This is one of those things I never expected to be hard until I tried to prove it. Why is the right permutohedron order (a.k.a. weak Bruhat order, a.k.a. weak order -- not to be confused with the ...
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 ...
5 votes
2 answers
879 views

Maximum distance within a subset of permutations

I'm modelling a scheduler that accepts a sequence of requests and outputs a sequence of responses, one response per request. It can partially reorder requests, but only within a finite queue. ...
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 \...
160 votes
37 answers
15k views

Conceptual reason why the sign of a permutation is well-defined?

Teaching group theory this semester, I found myself laboring through a proof that the sign of a permutation is a well-defined homomorphism $\operatorname{sgn} : \Sigma_n \to \Sigma_2$. An insightful ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
2 votes
1 answer
422 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 $...
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 ...
7 votes
1 answer
294 views

What is the Lie superalgebra generated by permutations?

Consider the group algebra of the symmetric group $\mathbb{C}S_n$. Then there is a corresponding Lie algebra $\mathfrak{L}(S_n)$ defined by $$[\sigma, \tau] = \sigma\circ\tau - \tau\circ\sigma,$$ ...
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 \...
16 votes
4 answers
635 views

Sets of points containing permutations - a Ramsey-type question

The following question arised as a side-question in a geometric problem. It has a "feel" similar to problems in Ramsey-theory, but I have not found any mention of it (also I'm not very familiar with ...
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\...
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 ...
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 (...
-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 ...

1
2 3 4 5
12