Permutation or Combinatorics

Question

A sequence of integers (a1,a2,...,an) is weakly increasing if a1 ≤ a2 ≤ ··· ≤ an. For instance, (0, 2, 2, 3, 5, 5, 7, 8, 9, 10) is weakly increasing, but (0, 2, 2, 3, 5, 6, 7, 9, 4, 10) is not. Determine the number of weakly increasing sequences of length 20 where 0 ≤ ai ≤ 10 for every 1 ≤ i ≤ 20.

Im not sure if I should approach the question as a permutation or combinatorics. Also confused on how to solve it to make sure it is in ascending order.

Thank you for your help

Answer 1

The answer is the binomial coefficient 30 choose 10, that is, 30!/(20! 10!).

To see this, observe that there is a bijection between the sought-after weakly-increasing sequences and permutations of 10 stars and 20 bars. Indeed, starting with a permutation, we get a sequence as follows:

-- Let a_1 be the number of stars before the first bar. This number may be zero.

-- Let a_2 be the total number of stars before the second bar. This includes those start before the first bar, so a_2 >= a_1.

-- And so on ...

Since there are 20 bars, we account for all the a_i. Since there are 10 stars, each a_i is at most 10.

Conversely, any weakly increasing sequence can be represented as a permutation of 10 stars and bars, by starting with a_1 stars, then a bar, then a_2 - a_1 stars, then a bar, then a_3 - a_2 stars, etc.

Finally, we know that there are 30 choose 10 permutations of 10 stars and 20 bars, so that's our final answer!

_________

Link to more information about stars and bars arguments: https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)