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 solve the problem, we need to determine the number of strictly increasing functions \( f: A \to B \), where \( A = \{ 1, 2, 3, 4, 5, 6 \} \) and \( B = \{ 1, 2, 3, \ldots, 9 \} \), with the condition \( f(i) \neq i \) for all \( i \in A \). 

First, find the number of strictly increasing functions \( f: A \to B \) without any conditions. For a strictly increasing function from a set with \( n \) elements (here \( A \) has 6 elements) to a set with \( m \) elements (here \( B \) has 9 elements), we select 6 distinct elements from \( B \). The number of ways to choose 6 elements from 9 is given by the combination formula \( \binom{m}{n} \):

\[ \binom{9}{6} = \binom{9}{3} = 84 \]

Next, we apply the condition \( f(i) \neq i \). For each \( i \), \( f(i) = i \) is not allowed, so we find the number of ways where at least one \(f(i)\) equals \(i\) and subtract this from 84.

For a specific \( i \), say \( f(1) = 1 \), the remaining set \( A' = \{ 2, 3, 4, 5, 6 \} \) must be mapped into \( B' = \{ 2, 3, 4, 5, 6, 7, 8, 9 \} \). The number of such strictly increasing functions is:

\[ \binom{8}{5} = 56 \]

By the Inclusion-Exclusion Principle, subtract cases where exactly one of the conditions \( f(i) = i \) is violated for any \( i \):

\[ 6 \times 56 = 336 \]

For cases where exactly two distinct \( f(i) \) equal \( i \), say \( f(1) = 1 \) and \( f(2) = 2 \): This leaves \( A'' = \{ 3, 4, 5, 6 \} \) and \( B'' = \{ 3, 4, 5, 6, 7, 8, 9 \} \):

\[ \binom{7}{4} = 35 \]

The number of ways for any two such conditions being violated:

\[ \binom{6}{2} \times 35 = 15 \times 35 = 210 \]

Finally, for three equalities \( f(i) = i \), say \( f(1) = 1, f(2) = 2, f(3) = 3 \), reduces to a trivial and impossible selection.

Now, apply Inclusion-Exclusion:

\[ 84 - 336 + 210 = -42 + 210 = 28 \]

The number of functions that satisfies the conditions is 28, which fits the specified range (28, 28).