-1
$\begingroup$

This question already has an answer here:

how many solutions in natural numbers are there to the inequality
$x_1 + x_2 +....+ x_{10} \leq 70$ ?

I know it has to be solved with combinatorics and specifically with the inclusion exclusion principle but I have no idea where to start. Help ?

$\endgroup$

marked as duplicate by N. F. Taussig, lulu, awkward, Namaste discrete-mathematics Jan 16 '18 at 14:28

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

Inclusion-exclusion is not the best way to solve this.. A much better way is using the "stars and bars" approach.

I'll use smaller numbers so that I can actually illustrate this, then you're free to apply it to your problem. So let's find the number of solutions to $x_1+x_2+x_3+x_4 = 10$ (note the equals sign here, I will come back to that). Also, I'm assuming that $0$ is a natural number, because that makes the solution a lot easier.

So, let's say we have $10$ identical marbles, and we want to distribute them into four distinct boxes (say the boxes are numbered 1 to 4, or have different color, or whatever). We want to know in how many ways this can be done. One way is to put all the marbles into box number 1. One way is to put five each in boxes 2 and 3. And so on.

The next step is to find a systematic way to describe all these possible arrangements. Say you put the boxes in a row, and you put the marbles into the boxes in some way. Then the arrangement corresponding to $x_1 = x_2 = 3, x_3 = x_4 = 2$ looks like this: $$ \boxed{3} \,\boxed{3}\,\boxed 2\,\boxed 2 $$ Of course, it's a lot more visual to actually draw the marbles. I'll use $*$ to signify a marble, because it's easy to type. The same arrangement will then look like $$ \boxed{***} \,\boxed{***}\,\boxed{\!\!{}**}\,\boxed{\!\!{}**} $$ Also, we don't really need to draw the boxes. We can just put a divider between them, so we know which $*$ belong to the first box, the second box, and so on. The same arrangement now looks like this: $$ ***\mid***\mid{}**{}\mid{}** $$ We see that any way to order ten stars and three bars gives exactly one arrangement of marbles, which again corresponds to exactly one solution to the original equation. Similarily, each solution to the original equation corresponds to exactly one arrangement of marbles, which again corresponds to a specific order of stars and bars. (An empty box, which is to say, a variable that is $0$, is signified by two bars being next to one another.)

So the number of solutions to the original equation is equal to the number of ways to order $3$ bars and $10$ stars. How many ways are there of doing that? To see that, here is yet another way of looking at it. Below we have thirteen spots, each of which can have either a bar or a star. $$ \_\,\_\,\_\,\_\,\_\,\_\,\_\,\_\,\_\,\_\,\_\,\_\,\_ $$ We want to know the number of ways that we can pick $10$ of them to put a star in (which makes the final three have a bar). That can be done in $\binom{13}{10}$ ways. So that is the number of solutions to our original equation.

Finally, a word on equality vs. inequality, and $0$. If we let the final box signify not really a box, but marbles we throw away, we see that this same argumentation gives the number of solutions to $x_1+x_2+x_3\leq 10$. Also, if $0$ is not allowed, we start out by putting a marble in each box (except the last "throwaway" box if we're using that), forgetting about them, and solve the problem as before, but with fewer marbles available ($6$ marbles if we're solving $x_1+x_2+x_3+x_4 = 10$, and $7$ marbles if we're solving $x_1+x_2+x_3\leq 10$, since then the "throwaway" box is allowed to contain $0$).

$\endgroup$
  • $\begingroup$ Thank you for the effort ! $\endgroup$ – MathChallenged Jan 16 '18 at 12:30
0
$\begingroup$

Inclusion-exclusion won't help much here. What you really want is stars and bars, breaking a pile of $70$ ($60$ if your natural numbers start at $1$) into $11$ smaller piles using $10$ bars. This gives $$\binom{80}{10}$$ or $\binom{70}{10}$ in the starts at $1$ case.

$\endgroup$

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