# Questions tagged [random-permutations]

The tag has no usage guidance.

40 questions
Filter by
Sorted by
Tagged with
52 views

### Multiplication on a group of given cardinal and random permutations

Let $n$ be an integer, that we assume to be large (the order of magnitude for the motivation about the question is about 2^100). For the purpose of random automatic program certification, I need to be ...
311 views

73 views

### Number of cells in array covered by a random permutation

Consider a set $A \subseteq [n] \times [n]$ with $|A| = a = \alpha n$ for some $\alpha \in [0,1]$. Suppose we select a permutation $\pi \in S_n$ uniformly at random. This permutation $\pi$ can also be ...
95 views

### Expected position in random permutation

Let $S$ be a set of $n$ numbers, and $\pi(x):S\rightarrow \left\{ 1,\ldots,n\right\}$ define a permutation. The position $p(x, \pi)$ of an element $x \in S$ in a given permutation $\pi$ is the sum of ...
128 views

913 views

167 views

### Generating bitstring combinations using a butterfly network

I'm using a butterfly network to generate a random combination of a bitstring of length $n$ and weight $w$. Let me clarify it with an example. Suppose I want a random bitstring of length 8 and Hamming ...
430 views

### Rank and frequency of permutations

(a) Let $[n] = \{1,\dotsc,n\}$, and let $\pi:[n]\to [n]$ be a permutation. Define an $n$-by-$n$ matrix $A=A(\pi)$ as follows: $A_{i,j}=1$ if $j>i$ and $\pi(j)>\pi(i)$, $A_{i,j}=-1$ If $j<i$ ...
101 views

### Another question on provable non-existence of an efficient deterministic numerical method

Herewith I submit what may or may not be considered a simpler version of this question. The question is whether it is provable that there is no efficient deterministic numerical method for a ...
168 views

### What is the expected minimum total matching distance between two partitions of identically and independently distributed points?

Suppose a square $[0,1]\times [0,1]$ in which $N$ vehicles $V_i$ and $N$ riders $R_i$ are distributed identically and independently (say, uniform distribution), a bipartite matching (or a permutation, ...
353 views

183 views

### A question about permutation matrices

This question is trying to abstract out in a self-contained way the point that is probably being made in page 6 of this paper, https://arxiv.org/pdf/1604.03544.pdf and why Theorem 4.1 there works. ...
686 views

### Girth of the symmetric group

Let $n \in \mathbb N$ and $\{\sigma,\tau\} \subset {\rm Sym}(n)$ be a generating set. Question: What is the maximal possible girth (if one varies $\sigma, \tau$) of the associated Cayley graph? I ...
151 views