Question

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?

• A. $r^{r-l+1}(r - 1)(r - 2)\dots(r - l + 1)$
• B. $r^{r-l}(r - 1)(r - 2)\dots(r - l + 1)$
• C. $r(r - 1)(r - 2)\dots(r - l + 1)$
• D. $r^r$

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.

Answer 1

The Correct Option is A

Step 1: Understanding the Concept:
We are counting functions with a specific constraint on a subset of the domain.
Key Formula or Approach:
Multiplication Principle: Total ways = (Ways for restricted elements) $\times$ (Ways for unrestricted elements).

Step 2: Detailed Explanation:
$\bullet$ Restricted Elements ($1, 2, \dots, l$): These must map to distinct values in the codomain of size $r$.
Ways to pick and arrange $l$ distinct images = $r \times (r-1) \times (r-2) \times \dots \times (r-l+1)$.
This is equal to ${}^{r}P_{l}$.
$\bullet$ Unrestricted Elements ($l+1, l+2, \dots, r$): There are $r - l$ such elements.
Each of these can map to any of the $r$ values in the codomain.
Ways = $r \times r \times \dots \times r$ ($r-l$ times) = $r^{r-l}$.
$\bullet$ Total Functions:
Total = $[r(r-1)(r-2)\dots(r-l+1)] \times r^{r-l}$.
Rearranging to match the options (bringing one $r$ inside the $r^{r-l}$ term):
Total = $r^{r-l+1} \times (r-1)(r-2)\dots(r-l+1)$.

Step 3: Final Answer:
The count is $r^{r-l+1}(r-1)(r-2)\dots(r-l+1)$.
This matches option (A).