Show that there are exactly n strictly increasing functions from {1, 2, . . . , n − 1} to {1, 2, . . . , n}.

Steps to Solve

1. Understanding Strictly Increasing Functions

A strictly increasing function $f$ from a set $A$ to a set $B$ means that for any two elements $x$ and $y$ in $A$, if $x < y$, then $f(x) < f(y)$. In our problem, $A = {1, 2, ..., n-1}$ and $B = {1, 2, ..., n}$.

2. Representing a strictly increasing function

Since the function must be strictly increasing and maps $n-1$ elements to a set of $n$ elements, we can represent a strictly increasing function $f$ by specifying the values $f(1), f(2), ..., f(n-1)$. Because $f$ is strictly increasing, we must have $1 \le f(1) < f(2) < ... < f(n-1) \le n$.

3. Finding possible values for the function

We need to choose $n-1$ distinct values from the set ${1, 2, ..., n}$ and arrange them in increasing order. Because we are always arranging them in increasing order, we can determine the function simply by choosing the $n-1$ values which will become $f(1), f(2), ..., f(n-1)$.

4. Using combinations

The number of ways to choose $n-1$ elements from a set of $n$ elements is given by the binomial coefficient $\binom{n}{n-1}$, which represents combinations.

5. Calculating the binomial coefficient

The binomial coefficient $\binom{n}{n-1}$ can be calculated as:

$$ \binom{n}{n-1} = \frac{n!}{(n-1)!(n - (n-1))!} = \frac{n!}{(n-1)!1!} = \frac{n \times (n-1)!}{(n-1)!} = n $$

Therefore, there are exactly $n$ such strictly increasing functions.