How many nondecreasing functions $f: \{1, 2, 3, \ldots, 15\} \to \{1, 2, 3, 4, 5\}$ are there?

Question

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?

Answer 1

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.

Answer 2

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$$

Answer 3

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.