Let $r, l$ be two integers such that $r \ge l \ge 3$. What is the total number of functions
\[ f : \{1, 2, \dots, r\} \to \{1, 2, \dots, r\} \]
such that $f(1), f(2), \dots, f(l)$ are all distinct?
Show Hint
For counting problems with mixed constraints, handle the restricted choices first.
Here, mapping the first $l$ elements is equivalent to selecting an ordered arrangement of $l$ elements out of $r$, which is $P(r,l) = \frac{r!}{(r-l)!}$.
Then multiply by $r^{r-l}$ for the remaining unrestricted elements.
Step 1: Understanding the Question:
We are asked to find the total number of functions from a set containing $r$ elements to itself.
The condition imposed is that the images of the first $l$ elements of the domain, i.e., $\{f(1), f(2), \dots, f(l)\}$, must be distinct.
The remaining $r - l$ elements in the domain have no restrictions on their mapping. Step 2: Key Formula or Approach:
We will use the fundamental counting principle.
First, we calculate the number of ways to map the first $l$ elements such that they have distinct images.
Next, we calculate the number of ways to map the remaining $r - l$ elements of the domain, which can be mapped to any of the $r$ elements of the codomain.
The total number of functions is the product of these two values. Step 3: Detailed Explanation:
• Let the domain and codomain be $S = \{1, 2, \dots, r\}$.
• We need to map the subset $\{1, 2, \dots, l\}$ to distinct values in $S$.
• For the first element, $1$, there are $r$ possible choices in the codomain.
• For the second element, $2$, there are $r - 1$ choices (since $f(2) \neq f(1)$).
• For the third element, $3$, there are $r - 2$ choices (since $f(3) \neq f(1)$ and $f(3) \neq f(2)$).
• Continuing this, for the $l$-th element, there are $r - (l - 1) = r - l + 1$ choices.
• Thus, the number of ways to assign distinct values to $f(1), f(2), \dots, f(l)$ is:
\[ P(r, l) = r(r - 1)(r - 2)\dots(r - l + 1) \]
• Now, we consider the remaining $r - l$ elements in the domain, which are $\{l+1, l+2, \dots, r\}$.
• Since there are no restrictions on these remaining elements, each can be mapped to any of the $r$ elements in the codomain.
• The number of ways to map these $r - l$ elements is:
\[ r \times r \times \dots \times r = r^{r - l} \]
• Therefore, the total number of functions is:
\[ \text{Total Functions} = r(r - 1)(r - 2)\dots(r - l + 1) \times r^{r - l} \]
We can rewrite this expression by combining the factor of $r$ with $r^{r-l}$:
\[ \text{Total Functions} = r^{r - l + 1}(r - 1)(r - 2)\dots(r - l + 1) \]
Step 4: Final Answer:
The total number of such functions is $r^{r-l+1}(r-1)(r-2)\dots(r-l+1)$.
