QB1
10 marks
Permutations & Arrangements
Counting Functions with Constraints
View
For a natural number $n$ denote by $\operatorname{Map}(n)$ the set of all functions $f : \{1,2,\ldots,n\} \rightarrow \{1,2,\ldots,n\}$. For $f, g \in \operatorname{Map}(n)$, $f \circ g$ denotes the function in $\operatorname{Map}(n)$ that sends $x$ to $f(g(x))$.
(a) Let $f \in \operatorname{Map}(n)$. If for all $x \in \{1,\ldots,n\}$ $f(x) \neq x$, show that $f \circ f \neq f$.
(b) Count the number of functions $f \in \operatorname{Map}(n)$ such that $f \circ f = f$.