The number of strictly increasing functions f from the set {1, 2, 3, 4, 5, 6} to the set {1, 2, 3,…,9} such that $f(i)\ne i$ for $1\le i\le6,$ is equal to:
- (1) 21
- (2) 27
- (3) 22
- (4) 28
Solution:
We are looking for strictly increasing functions where $f(1) < f(2) < \dots < f(6)$.
The condition $f(i) \neq i$ combined with the increasing nature means every output must be strictly greater than the input.
So, $f(i) > i$ for all $i$.
This implies specifically that $f(1) > 1$.
Since $f(1)$ must be an integer, the smallest value $f(1)$ can take is 2.
We can solve this by splitting it into cases based on the value of $f(1)$.
Case 1: Let $f(1) = 2$
If $f(1) = 2$, then the remaining 5 values $f(2), f(3), f(4), f(5), f(6)$ must be chosen from the numbers strictly greater than 2.
$\therefore$ Available numbers: $\{3, 4, 5, 6, 7, 8, 9\}$.
$\therefore$ Total available = 7 numbers.
$\therefore$ We need to choose 5 numbers from these 7. Once chosen, they can be arranged in only one increasing order.
$\therefore$ Number of ways = $^7C_5 = \frac{7 \times 6}{2} = 21$.
Case 2: Let $f(1) = 3$
If $f(1) = 3$, the remaining 5 values must be chosen from numbers strictly greater than 3.
$\therefore$ Available numbers: $\{4, 5, 6, 7, 8, 9\}$.
$\therefore$ Total available = 6 numbers.
$\therefore$ We need to choose 5 numbers from these 6.
$\therefore$ Number of ways = $^6C_5 = 6$.
Case 3: Let $f(1) = 4$
If $f(1) = 4$, the remaining 5 values must be chosen from numbers strictly greater than 4.
$\therefore$ Available numbers: $\{5, 6, 7, 8, 9\}$.
$\therefore$ Total available = 5 numbers.
$\therefore$ We need to choose 5 numbers from these 5.
$\therefore$ Number of ways = $^5C_5 = 1$.
Case 4: Let $f(1) = 5$
$\therefore$ Available numbers: $\{6, 7, 8, 9\}$ (Only 4 numbers).
$\therefore$ We cannot choose 5 distinct values from 4 numbers, so this case is impossible.
Total number of functions = $21 + 6 + 1 = 28$.
Ans. (4)