Possible numbers under the given restriction

[Saitama]

Problem:
All 4 digit numbers of the form $x_1x_2x_3x_4$ are formed by using digits $1,2,3,4,5,6,7,8,9$ such that $x_1\leq x_2 \leq x_3 \leq x_4$.

a)Find the total number of such possible 4-digit numbers.

b)The numbers are written in ascending order. If the number with rank 460 is abcd, then find $\frac{a+b+c+d}{4}$.

Attempt:
I have dealt with the case when $x_1<x_2<x_3<x_4$ in the past but how do I solve the problem when the numbers can be equal too?

 

[magneto1]

Once you have chosen a set of digits, there is only 1 way to arrange it such the digits are non-decreasing. So consider the case where all 4 digits are different: there are
$\binom 94$ many ways. If the set contains only 3 distinct digits (i.e., one digit repeats twice) there are $3 \binom 93$. If the set contains 2 distinct digits each repeated twice,
then there are $\binom 92$ possibilities; if it contains 2 distinct digits where 1 appears once
the other appears 3 times, then there are $2\binom 92$ many ways. Lastly there are 9 ways
if a single digit appearing 4 times. The answer to (a) is when you add them together.

 

[Saitama]

Once you have chosen a set of digits, there is only 1 way to arrange it such the digits are non-decreasing. So consider the case where all 4 digits are different: there are
$\binom 94$ many ways. If the set contains only 3 distinct digits (i.e., one digit repeats twice) there are $3 \binom 93$. If the set contains 2 distinct digits each repeated twice,
then there are $\binom 92$ possibilities; if it contains 2 distinct digits where 1 appears once
the other appears 3 times, then there are $2\binom 92$ many ways. Lastly there are 9 ways
if a single digit appearing 4 times. The answer to (a) is when you add them together.

Hi magneto! :)

Thanks for the help, I think I understand your solution.

I remember seeing a similar problem where the problem asks to find the number of possible solutions for: $0 \le x_1 \le x_2 \le ... \le x_{10} \le 25$. I think we are dealing with the same problem i.e we have to find the solutions of $0\le x_1 \le x_2 \le x_3 \le x_4 \le 9$.

The solution to the problem $0 \le x_1 \le x_2 \le ... \le x_{10} \le 25$ is as follows:

Shift $x_2$ to $x_{10}$ by 1 to the right (adding 1), then shift $x_3$ to $x_{10}$ by 1 to the right and so on, so we have shifted a total of 9 to the right, therefore, the problem becomes finding the number of solutions to: $0 \le x_1 < x_2 < x_3 < ... < x_{10} \le 34$, which is $\dbinom{35}{10}$.

I don't understand the solution though. Can you please help me understand the above? I think with this method, the problem at hand can be easily solved without dealing with too many cases.

 

[magneto1]

If you add the terms up, you will get 495 as an answer.

The other solution, which is a lot cleaner, is to find a way to move all the $\leq$ to become $<$. If we have, $1 \leq a \leq b \leq c \leq 9$, we want the inequality to become
$1 \leq a < b < c \leq ?$. Since they are integer, by moving each $\leq$ to become $<$
the maximum is increased (shifted by $1$). Therefore, if you have $4$ elements, that maximum of $9$ will shift $3$ times becoming $12$.

I.e., $1 \leq a_1 \leq a_2 \cdots \leq a_4 \leq 9$ is equivalent to
$1 \leq a_1 < a_2 \cdots < a_4 \leq 12$. In which case,
$\binom{12}{4} = 495$, which is the same answer.

 

[Plato2]

Problem:
All 4 digit numbers of the form $x_1x_2x_3x_4$ are formed by using digits $1,2,3,4,5,6,7,8,9$ such that $x_1\leq x_2 \leq x_3 \leq x_4$.

a)Find the total number of such possible 4-digit numbers.
how do I solve the problem when the numbers can be equal too?

Use multi-set selections:

Chose a four element multiset from $\{1,2,3,4,5,6,7,8,9\}$

That is $\dbinom{4+9-1}{4}=\dbinom{12}{4}=495$

 

