Questions tagged [permutations]
For questions related to permutations, which can be viewed as re-ordering a collection of objects.
13,319 questions
0
votes
2
answers
61
views
Conflicting Results for Circular Seating Problem — Which Solution Is Correct?
Question:Find the number of ways in which three americans, two british, one chinese, one dutch and one egyptiann can sit on a round table so that persons of the sme nationality are separated
what i ...
1
vote
0
answers
35
views
Reduced subword of a reduced word
Suppose that $v, w \in S_n$ such that $\ell(v) = \ell(w) + 2$ and $w < v$ in the Bruhat order. If $v = a_1 \cdots a_p$ is a reduced word for $v$, how many ways do we have to obtain $w$ as a reduced ...
- 131
0
votes
0
answers
49
views
Explicit automorphism of $\mathbb{C}$ which permutes two roots of a polynomial
Let $P$ be an irreducible polynomial of $\mathbb{Q}[X]$. Let $a, b$ be two roots of $P$.
Knowing a little bit of Galois theory, we know that $\mathrm{Aut}_{\mathbb{Q}}(\mathbb{C})$ acts transitively ...
- 660
0
votes
0
answers
36
views
Name for NPhard problems that ask for optimal permutations
Many hard combinatorial problems ask for an permutation that minimizes the value of a function $f:\pi\mapsto\mathbb{R}$ that maps permutations to real values, the most prominent being the TSP.
But ...
- 252
0
votes
0
answers
26
views
geometric hypercube defining vertices on a grid
Given $2^d$ points in n dimensions. $P \subset \mathbb R^n$, what is the most "meaningful" map $\varphi :\{0,1\}^d \to P$ so that $P$ can be interpreted as the vertices of a d-hypercube.
...
- 164
-1
votes
1
answer
106
views
Counting permutations where each element is the maximum or minimum of the prefix [duplicate]
I am trying to solve a combinatorial problem regarding a specific class of permutations.
The Problem:
Consider a permutation $\sigma$ of the set $\{1, 2, \dots, n\}$, where $n=13$.
The permutation ...
1
vote
0
answers
38
views
Constructive method for expressing arbitrary matrix permutations using cyclic row/column shifts
I am unsure which category this question best fits into, so I apologize in advance if this is not the ideal place to ask.
It is known (see for example:
Do cyclic permutations of rows and column ...
- 11
0
votes
0
answers
19
views
Even permutation decomposition
I was given this question in an assignment:
Given an even permutation sigma show that every even permutation tau can be written as $\rho^{-1}i\sigma\rho{i}$ where $\rho{i}$ is an even permutation
It's ...
- 1
0
votes
1
answer
138
views
Combinatoric solution to an Oxford interview question about replacing terms in a sequence
An Oxford interview question from a previous year goes like this:
"Starting with the sequence $1,2,\dots,n$, replace two arbitrary terms $x$ and $y$ with $x+y+xy$. Repeat this process until there ...
- 40.3k
5
votes
1
answer
110
views
Fixed-points-number distribution for strategically chosen permutation
Let $N \in \mathbb{N}$. We successively construct permutations $$A=(A_1, \dots, A_N), B = (B_1, \dots, B_N) \quad \in \text{Sym}(\{1, \dots, N\}).$$
At each time step $ 1 \leq n \leq N$,
We know $\{...
- 715
0
votes
0
answers
21
views
Orbits of a cyclic group on words of length $L$ with alphabet of size $k$ [duplicate]
Consider an alphabet $\Sigma$ of size $k=|\Sigma|$ and the set of words $\Sigma^L$ of length $L$, with the natural action of the cyclic group $\mathbb{Z}_L$ with generator $\tau$ acting naturally as $\...
- 399
0
votes
1
answer
65
views
Does function invariance under permutation imply existence of a stationary point invariant under permutation?
This question comes from the excellent introduction to mean-field spin glass methods by Montanari and Sen. Consider a function:
$$f\colon M_{n\times n}\longmapsto\mathbb{R}$$
which is invariant under ...
0
votes
0
answers
42
views
An extended problem related to Zolotarev's Lemma.
In the proof of Zolotarev's Lemma(Zolotarev's Lemma and Quadratic Reciprocity), it is first proven that the permutation $\tau_a: \mathbb{Z}_{\mathrm{p}} \rightarrow \mathbb{Z}_{\mathrm{p}}$, where ...
- 31
6
votes
2
answers
231
views
Distribution of number of ties in sum of two random permutations?
I have two random vectors $x$ and $y$ which are permutations of $\{1,...,n\}$. How is the number of ties in the component-wise sum $s$ with $s_i = x_i + y_i$ distributed? I am interested in the ...
- 91
4
votes
2
answers
447
views
Does creating groups with set permutations intrinsically satisfy more conditions than necessary? (How should I think about groups intuitively?)
When I think of any symmetric group $S_n$, I think of it (loosely speaking) as any group that contains all set permutations. Similarly I think of the cyclic group $C_n$ as any group that contains all ...
