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$
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 '19 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$ – Robert Shore Jun 26 '19 at 0:56
  • 1
    $\begingroup$ @RobertShore: Fixed! (Thanks!) $\endgroup$ – John Hughes Jun 26 '19 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 '19 at 1:15
  • $\begingroup$ This is a pretty common "dualizing" approach -- you'll see it in other places in combinatorics as well. $\endgroup$ – John Hughes Jun 26 '19 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$ – David G. Stork Jun 26 '19 at 1:12
  • $\begingroup$ @DavidG.Stork I decided to add color to the dividers, but I appreciate your point. $\endgroup$ – N. F. Taussig Jun 26 '19 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 '19 at 1:17
  • $\begingroup$ Nice...I was trying to think of a stars-and-pipes solution, but didn't stumble on this. $\endgroup$ – John Hughes Jun 26 '19 at 1:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.