4
$\begingroup$

Q: How many positive integers are there whose digits strictly increase from left to right? ($0$ is not allowed to be the leading digit)


Here're my thoughts on the problem.

For one digit numbers.

There are only $9$ such integers that satisfy the problem.

For two digit numbers.

If we start with $1$ as the left most digit, then we have $8$ choices for the one's place. So we have $8$ such numbers.

If we start with $2$ as the left most digit, then we have $7$ choices for the one's place.

If we start with $3$ as the left most digit, then we have $6$ choices for the ones place.

Continuing this process we have $8+7+6+ ... +2+1 = 36$ such numbers.

But for three - digit numbers, I'm stuck. What am I suppose to do, after I've chosen the first digit? I'll have to make sub cases for the second digit, and it'll get more complicated as I go up to 9 - digit numbers.


P.S. I know we have a question such as [Number of strictly increasing and decreasing 4 digit numbers?], but I don't quite get the hints ...

$\endgroup$
2
  • $\begingroup$ Wait, so are zeros in the middle of the number allowed or not? $\endgroup$ Commented Apr 19, 2018 at 14:50
  • $\begingroup$ I just edited the post. Zeroes are not allowed :) $\endgroup$ Commented Apr 19, 2018 at 14:51

2 Answers 2

5
$\begingroup$

An easier approach is to see there is one such integer for each nonempty subset of $\{1,2,3,4,5,6,7,8,9\}$. Once you have a subset, you arrange the digits in increasing order, so there are $2^9-1$ integers with strictly increasing digits.

$\endgroup$
4
  • $\begingroup$ No, $\{2,3,5\}$ is one of the subsets, given the number $235$ $\endgroup$ Commented Apr 19, 2018 at 14:38
  • $\begingroup$ Perhaps $0$ is allowed, making the answer $1024$. Or single digits are not allowed, making the answer $1014$ $\endgroup$
    – Henry
    Commented Apr 19, 2018 at 14:40
  • $\begingroup$ @Henry: allowing a leading $0$ does not allow any other positive integers. It allows more digit strings, but not positive integers. $\endgroup$ Commented Apr 19, 2018 at 14:44
  • $\begingroup$ I'm sorry, $2^{9}-1$ is correct ... the formatting was wrong on my part. $\endgroup$ Commented Apr 19, 2018 at 14:46
2
$\begingroup$

Lets say the number has $k$ digits, all distinct. We notice, that out of all possible permutations of the digits, only one satisfies the condition of the problem, that is, strictly ascending.

If we would try to generate a solution ourselves, we would pick digits from 1 to 9 $k$ times, except we would not be allowed to pick the same digit twice. The number of ways to do this for a fixed $k$ is the number of combinations

$C(n, k) = \frac{n!}{k!(n-k)!}$

where $n=9$ is the total number of digits we choose from

The total number of solutions is sum over number of solutions for a fixed digit length

$S = \sum_{k=1}^{n} C(n, k)$

As mentioned here

https://en.wikipedia.org/wiki/Binomial_coefficient#Sum_of_coefficients_row

There is a theorem for summing up binomial coefficients $C(n,k)$, which states that

$S = 2^n - 1 = 511$ in your case

$\endgroup$
2
  • 1
    $\begingroup$ You can't use $0$ because we don't allow that as a leading digit. $\endgroup$ Commented Apr 19, 2018 at 14:40
  • $\begingroup$ Already fixed, thanks $\endgroup$ Commented Apr 19, 2018 at 14:41

You must log in to answer this question.

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