9
$\begingroup$

I need to find the number of possibilities for which the following equation exists:

$$x_1 + x_2 + x_3 + \cdots + x_{10} \leq 70$$

Each variable is a non-negative integer.

I tried simplifying the question to the point of finding the number of possible solutions to each equation seperatly:

$$x_1 + x_2 + x_3 + \cdots + x_{10} = 70,$$ which is ${79}\choose{10}$.

$$x_1 + x_2 + x_3 \cdots + x_{10} = 69,$$ which is ${78}\choose{10}$.

$$x_1 + x_2 + x_3 + \cdots + x_{10} = 68,$$ which is ${77}\choose{10}$, and so forth.

Then I thought about adding all of these together. This seems a bit too much work considering that the textbook solution is: ${80}\choose{10}$, and I can't seem to figure out the idiomatic way of approaching these kind of questions.

Any help is greatly appreciated.

$\endgroup$
17
$\begingroup$

Do you know stars and bars? One usually solves this by introducing an additional variable, say $w$, and considering solutions to

$$x_1 + x_2 + x_3 + \cdots + x_{10} +w = 70$$

Can you see how solutions to your original inequality correspond to solutions to the equality above?

$\endgroup$
  • $\begingroup$ That's clever! I was introduced to the concept of start and bars actually by representing them as balls and baskets. I see now how adding another basket results in the inequality I introduced. This was very helpful, thanks! $\endgroup$ – 0rka Jan 15 '18 at 15:50
  • $\begingroup$ You're welcome! Glad to help. $\endgroup$ – Fimpellizieri Jan 15 '18 at 17:08
  • $\begingroup$ @0rka : See also "slack variable". $\endgroup$ – Eric Towers Jan 15 '18 at 21:20
3
$\begingroup$

Here is another way using your original method. The number of solutions to $$ x_1+x_2+\dotsb+x_{10}=r\quad (0\leq r\leq 70) $$ is $$ \binom{r+10-1}{10-1}=\binom{r+9}{9}. $$ Thus the number of solutions to $$x_1 + x_2 + x_3 + \cdots + x_{10} \leq 70$$ is $$ \sum_{r=0}^{70}\binom{r+9}{9}= \sum_{k=9}^{79}\binom{k}{9} =\sum_{k=9}^{79}\left[\binom{k+1}{10}-\binom{k}{10}\right] =\binom{80}{10} $$ as the sum telescopes.

$\endgroup$

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.