[Saitama]

Since they are integer, by moving each $\leq$ to become $<$
the maximum is increased (shifted by $1$).

This is the part where I am confused, why is it valid to do so?

Use multi-set selections:

Chose a four element multiset from $\{1,2,3,4,5,6,7,8,9\}$

That is $\dbinom{4+9-1}{4}=\dbinom{12}{4}=495$

Thanks for the alternative method! :)

 

[Opalg]

Since they are integer, by moving each $\leq$ to become $<$
the maximum is increased (shifted by $1$).

This is the part where I am confused, why is it valid to do so?

Think of it as a method for encoding a number. Given a four-digit number, add 0 to its first digit, 1 to its second digit, 2 to its third digit and 3 to its fourth digit. So for example if the number is 3338, its encoded form will be 345(11). If the original digits $x_1x_2x_3x_4$ satisfied $1\leqslant x_2\leqslant x_3\leqslant x_4 \leqslant 9$ then the encoded ones $y_1y_1y_3y_4$ will satisfy $1\leqslant y_1 < y_2 < y_3 < y_4 \leqslant 12$. Conversely, you can decode a number by subtracting 0 from its first digit, 1 from its second digit, and so so. For example, $256(10)$ will decode as 2447. That way, you see that there is a one-to-one correspondence between the two sets of numbers, so both sets must have the same size.

 

[Saitama]

Hi Opalg!

. Given a four-digit number, add 0 to its first digit, 1 to its second digit, 2 to its third digit and 3 to its fourth digit.

But how does this ensure that the $\leq$ signs will definitely change to $<$?

Sorry if this sounds dumb but I can't help it, combinatorics is my weakest point.

 

[Opalg]

But how does this ensure that the $\leq$ signs will definitely change to $<$?

Look at the numerical example that I gave, where $3338$ goes to $345(11)$. Each digit gets increased by 1 more than the digit to the left of it. So the equal digits 3, 3, 3 get transformed to the strictly increasing sequence 3,4,5. That illustrates what happens in general: if the original number contains equal digits, then they will get increasingly augmented by the "encoding" procedure, so that they become strictly increasing.

 

[Saitama]

Look at the numerical example that I gave, where $3338$ goes to $345(11)$. Each digit gets increased by 1 more than the digit to the left of it. So the equal digits 3, 3, 3 get transformed to the strictly increasing sequence 3,4,5. That illustrates what happens in general: if the original number contains equal digits, then they will get increasingly augmented by the "encoding" procedure, so that they become strictly increasing.

I am not sure if I get it. Can we do this: increase the first digit by 0, second by 2, third by 4 and fourth by 6 to get: $1\le x_1 <x_2<x_3<x_4\le 15$. This would give $15\choose 4$ and this is definitely wrong. Where is the flaw here?

 

[Opalg]

I am not sure if I get it. Can we do this: increase the first digit by 0, second by 2, third by 4 and fourth by 6 to get: $1\le x_1 <x_2<x_3<x_4\le 15$. This would give $15\choose 4$ and this is definitely wrong. Where is the flaw here?

If you "encode" a sequence in that way, then the corresponding way to "decode" a sequence would be to decrease the first digit by 0, second by 2, third by 4 and fourth by 6. Now let $A$ be the set of sequences $x_1x_2x_3x_4$ such that $1\leqslant x_1 \leqslant x_2\leqslant x_3\leqslant x_4\leqslant 9$, and let $B$ be the set of sequences $x_1x_2x_3x_4$ such that $1\leqslant x_1 <x_2<x_3<x_4\leqslant 15$. Your proposed procedure takes sequences in $A$ to some of the sequences in $B$. But there are many sequences in $B$ that do not come from sequences in $A$. For example, if you "decode" the sequence $1\,3\,4\, 5$ in $B$, you get $1\,1\,0\,(-1)$, which is certainly not in $A$. In fact, $B$ contains $15\choose 4$ elements and $A$ only has $12\choose 4$ elements.

If you want to show that two sets have the same number of elements, you must show that there is a bijective correspondence between them, in which each element of the first set goes to an element of the second set, and each element of the second set comes from an element of the first set.

 

