GATE CS 2001 Q2.1 — Combinatorics: Counting, Recurrence Relations, Generating Functions

To find the number of $4$-digit even numbers with all distinct digits, we represent the number as $d_3 d_2 d_1 d_0$, where $d_3 \neq 0$ and $d_0 \in \{0, 2, 4, 6, 8\}$.

Since the thousands digit $d_3$ cannot be $0$, we split the problem into two mutually exclusive cases based on whether the units digit $d_0$ is $0$ or non-zero.

Case 1: The units digit $d_0$ is $0$

• $d_0$: Only $1$ choice ($0$).
• $d_3$: Can be any non-zero digit from $\{1, 2, \dots, 9\}$. Since $0$ is already placed at $d_0$, we have $9$ choices.
• $d_2$: Can be any remaining digit except $d_0$ and $d_3$. This gives $8$ choices.
• $d_1$: Can be any remaining digit except $d_0, d_3,$ and $d_2$. This gives $7$ choices.

$$\text{Total for Case 1} = 9 \times 8 \times 7 \times 1 = 504$$

Case 2: The units digit $d_0$ is one of $\{2, 4, 6, 8\}$

• $d_0$: $4$ choices.
• $d_3$: Cannot be $0$ and cannot be equal to $d_0$. Out of $10$ possible digits, we exclude these $2$, leaving $8$ choices.
• $d_2$: Cannot be equal to $d_0$ or $d_3$ (but can be $0$). This leaves $8$ choices.
• $d_1$: Cannot be equal to $d_0, d_3,$ or $d_2$. This leaves $7$ choices.

$$\text{Total for Case 2} = 8 \times 8 \times 7 \times 4 = 1792$$

Total Even Numbers:

$$\text{Total} = 504 + 1792 = 2296$$

Thus, there are $2296$ such $4$-digit even numbers.