1
$\begingroup$

A basic result in combinatorics is:

In $S_n$ there are

  • $(n-d)(n-2)!$ permutations $\sigma$ such that $\sigma^k(a) = b$, if $a \neq b$;
  • $d(n-1)!$ permutations $\sigma$ such that $\sigma^k(a) = b$, if $a = b$,

where $d$ is the number of positive divisors of $k$.

This lemma makes me wonder:

In $S_n$ how many permutations $\sigma$ are there such that $$\sigma^k(a) = \sigma^h(b),$$ where $k \neq h$ (and $a = b$ or $a \neq b$)?

$\endgroup$
1
$\begingroup$

Since $\sigma$ is bijective, you can apply $\sigma^{-h}$ to transform this to

$$ \sigma^{k-h}(a)=b\;, $$

thus reducing it to the result you quoted.

$\endgroup$
  • 1
    $\begingroup$ Of course, you're right! Thanks! $\endgroup$ – user310769 Feb 4 '16 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy