What is the probability that the selected function maps prime numbers to prime numbers? Let $X = \{1, 2, 3, . . . , 25\}$. If a student selects a function randomly from the set of all functions from $X$ onto $X$, then what is the probability that the selected function maps prime numbers to prime numbers ?
No idea how to proceed, please guide.
 A: There is a trap in this question. The keyword in the question is the word $\color{red}{onto}$. This means we are not looking at any functions from $X$ to $X$. Instead, we are only
looking at functions $\pi : X \to X$ which is surjective. Since $X$ is finite, this means $\pi$ is also bijective. ie. $\pi$ is a permutation of the $25$ elements of $X$.
There are $|X|! = 25!$ of them. 
Let $P = \{ 2, 3, 5, 7, 11, 13, 17, 19, 23 \} \subset X$ be the subset of primes in $X$.
Let $\pi$ be any permutation of $X$ which sends $P$ into a subset of $P$.


*

*Since $\pi$ is a bijection and $P$ is finite, $\pi(P) \subset P \implies \pi(P) = P$.
This implies when we restrict $\pi$ to $P$, $\pi\mid_{P}$ is a bijection.

*Similarly, we have $\pi(X\setminus P) = X \setminus P$ and $\pi\mid_{X\setminus P}$ is also bijective. 

*Conversely, given any two bijections $f : P \to P$ and $g : X\setminus P \to X \setminus P$, we can "glue" them together to get a bijection over whole $X$.


Combine all these, we can conclude there are $|P|! \times |X\setminus P|! = 9! 16!$ bijections on $X$ which map primes into primes. As a result, the probability is $$\frac{16!9!}{25!} = \frac{1}{\binom{25}{9}}.$$
A: It doesn't matter where the function maps the non-primes, so you can forget about those.
The number of ways of mapping the prime numbers to the prime numbers is $9^9$.  The number of ways of mapping the prime numbers to anything is $25^9$.  Divide the two to get your answer.
