0
$\begingroup$

How many n-digit numbers with strictly increasing digits do exist?$(n<10)$
We mean numbers like: $13458$,these numbers do not have $0$ as a digit.How can we count them??
I used trees to distinguish and count each case of these numbers,but is there any combinatorial technique to count such numbers???

$\endgroup$
  • $\begingroup$ is 112233 valid? Repetitions of same digit allowed? Or has to be increasing for every successive place value. $\endgroup$ – sanketalekar Apr 30 '16 at 14:53
  • $\begingroup$ @sanketalekar it says strictly increasing. $\endgroup$ – Henno Brandsma Apr 30 '16 at 17:08
  • $\begingroup$ 112233 is not valid $\endgroup$ – Hamid Reza Ebrahimi Apr 30 '16 at 17:44
3
$\begingroup$

Such a number is just a $n$ size subset of $\{1,\ldots,9\}$. Such a subset has a unique increasing order (which is the number representation).

So there are $\binom{9}{n}$ such numbers.

$\endgroup$
  • $\begingroup$ Can you explain more please? $\endgroup$ – Hamid Reza Ebrahimi Apr 30 '16 at 17:46
  • 1
    $\begingroup$ The digits in the number form a subset of size $n$. And if we have any subset of size $n$, there is only one way to write the subset in increasing order. So there is a bijection between your increasing numbers and subsets of size $n$ (and $0$ is not allowed). The binomial coefficient counts those subsets. $\endgroup$ – Henno Brandsma Apr 30 '16 at 18:22

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.