$\begingroup$

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

$\endgroup$ 2

2 Answers

$\begingroup$

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

$\endgroup$ 4 $\begingroup$

(A) If the middle digit is 3, there are only 2 possibilities for the 1st 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, so 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 2nd digit is 3, there are 6 possibilities for the 3rd.

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

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 2nd digit is 3, there are 6 possibilities for the 3rd.

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

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 2nd digit would be 9, leaving no possibilities for the 3rd.

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.

$\endgroup$ 5

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy