Number of $3$-digit numbers with strictly increasing digits

Question

A positive integer is called a rising number if its digits form a strictly increasing sequence. For example, 1457 is a rising number, 3438 is not a rising number, and neither is 2334.

(a) How many three digit rising numbers have 3 as their middle digit?

(b) How many three digit rising numbers are there?

My efforts have yielded 12 for (a) - 1 and 2 for the first digit, and 4, 5, 6, 7, 8, 9 for the 3rd so $2 \cdot 6 = 12$ possibilities. Is this correct? What is the best method for (b)?

Answer 1

(A) If the middle digit is $3$, there are only $2$ possibilities for the $1$st digit: $1$ and $2$, for it to be rising. For the third, it can be any number greater than $3$, i.e. $4, 5, 6, 7, 8$, or $9$. This is $6$ numbers, therefore the total number of rising numbers with 3 as their middle digit is $ 2 \cdot 1 \cdot 6 = 12$ possibilities.

(b) We can list out by cases and subcases:


Case 1: First digit is $1$:

We see if the 2nd digit is $2$, there are $7$ possibilities for the 3rd.

We see if the $2$nd digit is $3$, there are $6$ possibilities for the $3$rd.

We see if the $2$nd digit is $4$, there are $5$ possibilities for the $3$rd.

This pattern continues, so there are $7 + 6 + 5 + 4 + 3 + 2 + 1 = 28$ possibilities.

Case $2$: First digit is $2$:

We see if the $2$nd digit is $3$, there are $6$ possibilities for the $3$rd.

We see if the $2$nd digit is $4$, there are $5$ possibilities for the $3$rd.

This pattern continues, so there are $6 + 5 + 4 + 3 + 2 + 1 = 21$ possibilities.

Case $3$: First digit is $3$:

Following the pattern from previous cases, there are $5 + 4 + 3 + 2 + 1 = 15$ possibilities

Case $4$: First digit is $4$:

Following the pattern from previous cases, there are $4 + 3 + 2 + 1 = 10$ possibilities

Case 5: First digit is $5$:

Following the pattern from previous cases, there are $3 + 2 + 1 = 6$ possibilities

Case $6$: First digit is $6$:

Following the pattern from previous cases, there are $2 + 1 = 3$ possibilities

Case $7$: First digit is $7$:

Following the pattern from previous cases, there is $1$ possibility here.

It cannot start with $8$, as the $2$nd digit would be $9$, leaving no possibilities for the $3$rd.

So the total is $28 + 21 + 15 + 10 + 6 + 3 + 1 =$ $84$ possibilities.

Edit: While I was accepted as the correct answer for confirming (a) also, I thought I should also acknowledge @DhanviSreenivasan's elegant formula:

$$\sum_{k=1}^9{9\choose k} = 2^9-1$$

Which gives us ${9 \choose 3}$ so $84$.

Answer 2

If you pick any $k$ distinct digits out of 9, there is exactly one way to make a rising number out of it

Hence, total number of rising numbers is $$\sum_{k=1}^9{9\choose k} = 2^9-1$$

EDIT

For 3 digit numbers, if you pick any 3 distinct digits, there is exactly one rising number corresponding to those digits - hence there is a one-to one mapping between number of ways of selecting three distinct digits, and the number of 3 digit rising numbers

Hence - answer is ${9 \choose 3}$

Answer 3

I'm little afraid this can be considered little rigorous and verbosal but this is my try :).

a) You can fix the digit '$3$' in the middle:

_ $3$ _

Then for its first digit you got $2$ options $\{1, 2\}$ whereas the third digit has $6$ options: $\{4, 5, 6, 7, 8, 9\}$.

Hence you have $2*6 = 12$ by Product Principle.

---

b) Since you must choose an increasing numbers which is a number between 100 and 999 (both inclusive). You may start looking for the first digit which can be choose from the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Since $0$ can't be choose due to the range (numbers greater or equal than $100$) . Then there're $9$ ways to pick the first digit.

WLOG you can pick the second digit from the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ but removing the previous number selection which is 8 ways and finally you can pick the third number, removing the first and previous number selection as well, hence there're $7$ ways to do it. This $^9P_3$

Since for each of this pick, there're $3!$ permutations in which just one of them is a rising number. For instances:

First digit: $3$

Second digit: $2$

Third digit: $7$

You have this permutations set: $\{ 327, 372, 723, 732, 237, 273\}$ which has $3! = 6$ permutations but just one of them ($237$) is a rising number.

Then you got in general, by Bijection Principle:

$\frac{^9P_3}{3!} = {{9} \choose {3}} = 84$