Number of total possibilities for an equation

Question

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.

Answer 1

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?

Answer 2

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.