Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $P_n$ denote the set of pairs $(x,y)$ of permutations on $S_{2n}$, where each permutation is a product of $n$ disjoint cycles of length two. Let i and j be two fixed elements of the set $\{1,2, \cdots,2n\}$. Select an element $(x,y)$ of $P_n$. What is the probability that the product $xy$ contains $i$ and $j$ in the same cycle?

share|improve this question
3  
Crosspost: mathoverflow.net/questions/110449/… –  Qiaochu Yuan Oct 23 '12 at 17:27
    
(The crosspost has been closed in the meantime.) –  joriki Oct 23 '12 at 18:51
add comment

1 Answer

Since every element other than $i$ has a $1$ in $2n-1$ chance of being $j$, the desired probability is $(a_n-1)/(2n-1)$, where $a_n$ is the expected length of the cycle containing $i$. Let $k=y(i)$. There is a $1$ in $2n-1$ chance that $x(k)=i$, in which case the cycle length is $1$. Otherwise swap $i$ and $x(k)$ in the cycle representation of $y$. Now both permutations have a two-cycle with $k$ and $x(k)$, the remaining cycles form two admissible permutations in $S_{2(n-1)}$, and the length of the cycle containing $i$ in their product is one less than the length of the cycle containing $i$ in the original product. This yields the recurrence

$$ a_n=1+\frac{2n-2}{2n-1}a_{n-1} $$

with the initial condition $a_1=1$, and it is readily checked that this is solved by $a_n=\frac13(2n+1)$. Thus the desired probability is

$$ \frac{\frac13(2n+1)-1}{2n-1}=\frac23\frac{n-1}{2n-1}\;. $$

It's interesting that the product can only contain cycles up to length $n$. For large $n$, the average length of the cycle containing $i$ is approximately $2/3$, so the probability for $j$ to be in it is approximately $1/3$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.