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}$$
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}$$
No comments:
Post a Comment