Here is the question:
How many non-negative integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 74$ with each $x_j \leq 26$?
We've been instructed to use the $C(n+r-1,r-1)$ identity for the amount of integer solutions for the equation $x_1 + x_2 + \cdots + x_r = n$. They also provided a hint on how to start that makes no sense to me.
Given hint for step 1: Let $U$ be the set of solutions without any restriction, and let $S_j$ be the set of solutions where $x_j > 26$. The size of $S_1$ can be found by replacing $x_1$ with $y_1 = x_1 – 27 \geq 0$ and applying the given formula. What is the size of $S_1$?
I am completely stumped on this question, and I'm not actually sure what the hint is actually pointing me towards. Any help or direction would be appreciated!
Best Answer
Let $U$ be the number of solutions where you don't restrict any of the $x_j$.
Now, let $S_j$ be the number of solutions restricting only $x_j$. Define $y_j = x_j - 27$. Then you have the equation for, for $S_1$ and $x_1$ and $y_1$ for instance,
$$(y_1 + 27) + x_2 + x_3 + x_4 = 74$$
Simplify to $y_1 + x_2 + x_3 + x_4 = 47$. Again, since you only restricted $x_1$, all variables are unrestricted again. ($x_1 \ge 27 \implies y_1 + 27 \ge 27 \implies y_1 \ge 0$)
Why did we let $y_j = x_j - 27$? Because we're counting the number of invalid solutions in every single variable first. $x_j \ge 27$ if it is invalid for any given $j$, and redefining it this way lets us simplify to an equation in unrestricted variables. You can apply your formula to each of the $S_j$.
Bear in mind you will need inclusion-exclusion for this problem, since $S_1$ and $S_2$ for instance could have cases where $x_1$ and $x_2$ both exceed $26$, so you need to account for these duplicates. The process and calculation should be analogous.
The final solution will be $U$ minus a sum of the $S_j$ and their various intersections as a result. This is because what you're ultimately doing is taking the complementary approach: finding the unrestricted solutions, and subtracting from those the number of solutions that are invalid.