# How many four digit numbers in which each digit is at least as large as the previous digit?

Given that the first digit has to be between 1 and 9, each subsequent digit depends on the previous. If they were strictly increasing, then it would be $$\binom{9}{4}$$ numbers. My idea is that for each digit after the first, there is an additional choice compared to the strictly increasing numbers, but I'm not sure how to translate that into an expression. Any help is appreciated!

You can associate any such four digit number to one and only one vector in $$\{0,1,2,\ldots\}^9$$ whose entries sum to $$4$$ by counting the number of times a certain digit appears. For example, $$3389\cong (0,0,2,0,0,0,0,1,1)$$ $$4499\cong(0,0,0,2,0,0,0,0,2)$$ $$1119\cong(3,0,0,0,0,0,0,0,1)$$ Using stars and bars, we see the number of such vectors is $${12 \choose 8}=495.$$

• That's downright elegant. ($+1$) Feb 21, 2021 at 3:39
• @Robert Shore thank you very much! As someone who has always struggled with combos, your comment feels very rewarding :-D Feb 21, 2021 at 16:41

Hint:

If $$1\leq a_1 then $$1\leq a_1\leq a_2-1\leq a_3-2\leq a_4-3\leq 9,$$ and visa versa.

• Should it be $a_2 - 1 \leq a_3 -2$ in the middle? Feb 21, 2021 at 2:33
• @ccroth. Yes, fixed. Feb 21, 2021 at 2:34

$$\sum\limits_{a_1 = 1}^9 \sum\limits_{a_2 = a_1}^9 \sum\limits_{a_3 = a_2}^9 \sum\limits_{a_4 = a_3}^9 1 = 495$$
• Okay, but then try it for $100$ digit numbers. :) Feb 21, 2021 at 2:42