Number of involutions by combinatorial

Question

Let $_$ be the number of involutions in $\sigma_n$. Show that $_0 = _1 = 1$ and for $ \geq 2$ $_ = _{−1} + ( − 1)_{−2}.$

Answer 1

Let $f$ be an involution on $\{1,2,...,n\}$.

Then, only two things could happen with $f(n)$:

• Either $f(n)=n$ and $f$ restricts to an involution on $\{1,2,...,n-1\}$, or
• $f(n) \ne n$ and $f$ restricts to an involution on $\{1,2,...,n-1\} \setminus \{f(n)\}$.

In the first case, there are $i_{n-1}$ involutions on $\{1,2,...,n-1\}$, each of which induces an involution on $\{1,2,...,n\}$ that fixes $n$.

In the second case, there are $n-1$ possible choices for $f(n)$, and each involution on the remaining $n-2$ elements (of which there are $i_{n-2}$ of them) induces an involution on $\{1,2,...,n\}$ that does not fix $n$.

So, $i_n=i_{n-1}+(n-1)i_{n-2}$.

There is just one involution on the empty set or on any singleton set (namely, the identity map), so $i_0=i_1=1$.