# simple combinatorics question about object division

In how many ways you can solve the equation $X_1+X_2+ \cdots +X_{15} = 300$ ($X_1,X_2, \ldots, X_{15}$ are natural numbers) so that :

a) for every $1 \leq i \leq 15$, $X_i \leq 19$
b) for every $1 \leq i \leq 15$, $X_i \leq 20$
c) for every $1 \leq i \leq 15$, $X_i \leq 40$

So I'm 99% sure that a and b are there for the logic and not combinatorics.
$19 \cdot 15 = 285$ so there are $0$ possibilities that it will happen.
$20 \cdot 15 = 300$ so the only option that it will happen will be if all those numbers are $20$.
for c, I'm thinking about taking all the options, so it's $314$ choose $300$ and from there I'm subtracting all the times I give a number $41$, I do it $7$ times because after $8$ times it will be over $300$, am I even close to the right way ? Thank you in advance.

• Do you know how to solve the equation $$x_1 + x_2 + \cdots + x_{15} = 300$$ in the natural numbers when there are no restrictions on the $x_i$? – N. F. Taussig Jan 18 '15 at 20:39
• Yes, it's the same as dividing 300 coins to 15 people, so i assume it's 314 chooses 300. – NotSure Jan 19 '15 at 17:08

If there were no restrictions, then the number of solutions of the equation $$x_1 + x_2 + \cdots + x_{15} = 300$$ in the non-negative integers would be $$\binom{300 + 14}{14} = \binom{314}{14}$$ However, we want each $x_i \leq 40$. Thus, we must subtract the number of solutions for which one or more of the $x_i \geq 41$. Since $7 \cdot 41 = 287 < 300 < 328 = 8 \cdot 41$, up to seven of the $x_i$'s could be at least $41$. To do so, we use the Inclusion-Exclusion Principle.

Subtracting the number of solutions in which exactly one $x_i$ exceeds $40$ from the total removes each solution in which exactly two $x_i$'s exceed $40$ twice, so we must add the number of solutions in which exactly two $x_i$'s exceed $40$. Removing the number of solutions in which exactly one $x_i$ exceeds $40$ from the total number of solutions, then adding back the number of solutions in which exactly two $x_i$'s exceed $40$ counts each solution in which exactly three $x_i$'s exceed $40$ counts once (since each solution was first removed three times, then restored three times), so we must subtract the number of solutions in which exactly three $x_i$'s exceed $40$. By similar reasoning, we must add the number of solutions in which exactly four $x_i$'s exceed $40$, subtract the number in which exactly five $x_i$'s exceed $40$, add the number of solutions in which exactly six $x_i$'s exceed $40$, then subtract the number of solutions in which exactly seven $x_i$'s exceed $40$.

Suppose $x_1 > 40$. Let $y_1 = x_1 - 41$. \begin{align*} x_1 + x_2 + \cdots + x_{15} & = 300\\ y_1 + 41 + x_2 + \cdots + x_{15} & = 300\\ y_1 + x_2 + \cdots + x_{15} & = 259 \end{align*} The number of solutions of this equation in the non-negative integers is $$\binom{259 + 14}{14} = \binom{273}{14}$$ Since there are $15$ ways for exactly one of the $x_i$'s to exceed $40$, the number of solutions in which exactly one $x_i > 40$ is $$\binom{15}{1}\binom{273}{14}$$ Suppose $x_1$ and $x_2$ both exceed $40$. Let $y_1 = x_1 - 41$ and $y_2 = x_2 - 41$. Then \begin{align*} x_1 + x_2 + x_3 + \cdots + x_{15} & = 300\\ y_1 + 41 + y_2 + 41 + x_3 + \cdots + x_{15} & = 300\\ y_1 + y_2 + x_3 + \cdots + x_{15} & = 218 \end{align*} This equation has $$\binom{218 + 14}{14} = \binom{232}{14}$$ solutions in the non-negative integers. Since there are $\binom{15}{2}$ ways for exactly two of the $x_i$'s to exceed $40$, there are $$\binom{15}{2}\binom{232}{14}$$ solutions in which exactly two of the $x_i$'s exceed $40$.

Calculate the number of solutions in which exactly three, exactly four, exactly give, exactly six, and exactly seven of the $x_i$'s exceed $40$, then use the Inclusion-Exclusion Principle to determine the number of solutions in which each $x_i \leq 40$. Your solution should look something like

$$\binom{314}{14} - \binom{15}{1}\binom{273}{14} + \binom{15}{2}\binom{232}{14} - \cdots + \cdots - \cdots + \cdots - \cdots$$

• Very helpful, thank you very much ! – NotSure Jan 19 '15 at 19:11
• You're welcome. – N. F. Taussig Jan 19 '15 at 19:13

The approach that you're taking is certainly along the right path; try making it a bit more formal, using the Inclusion-Exclusion principle, and you'll likely find things simpler.

Alternatively (and equivalently), you could look at generating functions: the ordinary generating function for the choices for a given $X_i$ is $$\sum_{i=0}^{40}x^i,$$ since there's only one choice of each size; this is a geometric sum, and can be simplified. What does the OGF for the sum $X_1+\cdots+X_{15}$ look in this case, and what coefficient will tell you how many combinations sum to $300$?

• Say i want to use the Inclustion - Exclusion principle here, how can i use it in a formal way ? thank you. – NotSure Jan 18 '15 at 18:39
• @MattG See the answer by Taussig. – Henno Brandsma Jan 19 '15 at 18:02