GATE 2026 DA Q.33: solution and answer

Official answer: 10Source: Official answer key, GATE 2026 DA (IIT Guwahati)

1. The condition $f(f(n))=n$ for every $n\in S$ says $f\circ f=\text{id}$, so $f$ is its own inverse. A bijection with this property is an involution, and every cycle of its cycle decomposition has length 1 (a fixed point) or length 2 (a swapped pair).

2. Count by the number $k$ of swapped pairs. The elements not in any pair are fixed points.

3. $k=0$: every element is fixed, so $f$ is the identity. This gives $1$ bijection.

4. $k=1$: choose the two elements that swap in $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ ways. The other two are fixed. This gives $6$ bijections.

5. $k=2$: split the 4 elements into two unordered pairs. Choose the partner of element $1$ in $3$ ways; the remaining two elements form the other pair. This equals $\frac{1}{2}\left(\genfrac{}{}{0ex}{}{4}{2}\right)=3$, so there are $3$ bijections.

6. A 3-cycle or a 4-cycle is excluded, because applying $f$ twice would not return every element to itself. Each of those has order 3 or 4 rather than dividing 2.

7. Total: $1+6+3=10$.

8. Check with the involution recurrence $a_n=a_{n-1}+(n-1)a_{n-2}$. Element $n$ is either fixed ($a_{n-1}$ ways) or paired with one of the other $n-1$ elements ($(n-1)a_{n-2}$ ways). With $a_1=1$ and $a_2=2$ this gives $a_3=2+2\cdot 1=4$ and $a_4=4+3\cdot 2=10$.