How many 4-digit integers between 1000 and 9999 have their digits in non-decreasing order, such as 3447? Click here for solutions.
Solution 1 – Brute Force Denote $f(m, n)$ as the number of $m$-digit
integers with their digits in non-decreasing order and the first digit value as $n$, where $0\le n\le 9$.
We have the following relation: $$ \begin{array}{rcl}
f(1,\ n)&=&1 \\
f(m,9)&=&1 \\
f(m, n)&=&f(m-1, 9) + … + f(m-1, n+1) + f(m-1, n)\\
&=&f(m, n+1) + f(m-1, n)
\end{array} $$
Then we have the following table $$ \begin{array}{c|rrrrrrrrrr}
f(m,n)& & & & & n & & & & & \\ \hline
m & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 \\ \hline
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
2 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
3 & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45 & 55 \\
4 & 1 & 4 & 10 & 20 & 35 & 56 & 84 & 120 & 165 & 220 \\
5 & 1 & 5 & 15 & 35 & 70 & 126 & 210 & 330 & 495 & 715 \\
\hline
\end{array} $$
The answer to the question is equivalent to $f(5, 1)=495$, i.e. number of 5-digit integers with their digits in non-decreasing order and the first digit as $1$.
Note Do you notice the Pascal’s triangle in the above table?
Solution 2 – Use Stars and Bars Theorem This problem can be translated into inserting 4 identical balls in the boxes after 9 ordered digits as the following, where the number of balls in a box indicates the number of consecutive occurrences of the proceeding digit in forming a 4-digit number: $$\fbox{1}\Box{ }\fbox{2}\Box\fbox{3}\Box{ }\fbox{4}\Box{ }\fbox{5}\Box{ }\fbox{6}\Box{ }\fbox{7}\Box{ }\fbox{8}\Box{ }\fbox{9}\Box{ }$$ For example, 3447 will have 1 ball in the box after 3, 2 balls in the box after 4, and 1 ball in the box after 7 in the above figure. Therefore, using the formula, the answer to the question is $$ {n+k-1\choose n} = {4+9-1 \choose 4} = {12 \choose 4} = \dfrac{12\times 11\times 10\times 9}{4\times 3\times 2\times 1} = 495$$