The question is:
Let $S = \{a,b,c,d\}$ and let $X : = \{f\colon S \to S \mid f \, \, \text{is bijective and } f(x) \ne x \, \, \text{for each}\, \, x \in S \}$. What is $|X|$?
Is there a simple counting principle to use for this problem? I thought about it in terms of the cycles of $S_4$. Essentially we want to exclude all cycles that have $1$ fixed element. So all cycles of length $3$ and the identity are out. This leaves cycles of length $4$, of which I believe there are $6$ and the disjoint $2$-cycles $(14)(23)$, $(13)(24)$, $(12)(34)$. This gives the correct answer of $|X| = 9$ but I am wondering if there is faster way to think about this problem since if $|S| = 10 $ I don't want to count through the elements of $S_{10}$.
Best Answer
The most direct way to solve this is to consider the complement of the given set - that is, the bijections that do have a fixed points. $$Y=\{f:S\rightarrow S\mid f\text{ is bijective and }f(x)=x\text{ for some } x\in S\}.$$ Notice that if we define, for each $s\in S$ the set $$Y_s=\{f:S\rightarrow S\mid f\text{ if bijective and }f(s)=s\}$$ then we may express $$Y=Y_{s_1}\cup Y_{s_2}\cup Y_{s_3} \cup \ldots \cup Y_{s_n}.$$ where the $s_i$ enumerate the set $S$. From here, we just apply the inclusion-exclusion principle - we sum up the size of each set, subtract the size of each intersection of two sets, add the size of intersections of three and so on.
To do this, we merely note that any element of $Y_s$ is created by taking a bijection on $S\setminus\{s\}$ and then setting $f(s)=s$ - so there are $(n-1)!$ elements of each $Y_s$. (And there are $n$ such sets, so they contribute a total of $n!$ to the sum). Then, the intersection of two distinct sets $Y_{s}\cap Y_{s'}$ is just the set of functions with two given fixed points, so arguing similarly, there are $(n-2)!$ elements in each intersection. Given that there are ${n \choose 2}=\frac{n!}{2!\cdot (n-2)!}$ such intersections, we take away $\frac{n!}{2!}$ to account for these intersections. We can continue on in this manner, considering intersections of $k$ sets.
If you work through this, you get a not-too-horrible sum for the desired quantity. If you factor out $n!$, you will be left with a sum that may be familiar to you and would lead to a simpler closed form.