4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – N. F. Taussig Jan 18 '15 at 20:39
  • 1
    $\begingroup$ Yes, it's the same as dividing 300 coins to 15 people, so i assume it's 314 chooses 300. $\endgroup$ – NotSure Jan 19 '15 at 17:08
4
$\begingroup$

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$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very helpful, thank you very much ! $\endgroup$ – NotSure Jan 19 '15 at 19:11
  • $\begingroup$ You're welcome. $\endgroup$ – N. F. Taussig Jan 19 '15 at 19:13
1
$\begingroup$

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$?

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

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.