Question

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)>i\) for \(1 \le i \le 6\), is equal to:}

• A. 22
• B. 27
• C. 21
• D. 28

Hint:

Problems involving counting ordered sequences (like strictly increasing functions) can often be transformed into simpler unordered selection problems (combinations with or without repetition).
The transformation \(c_i = f(i) - i\) is very effective for converting a strict inequality \(f(i)<f(i+1)\) into a non-strict one \(c_i \le c_{i+1}\), which is the standard setup for "stars and bars".

Answer 1

The Correct Option is D

Step 1: Understanding the Question:
We need to find the number of functions \(f\) with a domain \(A = \{1, 2, 3, 4, 5, 6\}\) and codomain \(B = \{1, 2, ..., 9\}\). The function must satisfy two conditions:
1. Strictly increasing: \(f(1)<f(2)<f(3)<f(4)<f(5)<f(6)\).
2. Additional condition: \(f(i)>i\) for all \(i \in A\).
Step 2: Key Formula or Approach:
A strictly increasing function is uniquely determined by its range. If we select 6 distinct elements from the codomain, there is only one way to assign them to \(f(1), ..., f(6)\) to satisfy the strictly increasing condition. So, the problem reduces to counting the number of ways to choose 6 distinct numbers from the codomain that satisfy the second condition. We can use a variable transformation to simplify the counting process, which often leads to a standard stars and bars (combination with repetition) problem.
Step 3: Detailed Explanation:
Let \(y_i = f(i)\). The conditions are: 1. \(y_1<y_2<y_3<y_4<y_5<y_6\) with \(y_i \in \{1, ..., 9\}\). 2. \(y_i>i\) for \(i=1, 2, ..., 6\). This means \(y_i \ge i+1\).
Let's apply a transformation to simplify these conditions. Let \(c_i = y_i - i\). From condition 2 (\(y_i>i\)), we get \(y_i - i>0\), so \(c_i \ge 1\). All \(c_i\) are integers. From condition 1 (\(y_i<y_{i+1}\)), we can analyze the relationship between \(c_i\) and \(c_{i+1}\). \(y_i<y_{i+1} \implies c_i + i<c_{i+1} + (i+1) \implies c_i - 1<c_{i+1}\). Since \(c_i\) and \(c_{i+1}\) are integers, this is equivalent to \(c_i \le c_{i+1}\). So, the original problem is equivalent to finding the number of integer sequences \(c_1, c_2, c_3, c_4, c_5, c_6\) such that: \[ 1 \le c_1 \le c_2 \le c_3 \le c_4 \le c_5 \le c_6 \] We also have an upper bound from the codomain: \(y_6 \le 9\). \[ c_6 + 6 \le 9 \implies c_6 \le 3 \] Combining these, we need to find the number of non-decreasing sequences of length 6 using numbers from the set \{1, 2, 3\}. \[ 1 \le c_1 \le c_2 \le c_3 \le c_4 \le c_5 \le c_6 \le 3 \] This is a problem of choosing 6 items from a set of 3 items (\{1, 2, 3\}) with repetition allowed. This is a classic stars and bars problem. The number of ways is given by the formula \(\binom{n+k-1}{k}\), where \(n\) is the number of items to choose from (n=3) and \(k\) is the number of items to be chosen (k=6). Number of ways = \(\binom{3+6-1}{6} = \binom{8}{6}\). \[ \binom{8}{6} = \binom{8}{8-6} = \binom{8}{2} = \frac{8 \times 7}{2 \times 1} = 28 \] Step 4: Final Answer:
The number of such strictly increasing functions is 28.