5
$\begingroup$

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?

  • 0
    (The crosspost has been closed in the meantime.)2012-10-23

1 Answers 1

3

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$.