2
$\begingroup$

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!

$\endgroup$
0

3 Answers 3

7
$\begingroup$

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.$

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

Hint:

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

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

Think about this figure (for the 3-digit case):

enter image description here

$$\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$$

$\endgroup$
1
  • $\begingroup$ Okay, but then try it for $100$ digit numbers. :) $\endgroup$ Feb 21, 2021 at 2:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .