How many nondecreasing functions $f: \{1, 2, 3, \ldots, 15\} \to \{1, 2, 3, 4, 5\}$ are there? Consider the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 15$. How many nonnegative integer solutions does it have? How about positive integer solutions? How many nondecreasing functions $f : \{1, 2, 3, \ldots, 15\} \to \{1, 2, 3, 4, 5\}$ are there?

Nonnegative and positive integer solutions I just used combinatorics (bars and stars or pirates and gold) which is not too bad. But for the last question of nondecreasing function i suppose i can rewrite it as $x_1 < x_2 < ... < x_5$. Where do i go from there?
 A: Let $f$ be a non-decreasing function from $\{1,2,3,...,15\} \to \{1,2,3,4,5\}$.

Let $y_1,...,y_{16}$ be defined by
\begin{align*}
y_1 &= f(1) - 1\\[4pt]
y_2 &= f(2) - f(1)\\[4pt]
y_3 &= f(3) - f(2)\\[4pt]
&\;\;\,\vdots\\[4pt]
y_{15}&=f(15)-f(14)\\[4pt]
y_{16}&=5-f(15)\\[4pt]
\end{align*}
Then $y_1,,...,y_{16}$ are nonnegative integers such that
$$y_1 + \cdots + y_{16} = 4$$
Conversely, if $y_1,,...,y_{16}$ are nonnegative integers such that
$$y_1 + \cdots + y_{16} = 4$$
there is a unique non-decreasing function $f\;{:}\,\{1,2,3,...,15\} \to \{1,2,3,4,5\}$, defined by $$f(n) = 1+ (y_1 + \cdots + y_n)$$
Thus, we have a one-to-one correspondence between the set of non-decreasing functions from  $\{1,2,3,...,15\} \to \{1,2,3,4,5\}$ and the set of $16$-tuples $(y_1,...,y_{16})$ of nonnegative integers satisfying the equation
$$y_1 + \cdots + y_{16} = 4$$
Hence, applying the stars-and-bars formula, we get the count
$${\small{\binom{4 + 16 - 1}{16-1}}} = {\small{\binom{19}{15}}} = {\small{\binom{19}{4}}} = 3876$$  
A: A non-decreasing function from $\{1, 2, 3, \ldots, 15\} \to \{1, 2, 3, 4, 5\}$ is completely determined by how many numbers in the domain are assigned to each element in the codomain.  For instance, $(15, 0, 0, 0, 0)$ corresponds to the constant function $f(k) = 1$ for $1 \leq k \leq 15$, while $(3, 4, 5, 2, 1)$ corresponds to the function 
\begin{align*}
f(1) & = f(2) = f(3) = 1\\ 
f(4) & = f(5) = f(6) = f(7) = 2\\ 
f(8) & = f(9) = f(10) = f(11) = f(12) = 3\\ 
f(13) & = f(14) = 4\\ 
f(15) & = 5
\end{align*}
Let $x_k$ be the number of elements in the domain that are assigned to $k$ in the codomain.  Then the number of decreasing functions is the number of solutions of the equation
$$x_1 + x_2 + x_3 + x_4 + x_5 = 15 \tag{1}$$
in the nonnegative integers.  A particular solution of equation corresponds to the placement of four addition signs in a row of $15$ ones.  For instance, 
$$1 1 1 1 + 1 1 1 1 1 1 + + 1 1 1 + 1 1$$
corresponds to the solution $x_1 = 4$, $x_2 = 6$, $x_3 = 0$, $x_4 = 3$, $x_5 = 2$.  There are 
$$\binom{15 + 4}{4} = \binom{19}{4}$$
such solutions since we must choose which $4$ of the $19$ positions required for $15$ ones and $4$ addition signs will be filled with addition signs.
A: Any such function can be encoded as a word containing the numbers from $1$ to $15$ in order and four separating bars, e.g. $(1,|,2,3,|,4,5,6,7,8,9,10,11,|,12,13,14,15,|)$. There are ${19\choose 4}=3876$ such words.
