Count number of increasing functions, nondecreasing functions $f: \{1, 2, 3, \ldots, n\} \to \{1, 2, 3, \ldots, m\}$, with $m \geq n$.

How many strictly increasing functions $f:\{1, 2, 3, \ldots, n\} \to \{1, 2, 3, \ldots, m\}$ are there?

A function $$f: \{1, 2, 3, \ldots, n\} \to \{1, 2, 3, \ldots, m\}$$ is determined by how the values $$f(1), f(2), f(3), \ldots, f(n)$$ are assigned. Since $f$ is a strictly increasing function, $$f(1) < f(2) < f(3) < \ldots < f(n)$$ Thus, for a strictly increasing function, each value in the domain is mapped to a distinct element in the codomain. Since there are $n$ elements in the domain and $m$ elements in the codomain, the number of ways we can select the elements in the range is $\binom{m}{n}$. Once we have selected these elements, there is only one way to assign them so that the function is strictly increasing, namely by assigning the smallest element in the range to be $f(1)$, the next smallest to be $f(2)$, and so forth. Hence, the number of strictly increasing functions is $$\binom{m}{n}$$

How many nondecreasing functions $f: \{1, 2, 3, \ldots, n\} \to \{1, 2, 3, \ldots, m\}$ are there?

Since $f$ is a nondecreasing function, the function is completely determined by how many values of $j \in \{1, 2, 3, \ldots, n\}$ are assigned to equal $k \in \{1, 2, 3, \ldots, m\}$. To see why, consider functions $$f: \{1, 2, 3, 4, 5\} \to \{1, 2, 3, 4, 5, 6, 7\}$$ If two values are assigned to equal $3$, one value is assigned to equal $4$, and two values are assigned to equal $7$, then since $f$ is nondecreasing, $f$ must be the function defined by $f(1) = f(2) = 3$, $f(3) = 4$, $f(4) = f(5) = 7$.

Let $x_k$, $1 \leq k \leq m$, be the number of values of $j \in \{1, 2, 3, \ldots, n\}$ such that $f(j) = k$. Then $$x_1 + x_2 + x_3 + \ldots + x_m = n$$ which is an equation in the nonnegative integers. A particular solution corresponds to the placement of $m - 1$ addition signs in a row of $n$ ones.

To make this concrete, consider nondecreasing functions $$f: \{1, 2, 3, 4, 5\} \to \{1, 2, 3, 4, 5, 6, 7\}$$ Then we have $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 = 5$$ The assignment $$+ + 1 1 + 1 + + + 1 1$$ corresponds to the above example that $x_1 = x_2 = 0$, $x_3 = 2$, $x_4 = 1$, $x_5 = x_6 = 0$, and $x_7 = 2$, that is, the function defined by $f(1) = f(2) = 3$, $f(3) = 4$, $f(4) = f(5) = 7$. In this case, the number of such functions is the number of ways we can insert six addition signs in a row of five ones, which is $$\binom{5 + 6}{6} = \binom{11}{6}$$ since we must choose which six of the eleven symbols (five ones and six addition signs) will be addition signs.

By similar reasoning, the number of nondecreasing functions $$f: \{1, 2, 3, \ldots, n\} \to \{1, 2, 3, \ldots, m\}$$ is equal to the number of ways we can insert $m - 1$ addition signs in a row of $n$ ones, which is $$\binom{n + m - 1}{m - 1}$$ since we must select which $m - 1$ of the $n + m - 1$ symbols ($n$ ones and $m - 1$ addition signs) must be addition signs.