Questions tagged [permutations]
Questions related to permutations, bijections from a finite (or sometimes infinite) set to itself.
591 questions
2
votes
2
answers
362
views
Worst-case number of single-card insertions to force Player 1 to be the unique winner in Texas Hold’em
Recently, I have been wondering about how to stack a deck in my favor using minimal moves for Poker. Concretely, I want to know if any deck can be stacked in my favor in 2 or 3 card moves. I have been ...
- 31
13
votes
1
answer
534
views
Order-universal permutation $\alpha:\omega\to\omega$
For the set $\omega$ of non-negative integers, we let $\newcommand{\oo}{[\omega]^\omega}\oo$ be the collection of infinite subsets of $\omega$. If $U\in \oo$, there is a unique order-preserving ...
- 54.6k
0
votes
0
answers
29
views
What to do with new LP formulations for optimal permutations
Question:
what, besides publishing, should I do with a new interpretation of how to formulate hard problems for optimal permutations with constraints on the cycle structure?
Currently I have ...
- 14k
6
votes
3
answers
499
views
Calculating probabilities for the naive Fisher-Yates shuffling algorithm
The Fisher-Yates shuffle is the standard implementation for randomly permuting a finite list of $n$ elements. The algorithm has several incorrect implementations, one being that in each step permuting ...
- 241
13
votes
0
answers
320
views
Equations in the permutation group
Let $n \in \mathbb N$ and let $\sigma,\tau \in {\rm Sym}(n)$. I am looking for a permutation $x \in {\rm Sym}(n)$ that minimizes the Hamming distance between $x^2 \sigma$ and $\tau x$. Here, the ...
- 26.3k
1
vote
0
answers
101
views
How to split discrete torus braids of size $k$ resulting from symmetric group $S_n$ action on $[n]$
Consider the symmetric group $S_{2n}$ and $[2n]:=\lbrace 1,..,2n\rbrace$. All notations regarding the symmetric group come from its action on the set $[2n]$. We define discrete torus braids of size $k$...
- 377
15
votes
0
answers
315
views
Guessing a permutation in a way analogous to Wordle
Let $w$ be a permutation of $\{1,2,\dots,n\}$ chosen uniformly at
random. You have to determine $w$ by successively guessing
permutations $v_1, v_2, \dots$. After each guess $v_j$ you are told
where $...
- 53.7k
0
votes
0
answers
102
views
Recursion for A375838
Let
$T(n,k)$ be A375837, i.e., triangle read by rows: $T(n,k)$ is the number of rooted chains starting with the cycle $(1)(2)(3)\dotsc(n)$ of length $k$ of permutation poset of $n$ letters.
$a(n)$ be ...
user231922
4
votes
1
answer
200
views
Sign of the permutation mapping a row-major tableau to a column-major tableau
Consider the Young diagram of an integer partition $\lambda \vdash n$. I can fill the boxes of the Young diagram with the integers $1,2,\ldots,n$ in row-major order (i.e., in increasing order row-by-...
- 2,202
10
votes
1
answer
369
views
Distribution of descents of random permutations
Consider a uniform random permutation of $\{1,\dots, n\}$, and let $D_n$ be its number of descents (indices $i$ such that $\sigma(i)>\sigma(i+1)$). There is a nice result by Tanny where they show ...
- 103
4
votes
0
answers
167
views
On the coverage of permutations by argsort of polynomial evaluations
Let $s = (s_1, s_2, \ldots, s_N) \in \mathbb{R}^N$ be a fixed vector with distinct elements.
We define the label $l(s) = (l_1, \ldots, l_N) \in \{1, \ldots, N\}^N$ as the argsort of $s$, i.e., the ...
- 4,150
0
votes
1
answer
268
views
Lengths of arithmetical sequences and arithmetical images for bijections $\varphi:\mathbb{N}\to\mathbb{N}$
We call a finite subset $S\subseteq \mathbb{N}$ arithmetical if there are $n, k\in\mathbb{N}$ with $k>1$ such that $S = \{n+j: 0 \leq j\leq k\}$.
Given an integer $\ell>0$ and a bijection $\...
- 54.6k
2
votes
0
answers
220
views
Matrix shuffling by shifting rows and columns
Let $M$ be an $n \times m$ matrix, with $1, \dots, m$ in the first row, $m+1, \dots, 2m$ in the second row, etc.
$$M = \left[
\begin{array}{c}
1 & 2 & \dots & m \\
m+1 & m+2 & \...
- 51
2
votes
0
answers
110
views
Conjugation of Bruhat cells?
Consider the Bruhat decomposition of a simple linear algebraic group $G$:
$$G = \bigsqcup_{w\in W} B w B.$$
There are rules for multiplying two elements $g_1 \in B w_1 B$, $g_2\in B w_2 B$, in the ...
- 22k
8
votes
1
answer
406
views
A new generalization of Eulerian numbers
I recently became aware of the paper, The Geometry and Combinatorics of Some Hessenberg Varieties Related to the Permutohedral Variety, by Jan-Li Lin. In it, the author defines prepermutohedral ...
- 89k