The permutation is given. For how many functions $f:\Bbb{N_{10}} \rightarrow \Bbb{N_{10}}$ are $f(\pi(i))=\pi(f(i))$?

Question

The permutation $\pi\in S_{10}$ is given by the table:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \pi & 9 & 7 & 10 & 4 & 8 & 1 & 2 & 5 & 6 & 3\\ \hline \end{array}

For how many functions $f:\Bbb{N_{10}} \rightarrow \Bbb{N_{10}}$ are $f(\pi(i))=\pi(f(i))$, where $i \in \Bbb{N_{10}}$?

Hi, this is a question from a old exam in my course. I know that the answer is $1372$ functions, however I can't follow the explanation that is given. Thus I come to this place and hope that someone can give an answer and an explanation that is easy to follow and understand.

Thanks!

Answer 1

I'll assume that you know how to decompose a permutation into cycles (if it is more familiar, this is the same as the decomposition of $\mathbb{N}_{10}$ into orbits under the action of $S_{10}$ on $\mathbb{N}_{10}$).

For $\pi$, the cycle decomposition is

$\pi = (196)(27)(3 10)(4)(58)$

Now, make the following two observations:

1. For each cycle, the image of a single element of that cycle under $f$ determines the images of every other element of the cycle.

For example, suppose we know that $f(1) = j$. Then $f(9) = f(\pi(1)) = \pi(f(1)) = \pi(j)$ and $f(6) = f(\pi(9)) = \pi(f(9)) = \pi(\pi(j))$.

So once we decide on $f(1)$, the images of $f(9)$ and $f(6)$ are completely determined.

Similarly, $f(2)$ is determined by $f(7)$, $f(3)$ is determined by $f(10)$ and so on.

2. The length of the cycle that the element $f(j)$ is contained in divides the length of the cycle that the element $j$ is contained in.

This is because by induction for any $r \geq 1$, we have $f(\pi^r(j)) = \pi^r(f(j))$. So if $\pi^r(j) = j$, we also have $\pi^r(f(j)) = f(\pi^r(j)) = f(j)$.

So again

$\mbox{length of cycle of } f(j) | \mbox{length of cycle of } j$

---

Now we can count how many functions there are that satisfy the required properties.

By 1, it is enough to decide the images of 1,2,3,4 and 5.

By 2, the length of the cycle of $f(1)$ divides 3, so the length is either 1 or 3. So $f(1) = 1,9,6$ or $4$.

Then, the length of the cycle of $f(2)$ divides 2, so the length is 1 or 2. So $f(2) = 2,7,3,10,4,5$ or 8.

Similarly for $f(3)$ and $f(5)$ since those are contained in cycles of length 2.

Finally, $f(4) = 4$ is the only possibility for $f(4)$, since the length of a cycle that contains $f(4)$ must be 1, i.e. it is a fixed point, and there is a unique fixed point.

So altogether the number of choices is

$4 \cdot 7^3 = 1372.$