Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Crosspost:… – Qiaochu Yuan Oct 23 '12 at 17:27
(The crosspost has been closed in the meantime.) – joriki Oct 23 '12 at 18:51

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|cite|improve this answer

Your Answer


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.