Solving a Combinatorial Problem Using Bijection

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

The answer is $$a(n)=(\genfrac{}{}{0ex}{}{n+8}{n})=(\genfrac{}{}{0ex}{}{n+8}{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,\text{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!}=(\genfrac{}{}{0ex}{}{4}{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!}=(\genfrac{}{}{0ex}{}{n+8}{n})=(\genfrac{}{}{0ex}{}{n+8}{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: $$\text{A000581}(n+8)=\text{A035927}(n)-\text{A035927}(n-1),$$ where $\text{A035927}(-1):=-1$ and $n=0,1,2,\dots .$

References

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