Question

Let \(\mathbb{N}\) denote the set of all positive integers. Consider the sets \[ A = \{1,2,3,4,5\} \] and \[ B = \{1,2,3,4,5,6,7\}. \] Let \(S\) be the set of all functions \[ f : A \to B \] such that \[ f(2) \ne 2 \quad \text{and} \quad f(4) \ne 4. \] Consider the set \[ T = \left\{ f \in S : \text{there exists a function } g : B \to \mathbb{N} \text{ such that } g(f(x)) = 2^x \text{ for all } x \in A \right\}. \] Then the number of elements in the set \(T\) is:

Hint:

Whenever a problem defines a composite function $g(f(x)) = h(x)$ where $h(x)$ is injective, $f(x)$ must also be injective. This simplifies function-counting problems into permutation problems ($^nP_r$).

Answer 1

Correct Answer: 1860

Step 1: Understanding the Question:
We are looking for the number of specific functions $f: A \to B$. The condition $g(f(x)) = 2^x$ implies that $f$ must be an injective function. If $f(x_1) = f(x_2)$, then $g(f(x_1)) = g(f(x_2)) \implies 2^{x_1} = 2^{x_2} \implies x_1 = x_2$. Additionally, we have the constraints $f(2) \neq 2$ and $f(4) \neq 4$.

Step 2: Key Formula or Approach:

• Total number of injective functions $f: A \to B$ is $P(n(B), n(A)) = P(7, 5)$.

• Apply the Principle of Inclusion-Exclusion (PIE) to handle the conditions $f(2) \neq 2$ and $f(4) \neq 4$.

Step 3: Detailed Explanation:

• Let $U$ be the set of all injective functions from $A$ to $B$.
$|U| = P(7, 5) = 7 \times 6 \times 5 \times 4 \times 3 = 2520$.

• Let $P_1$ be the set of injective functions such that $f(2) = 2$.
In this case, 2 is fixed. We need to choose images for the remaining 4 elements of $A$ from the remaining 6 elements of $B$.
$|P_1| = P(6, 4) = 6 \times 5 \times 4 \times 3 = 360$.

• Let $P_2$ be the set of injective functions such that $f(4) = 4$.
Similarly, $|P_2| = P(6, 4) = 360$.

• Let $P_1 \cap P_2$ be the set of injective functions such that $f(2) = 2$ and $f(4) = 4$.
Now 2 elements are fixed. We choose images for the remaining 3 elements of $A$ from the remaining 5 elements of $B$.
$|P_1 \cap P_2| = P(5, 3) = 5 \times 4 \times 3 = 60$.

• The number of functions in set $T$ (where $f(2) \neq 2$ and $f(4) \neq 4$) is given by:
$|T| = |U| - (|P_1| + |P_2| - |P_1 \cap P_2|)$.
$|T| = 2520 - (360 + 360 - 60) = 2520 - 660 = 1860$.

Step 4: Final Answer:
The number of elements in the set $T$ is 1860.