# How many $5$-digit numbers are there with digits $abcde$ such that $a < b < c \leq d \leq e$?

How many $$5$$-digit numbers are there with digits $$abcde$$ such that $$a < b < c \leq d \leq e$$?

I know that if all of them were distinct, then the answer will be $$C(9,5)$$. However, there are some "less than or equal to" notations, so I do not know how to approach it. I need help. Thanks in advance.

• If all of them were distinct, the answer would just be $\binom 95$. Aug 18, 2021 at 18:32
• @MishaLavrov little mistake , thanks Aug 18, 2021 at 18:33
• Does $a$ have to be nonzero? Aug 18, 2021 at 18:34
• @JukkaKohonen yeap , to be 5 digit , it has to be nonzero Aug 18, 2021 at 18:34
• The question doesn't make sense to me. How many numbers are there such that $abcde$ what? Aug 18, 2021 at 18:41

Hint: If you replace $$d$$ by $$d+1$$, and $$e$$ by $$e+2$$ in your number, then you are looking for all distinct digits, and now the digits are at most 11 (instead of at most 9).

• Great hint (I upvoted) . I think you meant to say that the digits are at most 11 (instead of at most 9)
– WW1
Aug 18, 2021 at 19:20
• Oops, of course (originally between 1 and 9, now between 1 and 11). Thanks, will correct! Aug 18, 2021 at 19:41
• @Jukka Kohonen: (1) I don't see how $11$ can be considered as a digit. (2) Only part of the abcde is strictly increasing Aug 18, 2021 at 21:39
• true blue anil: (1) I don't see the problem. You can call them hexadecimal digits if you will, or just integers. It does not matter. Once you have such five integers $a < b < c < d' < e'$, with $e' \le 11$, you can turn them back to a solution of the original problem with $d=d'-1$ and $e=e'-2$. (2) That's exactly why the transformation was applied only to $d$ and $e$. Aug 19, 2021 at 0:15
• Nice shortcut (+1). Aug 19, 2021 at 6:48

The first thing to note is that if we select k distinct digits from n digits, the digits can be arranged in a strictly ascending order in only one way

We can break up the number string into two parts

(a): $$a,b,c:\;$$ The ending digit($$c$$) can range from $$3-9$$ and it can be seen that if the ending digit $$c$$ is $$n$$, say, from the lower digits, there can be $$\binom{n-1}2$$ selections in strictly ascending order

(b): Suppose c was $$3$$, then we have $$10-3=7$$ digits for the remaining slot $$e$$ . These slots can either have distinct digits $$\binom72$$, or identical digits, $$7$$

Combining the two parts, the formula comes out to

$$\sum_{n=3}^{10}\binom{n-1}2\left[\binom{10-n}2+(10-n)\right] = 462$$

• Not quite. For example, suppose that the third digit is $c=8$. Then your summation is counting $(10-8)^2 = 4$ ways for the final two digits $(d,e)$, but if you simply list the possibilities, you can see that there are only three: 88, 89 and 99. A similar error is in the other terms (that is, when $c<8$) so the sum is overcounting the cases. Aug 19, 2021 at 0:10
• Corrected 3am error after 10am coffee ! Aug 19, 2021 at 4:33
• (+1) I also confirmed the numeric value by brute force. Aug 19, 2021 at 6:28
• Yes, now it works! (Coffee helps, ask Erdős.) Aug 19, 2021 at 6:51
• @trueblueanil hmmm nice +1 , by the way for part $b$ you can use combinantion with repetition instead of wrting seperately such that distinct digits + identical digits Aug 19, 2021 at 6:51

To find all digits such that $$0,

• find all subsets $$\{a,b,c,d,e\}$$ from $$\{1,\ldots,9\}\$$ (w.l.o.g $$a) to get all 5 digit numbers, there are $$\binom 9 5$$ such numbers
• find all subsets $$\{a,b,c,e\}$$ from $$\{1,\ldots,9\}\$$ (w.l.o.g $$a), set $$d:=c$$ to get all 5 digit numbers such that $$a, there are $$\binom 9 4$$
• find all subsets $$\{a,b,c,d\}$$ from $$\{1,\ldots,9\}\$$ (w.l.o.g $$a), set $$e:=d$$ to get all 5 digit numbers such that $$a, again there are $$\binom 9 4$$ such numbers
• find all subsets $$\{a,b,c\}$$ from $$\{1,\ldots,9\}\$$ (w.l.o.g $$a), set $$d:=c$$, $$e:=c$$, to get all 5 digit numbers such that $$a, there are $$\binom 9 3$$

So all in all there are $$\binom 9 5 + 2 \binom 9 4 +\binom 9 3 = 462$$ such numbers