The number of fixed points of an involution on a finite set has the same parity as the cardinality as the set What is wrong with the following proof-probably familiar to many? Assume that $S$ is a finite set and that $f:S\rightarrow{S}$ is a bijection. Let ${\rm{Fix}}{f_{S}}$ denote the set of fixed points of $f$. Then the union of $$\{\{s,f(s)\}:s\in{S}\}$$ can be written as the disjoint union of ${\rm{Fix}}{f_{S}}$, and its complement in $S$, say $S'$. Since $S'$ is the finite union (say $r$ of them) of sets of the form $\{s,f(s)\}$ each of which contains two elements, we conclude that $|S|=|{\rm{Fix}}{f_{S}}|+2r$. Thus, $|S|-|{\rm{Fix}}{f_{S}}|=2r$, and so $|S|\equiv|{\rm{Fix}}{f_{S}}|({\rm{mod}})2.$
I have seen this argument prove that for an involution $f$ of a finite set $S$ that cardinality of $S$, and the cardinality of the set of its fixed points have the same parity. My question is where do we use the fact that $f$ is an involution (i.e. $(f\circ{f})$ is equal to the identity mapping $S\rightarrow{S}$) in this proof?
 A: Try an example where $f$ is not an involution and the result is clearly false. Simplest is a 3-cycle where $S = \{a,b,c\}$, $f(a)=b$, $f(b)=c$, and $f(c)=a$. There are 0 fixed points but $|S|=3$, so the parities of $S$ and the set of fixed points of $f$ are different. You should see where the proof goes wrong.
A: $S'$ is a union of $r$ sets of the form $\{s,f(s)\}$, but these sets may not be disjoint and so you cannot conclude that $|S'|=2r$.  Indeed, the sets $\{s,f(s)\}$ and $\{t,f(t)\}$ will overlap if $t$ happens to be equal to $f(s)$ (or $s$ happens to be equal to $f(t)$, or if $s=t$ but that case is trivial).  If $f$ is an involution, you know that $f(f(s))=s$, so when $t=f(s)$ the sets $\{s,f(s)\}$ and $\{t,f(t)\}$ will actually be the same set.  However, if $f$ is not an involution, you could have two different sets $\{s,f(s)\}$ and $\{f(s),f(f(s))\}$ which are not disjoint.
A: Counter example:
Consider $S_6$, the permutation group on 6 elements and the cycle $(123)\in S_6$. If we calculate $Fix(f)$, it turns out to be $\lbrace 4,5,6 \rbrace$ which has an odd number of elements. So, the parities are not same, which shows the statement in the question is false.
Breaking the problem down: Essentially, given a bijection $f$ of a finite set $S$ with $|S|=n$, then $f\in S_n$. Now, method of proof says that there is a representation of $f\in S_n$ which is the product of disjoint cyclic elements of the form $(a_1 a_2 \cdots a_k)$. Look at $(12)(34)(5678)\in S_n$ for very large $n$, for example. It carries first element to the second and the second to the first and so on, under the bijection. This bijection fixes every element that is not in the first 8. It changes an even no. of elements. So, the parity of the whole set and fixed point set will be the same. Why? Because 'Fixed Points' + 'Non fixed points' is the whole set $S$.
Now, if we ensure that the 'Non fixed points' set is of even parity, then we are done. One way of doing that is claiming that the bijection is an involution. Then, the cyclic decomposition will have $2-cycles$ apart from the fixed points, which forces 'Non fixed points' to be even. However, this isn't the only way to ensure such a thing.
A general result: The most general criteria for the parity of the fixed points $Fix(f)$ and the whole set $S$ to be the same is if the number of odd cycles of length $\geq 3$ in the cyclic decomposition is even. The identity and involution bijections are the most trivial ones because they have no cycles of length $\geq 3$. There are other examples such as $(123)(456) \in S_9$ which aren't involutions but the parity is the same.
A: It's true if you know that $f$ has order a power of $2$ ( or more generally, if a group acting on your set has order a power of $2$).  Otherwise the nontrivial orbits might have  an odd size.
So, for instance, if $f$ is an involution  (order $2$) , then any orbit has size $1$, or $2$.
If $f$ has order $4$, then any orbit has size a divisor of $4$, so either $1$, $2$, or $4$.
Orbit of size $1$ corresponds to a fixed point.
