1
$\begingroup$

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.

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

3 Answers 3

8
$\begingroup$

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

$\endgroup$
19
  • $\begingroup$ Great hint (I upvoted) . I think you meant to say that the digits are at most 11 (instead of at most 9) $\endgroup$
    – WW1
    Aug 18, 2021 at 19:20
  • $\begingroup$ Oops, of course (originally between 1 and 9, now between 1 and 11). Thanks, will correct! $\endgroup$ Aug 18, 2021 at 19:41
  • $\begingroup$ @Jukka Kohonen: (1) I don't see how $11$ can be considered as a digit. (2) Only part of the abcde is strictly increasing $\endgroup$ Aug 18, 2021 at 21:39
  • $\begingroup$ 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$. $\endgroup$ Aug 19, 2021 at 0:15
  • $\begingroup$ Nice shortcut (+1). $\endgroup$ Aug 19, 2021 at 6:48
3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Aug 19, 2021 at 0:10
  • $\begingroup$ Corrected 3am error after 10am coffee ! $\endgroup$ Aug 19, 2021 at 4:33
  • $\begingroup$ (+1) I also confirmed the numeric value by brute force. $\endgroup$
    – dodoturkoz
    Aug 19, 2021 at 6:28
  • $\begingroup$ Yes, now it works! (Coffee helps, ask Erdős.) $\endgroup$ Aug 19, 2021 at 6:51
  • $\begingroup$ @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 $\endgroup$
    – user955791
    Aug 19, 2021 at 6:51
2
$\begingroup$

To find all digits such that $0<a < b < c \leq d \leq e$,

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.