2
$\begingroup$

How many $5$ digit numbers are there such that digits are in ascending order ?

I think it must be $5 \times 6^4$ , But I'm not sure. I would love to see an algorithm to solve this kind of problems.

$\endgroup$
  • 2
    $\begingroup$ Do you allow repeated digits? $\endgroup$ – Parcly Taxel Oct 8 '18 at 15:37
  • $\begingroup$ Once you choose the digits, there's only one way to arrange them. $\endgroup$ – saulspatz Oct 8 '18 at 15:38
  • $\begingroup$ Can you answer the question for one and two digit numbers, then three? That might lead you to a solution. $\endgroup$ – Ethan Bolker Oct 8 '18 at 15:38
  • $\begingroup$ @saulspatz assuming no repeating digits $\endgroup$ – Don Thousand Oct 8 '18 at 15:39
  • $\begingroup$ I think no repeating digits, that wouldn't really be acceding order $\endgroup$ – R0xx0rZzz Oct 8 '18 at 15:41
4
$\begingroup$

There are two answers here, depending on the criteria you hold.

If you require that the digits are strictly ascending, i.e., repeated digits are not allowed, this question becomes rather simple, as for each combination of digits, there is only "valid" ordering of numbers. Hence, we simply take the combination of 5 digits from the numbers 1,2,3,4,5,6,7,8,9 (no 0 because a number can't start with 0). This gives us $${9\choose 5} = 126$$

If you allow repeated digits, then it's a bit more tricky. If the digits are $a,b,c,d,e$, we define $u=a-1, v=b-a,w=c-b, x=d-c,y=e-d, z=9-e$. This is useful because $$u+v+w+x+y+z=8$$ and each of these numbers must be $\geq0$. So, we use stars and bars to get ${13\choose 5} = 1287$.

P.S. You could also use stars and bars for the strictly ascending case! You should try it out to see whether you can replicate the same solution I've derived.

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