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$
    – Misha Lavrov
    Aug 18, 2021 at 18:32
  • $\begingroup$ @MishaLavrov little mistake , thanks $\endgroup$
    – Not a Salmon Fish
    Aug 18, 2021 at 18:33
  • $\begingroup$ Does $a$ have to be nonzero? $\endgroup$
    – Jukka Kohonen
    Aug 18, 2021 at 18:34
  • $\begingroup$ @JukkaKohonen yeap , to be 5 digit , it has to be nonzero $\endgroup$
    – Not a Salmon Fish
    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$
    – Adam Rubinson
    Aug 18, 2021 at 18:41

3 Answers 3

Reset to default
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$
    – Jukka Kohonen
    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$
    – true blue anil
    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$
    – Jukka Kohonen
    Aug 19, 2021 at 0:15
  • $\begingroup$ Nice shortcut (+1). $\endgroup$
    – true blue anil
    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$
    – Jukka Kohonen
    Aug 19, 2021 at 0:10
  • $\begingroup$ Corrected 3am error after 10am coffee ! $\endgroup$
    – true blue anil
    Aug 19, 2021 at 4:33
  • $\begingroup$ (+1) I also confirmed the numeric value by brute force. $\endgroup$
    – krazy-8
    Aug 19, 2021 at 6:28
  • $\begingroup$ Yes, now it works! (Coffee helps, ask Erdős.) $\endgroup$
    – Jukka Kohonen
    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$
    – Not a Salmon Fish
    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$

You must log in to answer this question.

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