Solving a Combinatorial Problem Using Bijection

Question: For $n=1, 2, \ldots,$ let $a(n)$ be the number of $n$-digit positive integers $d_1d_2\cdots d_n$, where $d_1\le d_2\le \cdots \le d_n$. What is $a(n)$?

The answer is $$ a(n) = {n+ 8 \choose n}={n+8 \choose 8}. $$

To fully understand how to derive the above formula, let us look at a special case, where $n=2$ and we restrict that the digits can only come from the set ${1,\ 2,\ 3}$. For this special case, we can write down all the candidate 2-digit numbers, and they are $$ 11,\ 12,\ 13,\ 22,\ 23,\ \hbox{and}\ 33 $$ Now, for the special case, we can translate the original question as: If we put 2 markers into the 3 boxes, count all the possibilities.

Since we know the six 2-digit numbers as shown above, we can establish the following bijection

The bijection tells us that the count of all possibilities is the same as all the arrangements of 2 indistinguishable markers (shown as M in the above picture) and 2 indistinguishable boundaries (they are for the 3 boxes). So the answer to the special case is $$ \frac{(2+2)!}{2!2!}={4 \choose 2}=6. $$

Following the ideas used for dealing with the special case, we can now figure out that $a(n)$ counts all the different arrangements of $n$ indistinguishable markers and 8 indistinguishable boundaries (they are for 9 boxes). Thus, the answer to the original question is $$ \frac{(n+8)!}{n!8!}={n+8 \choose n}={n+8 \choose 8}. $$

Remarks:

1. I learned the bijection idea from [1].
2. This post is motivated by Alon Amit’s post on Quora.
3. This post actually is about OEIS sequence A000581. I have found that the sequence A000581 has a connection with OEIS sequence A035927. The connection is: $$ \hbox{A000581}(n+8)=\hbox{A035927}(n)-\hbox{A035927}(n-1), $$ where $\hbox{A035927}(-1):=-1$ and $n=0, \ 1, 2,\ \ldots.$

References

[1] Casella, G. and Berger, R. (2002). Statistical Inference.