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

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)?

• Are single digit numbers counted as rising numbers? What is the largest possible rising number? Jun 27, 2020 at 5:01
• Ah, see my edit Jun 27, 2020 at 5:02

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}$$

• Sorry, I omitted a key part of the question: three digit Jun 27, 2020 at 5:03
• I'm rusty on combinatorics when it comes to your notation. Is (9 3) 9C3 or 9P3? Jun 27, 2020 at 5:07
• It is corresponding to 9 choose 3 Jun 27, 2020 at 5:07
• The easy way to see $2^9-1$ (assuming single digit numbers are rising) is to take the number $123456789$ - to make a rising number each digit is either in or out $2^9$ - but you can't leave them all out - hence $2^9-1$ Jun 27, 2020 at 6:57

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

• @dhanvisreenivasan, is this correct by your formula? Jun 27, 2020 at 5:06
• @markbennet, do you agree? Jun 27, 2020 at 5:06
• @gill it is consistent with mine Jun 27, 2020 at 5:07
• @Global05 thanks for confirming both the first and answering the second, with a detailed method. Jun 27, 2020 at 5:08
• This math is very cool! Oct 26, 2020 at 11:12

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