[Saitama]

If you "encode" a sequence in that way, then the corresponding way to "decode" a sequence would be to decrease the first digit by 0, second by 2, third by 4 and fourth by 6. Now let $A$ be the set of sequences $x_1x_2x_3x_4$ such that $1\leqslant x_1 \leqslant x_2\leqslant x_3\leqslant x_4\leqslant 9$, and let $B$ be the set of sequences $x_1x_2x_3x_4$ such that $1\leqslant x_1 <x_2<x_3<x_4\leqslant 15$. Your proposed procedure takes sequences in $A$ to some of the sequences in $B$. But there are many sequences in $B$ that do not come from sequences in $A$. For example, if you "decode" the sequence $1\,3\,4\, 5$ in $B$, you get $1\,1\,0\,(-1)$, which is certainly not in $A$. In fact, $B$ contains $15\choose 4$ elements and $A$ only has $12\choose 4$ elements.

If you want to show that two sets have the same number of elements, you must show that there is a bijective correspondence between them, in which each element of the first set goes to an element of the second set, and each element of the second set comes from an element of the first set.

Wonderful explanation, thanks Opalg! :)

I attempt part b) now.

If $x_1=1$, then the total possible numbers starting with $1$ are the solutions of $1\le x_2\le x_3\le x_4 \le 9$ which is ${11\choose 3} = 165$.

Numbers starting with $x_1=2$ are solutions of $2\le x_2\le x_3\le x_4 \le 9$ i.e ${10 \choose 3}=120$

With $x_1=3$, possible numbers are: ${9 \choose 3}=84$

With $x_1=4$, possible numbers are: ${8 \choose 3}=56$.

So far, I have counted $425$ numbers.

With $x_1=5$, possible numbers are: ${7 \choose 3}=35$. Since $425+25=460$, this means that the largest possible number with $x_1=5$ is our answer. Hence, $abcd=5999$ which is the correct answer.

I am wondering if it possible to solve part b) by counting from the end. $495-460=35$ are less cases to consider but I am not sure about how to solve it the other way.

 

[Opalg]

Wonderful explanation, thanks Opalg! :)

I attempt part b) now.

If $x_1=1$, then the total possible numbers starting with $1$ are the solutions of $1\le x_2\le x_3\le x_4 \le 9$ which is ${11\choose 3} = 165$.

Numbers starting with $x_1=2$ are solutions of $2\le x_2\le x_3\le x_4 \le 9$ i.e ${10 \choose 3}=120$

With $x_1=3$, possible numbers are: ${9 \choose 3}=84$

With $x_1=4$, possible numbers are: ${8 \choose 3}=56$.

So far, I have counted $425$ numbers.

With $x_1=5$, possible numbers are: ${7 \choose 3}=35$. Since $425+25=460$, this means that the largest possible number with $x_1=5$ is our answer. Hence, $abcd=5999$ which is the correct answer.

I am wondering if it possible to solve part b) by counting from the end. $495-460=35$ are less cases to consider but I am not sure about how to solve it the other way.

Your method is fine, and you could apply exactly the same method from the other end.

With $x_1 = 9$, there is ${3\choose3} = 1$ possible number.

With $x_1 = 8$, there are ${4\choose3} = 4$ possible numbers.

With $x_1 = 7$, there are ${5\choose3} = 10$ possible numbers.

With $x_1 = 6$, there are ${6\choose3} = 20$ possible numbers.

That adds up to $35$, so the number you want is the previous one, namely $5999$.

 

[Saitama]

Your method is fine, and you could apply exactly the same method from the other end.

With $x_1 = 9$, there is ${3\choose3} = 1$ possible number.

With $x_1 = 8$, there are ${4\choose3} = 4$ possible numbers.

With $x_1 = 7$, there are ${5\choose3} = 10$ possible numbers.

With $x_1 = 6$, there are ${6\choose3} = 20$ possible numbers.

That adds up to $35$, so the number you want is the previous one, namely $5999$.

Thank you once again Opalg! :)