How many non-decreasing functions [Solutions]

The problem was to find the number of ordered pairs $x = (x_1, x_2, \dots, x_n)$ such that $x_i \le x_{i+1}$ and $1 \le x_i \le m$ for all $i$, $x_i$ being a natural number.

Solution

---

We will present two solutions.

Solution 1)

The first solution uses what is called the Stars and Bars approach.

For each $k \in \{1, 2, \dots, m\}$ you look at exactly how many $x_i = k$. Call this number $y_k$ (note, it could be $0$).

We must have that $y_1 + y_2 + \dots + y_m = n$, with $0 \le y_i \le n$.

Now given a $y = (y_1, y_2, \dots, y_m)$ we can easily map this back to the $x = (x_1, x_2, \dots, x_n)$ from which it was created.

Thus it is enough to count the number of solutions to $y_1 + y_2 + \dots + y_m = n$, with $0 \le y_i \le n$.

The way to look at this is to consider $n$ stars, and $m-1$ vertical bars. Finding a solution to the above equation is equivalent to placing the $m-1$ bars among the $n$ stars. The number of stars to the left of the leftmost bar is $y_1$, the one next to it is $y_2$ and so on.

The number of ways to do this is to select the position of the stars among a total $n + m - 1$ spots: $$\binom{n+m-1}{n}$$

Solution 2)

The second solution I find particularly elegant.

Suppose instead of $x_i \le x_{i+1}$, we had the condition $x_i \le x_{i+1}$ (i.e. strictly increasing).

Then it is easy to count: just select $n$ among $m$ = $\binom{m}{n}$ (and sort to get the increasing order).

We can reduce our problem to the strictly increasing case.

Set $z_i = x_i + i - 1$.

Now we have that $z_i \lt z_{i+1}$ (strictly increasing) and that $1 \le z_i \le m + n - 1$.

Thus the answer is $$\binom{m+n-1}{n}$$