Question

If \( A = \{1,2,3,4,5,6\} \) and \( B = \{1,2,3,\ldots,9\} \), then the number of strictly increasing functions \( f : A \to B \) such that \( f(i) \neq i \) for all \( i = 1,2,3,4,5,6 \) is:

Hint:

For counting strictly increasing functions:
They correspond to combinations of codomain elements
Restrictions like \( f(i) \neq i \) are handled using inclusion–exclusion
Always start with the unrestricted count

Answer 1

Correct Answer: 28

To find the number of strictly increasing functions \( f: A \to B \) such that \( f(i) \neq i \) for all \( i = 1,2,3,4,5,6 \), we need to choose 6 distinct elements from set \( B \) of 9 elements to map the 6 elements of set \( A \). The function must be strictly increasing; therefore, once the elements from \( B \) are chosen, they are automatically assigned in increasing order to \( A \).
First, we calculate the total number of ways to choose 6 elements from 9: \[ \binom{9}{6} = \binom{9}{3} = 84. \]
Next, implement the condition \( f(i) \neq i \) for all \( i \). No direct positions can match. Thus, we use an inclusion-exclusion principle:

• Let \( S_i \) be the set of functions where \( f(i) = i \).
• Total elements in each \( S_i \) is \( \binom{8}{5} \) since now choosing 5 elements from remaining 8 elements of \( B \), giving \(\binom{8}{5} = 56 \).
• To manage overlaps for when two elements match, apply: \(\binom{7}{4} = 35\).
• Include-exclusion for 3 matches gives: \(\binom{6}{3} = 20\).
• With 4 or more, there are no possible combinations for strict increasing functions, as 6 cannot exceed chosen 9.

Applying inclusion-exclusion:
\[ 84 - \binom{6}{1}\cdot56 + \binom{6}{2}\cdot35 - \binom{6}{3}\cdot20 = 84 - 336 + 210 - 120 = 28. \]
After satisfying all conditions, the number of strictly increasing functions \( f: A \to B \) with \( f(i) \neq i \) is 28.
The computed solution, 28, falls within the given range of 28 to 28, confirming it is correct.