Questions tagged [permutations]
Questions related to permutations, bijections from a finite (or sometimes infinite) set to itself.
579 questions
1
vote
1
answer
52
views
Comparability of elements in a Latin square based on a few rows
Let $\Pi=\{\pi_1,\pi_2,\dots,\pi_n\}$ be the rows of an $n\times n$ Latin square (the order of the rows does not matter).
Each row $\pi_i$ induces an order $\prec_i$ on the elements of $[1,n]$, where $...
- 235
2
votes
0
answers
104
views
Find an $a \times m$ submatrix of an $n \times m$ matrix with smallest rank
Given a matrix $n \times m$, I want to find the submatrices $a \times m$ by selecting $a$ columns such that their rank is minimal. Can this problem be solved efficiently?
- 1,207
0
votes
1
answer
99
views
Only special permutations result in a constant expression when permuting coefficients in a sum involving binomials?
Fix $n\geq 1$ and let $p_k(x) := x^k(x-1)^{n-k}$.
Suppose $\pi$ is a permutation on $\{0,1,\dotsc,n\}$, such that
$$
\sum_{k=0}^n (-1)^k \binom{n}{k} p_{\pi(k)}(x) \text{ is a constant}.
$$
Must it be ...
- 15.8k
3
votes
0
answers
93
views
Realized graph of majority of permutations
This question was asked several months ago on Math.SE, but remains unsolved.
For any collection of permutations of $\{1,2,\dots,n\}$, we say that it realizes a directed multigraph with $1,2,\dots,n$ ...
- 277
1
vote
1
answer
77
views
Enumeration of permutations with prescribed numbers of fixed points and excedance/deficiency statistics
Consider the following refinement of permutation statistics. For $π ∈ S_n$, let:
$\mathrm{fix}(π) = |\{i : π(i) = i\}|$ (number of fixed points)
$\mathrm{exc}(π) = |\{i : π(i) > i\}|$ (number of ...
- 11
10
votes
0
answers
250
views
Permutation of positive integers
Let $a_n$ be a sequence such that $a_1=1$ and for each $n \geq 1$ $a_{n+1}$ is the smallest positive integer distinct from $a_1,a_2,...,a_n$ such that $\gcd(a_{n+1}a_n+1,a_i)=1$ for each $i=1,2,...,n$....
- 3,153
19
votes
4
answers
1k
views
Generalization of a mind-boggling box-opening puzzle
Motivation. Suppose we are given $6$ boxes, arranged in the following manner:
$$\left[\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \end{array}\right]$$
Two of these boxes contain a ...
- 48.9k
4
votes
0
answers
124
views
LIS-based permutation property
Let $S_n$ be the set of all permutations of $\{1, \ldots, n\}$, thereafter treated as integer sequences. Let $A_n$ be the set of all such permutations $\sigma \in S_n$ that we can choose two ...
- 5,590
4
votes
0
answers
92
views
Reference for fact about flags of vexillary permutations
Vexillary permutations are an important family of permutations in Schubert calculus. There are several definitions, for example that they avoid the pattern 2143.
Recall the Lehmer code of a ...
- 1,989
1
vote
0
answers
118
views
Can we construct the circular permutation from partial partition info?
Imagine a circular permutation of n points on a circle, if we draw a line connecting any pair of points, the rest of the points are divided into two sets that are on the same side. We can partition a ...
- 11
2
votes
0
answers
71
views
Are the ranks of the following matrices given by these simple expressions?
The question itself is formulated in the title, so below I specify the matrices and expressions mentioned there. In case if this is something known or can be easily deduced from something known, this ...
- 321
0
votes
0
answers
95
views
Nested Set Permutations and their Enumeration
Let $(S_i)_{i \in \mathbb{N}}$ be a sequence of sets defined recursively as follows:
$S_1 = \{1\}$
$S_{i+1} = S_i \cup \{S_i, i+1\} \quad \forall i \in \mathbb{N}$
A permutation $\sigma$ of $S_i$ is ...
- 1
4
votes
1
answer
182
views
Permutations of the natural numbers with a common conditionally convergent series
Let $S\subset S_{\infty}$ be a set of permutations of $\mathbb{N}$. A real series $\sum_{n\geq0}u_{n}$ will be called $S$-conditionally convergent if it is absolutely divergent and if, for all $\sigma\...
- 105
2
votes
1
answer
276
views
Probability of visible permutations
A visible permutation $\sigma$ of $[1,2, ...,n]$ has a permutation matrix such that all "1" locations are visible from the origin $(0,0)$.
Two "1" locations are visible if the two ...
- 2,993
6
votes
0
answers
254
views
Maximal bijection-dodging families on $\mathbb{N}$
We say that a family ${\cal S}\subseteq{\cal P}(\mathbb{N})$ is bijection-dodging if there is a bijection $\varphi:\mathbb{N}\to\mathbb{N}$ with $\varphi(T)\notin {\cal S}$ for all $T\in{\cal S}$.
...
- 48.9k
42
votes
2
answers
2k
views
How decreasing can a bijection $f:\mathbb{N}\to\mathbb{N}$ be?
This is a follow-up to this question by
Dominic van der Zypen. For each bijection $f:\mathbb{N}\to\mathbb{N}$, let
$$\operatorname{rc}(f) := \liminf_{N\to\infty} \frac{\left|\left\{(m,n)\in\{1,\dots,N\...
- 10.6k
9
votes
1
answer
460
views
Min–max reversing bijections $f:\mathbb{N}\to\mathbb{N}$
For any set $X$, let $\newcommand{\N}{\mathbb{N}}[X]^2 = \big\{\{x,y\}:x\neq y \in X\big\}$ and set $[n]^2 = [\{0,\dotsc,n-1\}]^2$ for any positive integer $n$. For $A\subseteq [\N]^2$ we set $$\...
- 48.9k
8
votes
2
answers
509
views
Bijection $\varphi:\mathbb{N}\to\mathbb{N}$ that distorts every finite arithmetic progression
Let $\mathbb{N}$ denote the set of non-negative integers. We say $A\subseteq \mathbb{N}$ is a finite arithmetic progression if there are $a, n, d\in\mathbb{N}$ with $d \geq 1$ and $n \geq 2$ such that ...
- 48.9k
1
vote
1
answer
200
views
Sign of the permutation when I show that $\star{\star w}= (-1)^{n(n-k)} w$ for the Hodge operator
Let $w=\sum_{I} a_{I}dx_{I}$ be a $k$-form in $\Bbb R ^n$. Let us consider the Hodge operator in a combinatorial form, i.e. as an $(n-k)$ form such that
$$\star(dx_{i_{1}} \wedge \dotsb \wedge dx_{i_{...
- 251
1
vote
0
answers
50
views
Computational complexity of deciding if two elements are in the same cycle of a permutation, version 2
This question has relation with this previous one, although the two cases are not likely solved with the same method.
Let us consider a function $P:\{0,1\}^*\to\{0,1\}^*$ that can be calculated in ...
- 469
5
votes
1
answer
175
views
Computational complexity of deciding if two elements are in the same cycle of a permutation
Given $n\in \mathbb{N}$, we have a bijection $P:\{0,1\}^n\to\{0,1\}^n$, i.e. $P$ is a permutation of $2^n$ symbols, $P\in S_{2^n}$. The permutation $P$ can be calculated efficiently, i.e. by a ...
- 469
-4
votes
1
answer
197
views
How to express a quadratic polynomial exactly as a power series [closed]
I claim, for $\operatorname{artanh}(\rho) = \frac{1}{2} \ln\left(\frac{1+\rho}{1-\rho}\right)$, i.e., the inverse hyperbolic tangent function, the following holds approximately under assumptions given ...
- 183
11
votes
1
answer
1k
views
Order of the "children's card shuffle"
Motivation. My eldest son thinks the following procedure is a "perfect shuffle" for a deck of cards: Take the first card, put the second on top of it, put the 3rd below cards 2 and 1, put ...
- 48.9k
5
votes
1
answer
213
views
Partition an $(2n+1)$-permutation into two parts in which there are no three consective elements in given sequences
Let $a_1a_2\ldots a_{2n+1}$ ($n\geq 2$) be a given permutation of the numbers from $1$ to $2n+1$ and let
$\alpha_i=\{i,i+1,i+2\},~1\leq i\leq 2n-1$
$\alpha_{2n}=\{2n,2n+1,1\}$
$\alpha_{2n+1}=\{2n+1,1,...
- 557
2
votes
1
answer
330
views
Transversal of $\mathbb{N}\times\mathbb{N}$
Motivation. I am trying to make an interesting infinite version out of this fascinating problem from the Russian mathematical olympiad:
There are $c$ flavours of cookies, we are given $n$ cookies of ...
- 48.9k
0
votes
1
answer
211
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
149
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 ...
- 48.9k
1
vote
1
answer
168
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 ...
- 48.9k
1
vote
0
answers
68
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 ...
- 283
0
votes
0
answers
63
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,938
2
votes
2
answers
77
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 ...
- 21
4
votes
0
answers
155
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 ...
- 2,993
0
votes
0
answers
193
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 ...
- 315
4
votes
1
answer
228
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. ...
- 3,477
4
votes
0
answers
214
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,991
8
votes
0
answers
171
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 ...
- 44.7k
2
votes
2
answers
273
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 ...
- 183
1
vote
0
answers
107
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 ...
- 48.9k
6
votes
1
answer
228
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=...
- 3,979
2
votes
0
answers
91
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 ...
- 4,938
2
votes
0
answers
64
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 ...
- 15.8k
1
vote
0
answers
84
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 ...
- 43
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 ...
- 4,938
3
votes
1
answer
360
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 \...
- 1,362
30
votes
0
answers
814
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 ...
- 301
9
votes
0
answers
180
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 ...
- 4,219
2
votes
1
answer
60
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 ...
- 48.9k
6
votes
1
answer
372
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 ...
- 1,190
1
vote
0
answers
94
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 ...
- 2,287
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 $...
- 33.8k