6
$\begingroup$

How many numbers of $4$ digits $x_1x_2x_3x_4$ satisfy $x_1\leq x_2 \leq x_3 \leq x_4$?

What I've worked so far:

I have identified this situation with distributing $4$ equal objects among $9$ different boxes (digits from $1$ to $9$).

Therefore, solving the question proposed should be equivalent to solving the number of integer solutions of the following equation: $$y_1+y_2+y_3+y_4+y_5+y_6+y_7+y_8+y_9=4\\ y_i\geq0 \quad \forall i\in\{1,2,...,9\}$$

The total solutions for this equations are: $$\text{CR}_{9}^{4}={4+9-1 \choose 4}={12 \choose 4}=\frac{12!}{4!\cdot8!}=11\cdot9\cdot5=495\text{ posibilities}$$

Is there any other approach you think it's more practical? Is this reasoning correct?

Clarifications: If one distribution of the objets is $6292$ (box nº 6 is the first box where I distribute an object; box nº $2$ the second; box nº $9$ the third and box nº $2$ the fourth). The order in which boxes I distribute the objects doesn't really matter because the objects are identical, so I can rearrange the result to get $2269$ which is a combination that verifies the restriction given.

$\endgroup$

3 Answers 3

5
$\begingroup$

Another way is to set $x_0 = 1$ and $x_5 = 9$. Then define $$ t_i = x_i - x_{i-1} ~~~~(i = 1, 2, 3, 4, 5) $$ as the "jump" from the $i$th digit from the preceding digit.

Now \begin{align} t_1 + t_2 + \ldots + t_5 &= (x_1 - x_0) + (x_2 - x_1) + \ldots + (x_5 - x_4)\\ &= (-x_0 + x_1) + (-x_1 + x_2) + \ldots + (-x_4 + x_5)\\ &= -x_0 + (x_1 -x_1) + (x_2 - x_2) + \ldots + (x_4 -x_4) + x_5\\ &= -x_0 + x_5\\ &= -1 + 9 = 8\\ \end{align}

The numbers $t_i$ are all nonnegative, and their sum is exactly $8$. We end up (using the dual of your reasoning) needing to compute $$ \binom{5+8-1}{8} = \binom{12}{8} = \binom{12}{4} = 495. $$

$\endgroup$
5
  • $\begingroup$ Can you explain more thoroughly how do you proceed from defining $t_i$ to the moment where you conclude that the sum of them is $8$. I didn't follow, sorry. $\endgroup$
    – Rober
    Jun 26, 2019 at 0:54
  • 1
    $\begingroup$ Shouldn't $i$ range up to $5$? And doesn't that make the correct expression $\binom{5+8-1}{8}$? $\endgroup$ Jun 26, 2019 at 0:56
  • 1
    $\begingroup$ @RobertShore: Fixed! (Thanks!) $\endgroup$ Jun 26, 2019 at 0:58
  • $\begingroup$ It is interesting that you solve for the sum of the "jumps". Now I do understand it. Thanks! $\endgroup$
    – Rober
    Jun 26, 2019 at 1:15
  • $\begingroup$ This is a pretty common "dualizing" approach -- you'll see it in other places in combinatorics as well. $\endgroup$ Jun 26, 2019 at 1:27
3
$\begingroup$

Your solution is correct though it took me some time to understand the equivalence between the problem you were given and the problem you set up in your solution. Here's how I'd approach the problem:

The initial digit cannot be $0$ so I'm always choosing digits from $1$ through $9$.

If my number has $4$ distinct digits, then there's a unique way to order them. This gives me $\binom{9}{5}=126$ possibilities.

There are $\binom{9}{6}=84$ ways to choose $3$ distinct digits. Each of these ways gives me $3$ possible numbers (I can choose any of the three digits as the repeated digit), so this adds another $252$ possibilities.

There are $36$ ways to choose $2$ distinct digits. Each of these ways gives me $3$ possible numbers ($xxyy, xxxy, xyyy$), so this adds another $108$ possibilities.

Finally, there are $9$ ways to choose a single digit, repeated $4$ times.

So the total number of possible answers is $126+252+108+9=495.$

$\endgroup$
3
$\begingroup$

Your solution is correct. While I like your approach, here is another way of thinking about the problem.

We can represent any four-digit number by placing four dividers in a row of nine ones, with the dividers placed to the immediate right of the digit that is included in the number. For instance, we can represent $2269$ by $$1 1 \color{blue}{| |} 1 1 1 1 \color{blue}{|} 1 1 1 \color{blue}{|}$$ and $1234$ by $$1\color{blue}{|} 1 \color{blue}{|} 1 \color{blue}{|} 1 \color{blue}{|} 1 1 1 1 1$$ Each such number is completely determined by the positions of the dividers. Since the first digit cannot be zero, the first of the $13$ symbols must be a $1$. Thus, four of the remaining $12$ symbols must be dividers. Choosing which four of those twelve positions will be filled with dividers determines the number. Hence, as you found, there are $$\binom{12}{4}$$ four-digit numbers with non-decreasing digits.

$\endgroup$
4
  • $\begingroup$ I often use this method, but recommend you use an $x$ instead of a $1$ to avoid confusions. $\endgroup$ Jun 26, 2019 at 1:12
  • $\begingroup$ @DavidG.Stork I decided to add color to the dividers, but I appreciate your point. $\endgroup$ Jun 26, 2019 at 1:15
  • $\begingroup$ This interpretation is like the stars and bars problem which is identifiable with solving for the integer solutions of an equation like I proposed. Very interesting! $\endgroup$
    – Rober
    Jun 26, 2019 at 1:17
  • $\begingroup$ Nice...I was trying to think of a stars-and-pipes solution, but didn't stumble on this. $\endgroup$ Jun 26, 2019 at 1:28

You must log in to answer this question.

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