Questions tagged [permutations]
For questions related to permutations, which can be viewed as re-ordering a collection of objects.
13,317 questions
13
votes
3
answers
609
views
A problem about random permutations
The following question was asked by another user and then deleted. I liked my answer to the post, so I have made another post with the question and the answer. I am paraphrasing the question here, ...
- 485
1
vote
2
answers
97
views
A permutation $p_{1}, p_{2}, p_{3}, \dots p_{n}$ For each $i = 1, 2, 3, \dots, n-1$, $\exists j > i$ such that $\lvert p_{j} - p_{i} \rvert = 1$.
A permutation $p_{1}, p_{2}, p_{3}, \dots p_{n}$
For each $i = 1, 2, 3, \dots, n-1$, there exists a $j > i$ such that $\lvert p_{j} - p_{i} \rvert = 1$.
For example, the orderly permutation of $n = ...
- 21
0
votes
2
answers
82
views
Conflicting Results for Circular Seating Problem — Which Solution Is Correct? [closed]
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
100
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
37
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
30
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
125
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,047
1
vote
0
answers
44
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
20
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
144
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.7k
5
votes
1
answer
119
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
67
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
46
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
235
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
