2
$\begingroup$

Let's say $S_n$ is the set of all permutations of {1,2,...,n} without fixed points.

Now what I want to find out is the number of pairs of permutations $(\sigma,\mu)$ where

$$\sigma, \mu \in S_n$$ and $$\mu(\sigma(i))\neq i$$ for every $i\in \text{{1,2,...,n}}$

For example, for the case n=3, only two pairs ($\sigma_1$,$\sigma_1$) and ($\sigma_2$,$\sigma_2$) satisfies all the conditions where $$\sigma_1:=\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$$ $$\sigma_2:=\begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}$$

$\endgroup$
  • $\begingroup$ I do know the number of elements in Sn $\endgroup$ – UJung Jul 21 '18 at 13:47
  • 2
    $\begingroup$ If $\mu$ and $\sigma$ are permutations without fixed points isn't the condition $\mu(\sigma(i))\neq\sigma(i)$ automatic? Otherwise $\sigma(i)$ would be a fixed point of $\mu$, no? $\endgroup$ – Jyrki Lahtonen Jul 21 '18 at 13:48
  • $\begingroup$ For the number of permutations without fixed points see this thread. As you only seem to need both $\mu$ and $\sigma$ not to have any fixed points then that answers the question (but not in an entirely helpful form). $\endgroup$ – Jyrki Lahtonen Jul 21 '18 at 13:53
  • $\begingroup$ See also here. $\endgroup$ – Jyrki Lahtonen Jul 21 '18 at 13:54
  • 1
    $\begingroup$ Thanks, @joriki. No problem, really. I was expecting this edit since I saw Joffan and Ross Millikan comment. My interpretation didn't match with the single given data point. I only noticed that too late, i.e. after posting the answer. $\endgroup$ – Jyrki Lahtonen Jul 21 '18 at 19:19

Your Answer

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

Browse other questions tagged or ask your own question.