自分で少し考えてみたのですが、どうでしょうか？

特定の2つの自然数p,qに注目し、互換(p,q)をXからYへの写像fと考える。

任意の異なる2つの偶順列に互換(p,q)を行うと異なる2つの奇順列が得られる。
また、任意の奇順列に対しては、ある偶順列が存在して、その偶順列に対して
互換(p,q)を行えばその奇順列が得られる。

したがって、fはXからYへの全単射であり、XとYの元の数は等しい。