Prove that the number of increasing words of length $n$ formed by an alphabet of $m$ letters is $$\binom{m+n-1}{n}$$
(A word is increasing if its letters(except repetitions) appear in alphabetic order)
$e.g.: abbbbccdeeef$ is an increasing word of length 12
I would really appreciate your help; I don't know how to solve this 🙁
Best Answer
It's all about finding the right bijection into a set you can count.
Starting with an alphabetical string, form an auxiliary string as follows. Between consecutive blocks, place a barrier symbol $|$. Replace each letter by a $_$. For instance, you string $abbbbccdeeef$ becomes $$ _|____|__|_|___|_ $$ Do you see why there is a bijection between these auxiliary strings and the alphabetized ones we started with?
Now we count the auxiliary strings. In total, there are $m-1$ barriers and $n$ spaces $_$. Hence we've written down $n+m-1$ symbols. Now we choose the locations for the $m-1$ barriers. Hence there are $$ {n+m-1 \choose m-1} $$ possible auxiliary strings. Now since $n=(n+m-1)-(m-1)$, it follows that $$ {n+m-1 \choose m-1}={n+m-1 \choose n} $$ which is the answer we desired.