All Questions
11 questions
1
vote
1
answer
177
views
What is the function defined by f(k) = #σ1({1,2,…,k})∩σ2({1,2,…,k})∩{1,2,…,k}, where σ1,σ2 are a uniformly random permutations of size N?
Thanks to David Pechersky excellent answer we know that
expectation of $ | σ({1,2,…,k}) ∩ \{1,2,…,k \} | \rightarrow k^2/N$ for σ uniformly random permutation over $N$.
What about the same ...
- 24.9k
1
vote
1
answer
241
views
What curve is defined by the formula $f(k) ={}$length of intersection of the first $k$ elements for two random permutations?
Let us fix $N$. Note that function $f$ defined below will satisfy $f(0)=0, f(N) = N$ and it is monotonically increasing (not strictly).
The code for the function seems to me more clear way to ...
- 24.9k
3
votes
1
answer
135
views
Cycle counts in Ewens measure as $\theta$ diverges
For $w$ a permutation, let $c(w)$ denote the total number of cycles and $c_i(w)$ denote the number of $i$-cycles.
The Ewens measure is a one-parameter probability distribution on permutations where ...
- 1,989
8
votes
2
answers
475
views
Random permutations without double rises (avoiding consecutive pattern $\underline{123}$)
A permutation avoiding a consecutive pattern $\underline{123}$ is permutation
$\pi = \pi_1 \pi_2 \ldots \pi_n$ with the property that there does not exists $i \in [1, n-2]$
such that $\pi_i < \pi_{...
- 345
5
votes
1
answer
250
views
Dealing cards numbered $1$ to $n$ into piles
Is anything known about the following?
I hold in my hand a shuffled pack of cards numbered $1$ to $n$. One by one, I place them all, face up, on a table in piles. For each card I deal from my hand, ...
- 3,707
3
votes
0
answers
80
views
Counting sets whose alternation is preserved by a permutation
Say a set $X \subseteq \{1,\ldots,n\}$ is alternating if successive elements of $X$ are of opposite parity. That is to say for any $x \in X$, if $y = \min \{z \in X \mid x < z\}$ then $x \not\...
- 31
12
votes
2
answers
947
views
How rare are unholey permutations?
For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$.
Given a permutation $\pi$ of $[n]$, we define the holeyness $D(\pi)$ of $\pi$ as being $...
- 20.2k
4
votes
0
answers
216
views
How frequent are permutations with small interleaving?
For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$.
Let $\pi$ be a permutation of $[n]$. For simplicity, assume that $\pi$ is an $n$-cycle. ...
- 20.2k
4
votes
1
answer
196
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 ...
- 41
6
votes
1
answer
500
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$ ...
- 20.2k
5
votes
1
answer
2k
views
Number of Permutations with k-inversions and with a single clamped value
This question is cross-posted from math.stackexchange because it might be too technical.
Let $S_n$ be the symmetric group. Recall that the number of inversions of a permutation $\sigma\in S_n$ is the ...
- 4,952