Counting solutions to $x_1 + x_2 + x_3 + x_4 = 12$ with at least one $x_i\ge 5$.

Question

Count the non-negative integral solutions of $x_1 + x_2 + x_3 + x_4 = 12$ with at least one $x_i\ge 5$.

I got really confused about that problem and really would like to know about methods to solve this.

I have tried to substitute the variables and the result for $7$ and then adding the $5$ later. I also thought about subtracting and using the pigeonhole principle.

Answer 1

For $x_1+x_2+x_3+x_4=12$ with integer $x_i\ge 0$ without other constraints we use stars and bars to get ${12+4-1\choose 4-1}=455$.
Then we subtract cases $(4, 4, 4, 0): 4, (4, 4, 3, 1): 12, (4, 4, 2, 2): 6, (4, 3, 3, 2): 12, (3, 3, 3, 3): 1$ where no $x_i\ge 5$.
In order not to enumerate the possibilities by hand, let $x_i'=4-x_i$ then $x_1+x_2+x_3+x_4=12$ becomes $x_1'+x_2'+x_3'+x_4'=4$ and we can use stars and bars again, getting ${4+4-1\choose 4-1}=35$ disallowed possibilities.
So the final answer is $${12+4-1\choose 4-1}-{4+4-1\choose 4-1}=455-35=420.$$

Answer 2

We can first get $4$ numbers adding to $7 = ^{(7+4-1)}C_{(4-1)} = 120$. As $5$ can be added to any of the $4$ numbers, multiply the answer by $4$.

Then we need to subtract duplicate arrangements -

$\{7,0,0,0\}$ arrangements that make arrangements of $\{7,5,0,0\}$ by adding $5$ are already covered in $\{2,5,0,0\}$ arrangements. So for each place of $7$, the only valid placement of $5$ is with $7$. Other $3$ are duplicates.

$S1 = 4 \times 3 = 12$

$\{6,1,0,0\}$ arrangements that make arrangements of $\{6,1,5,0\}$ by adding $5$ are already covered in $\{5,1,1,0\}$ arrangements.

$S2 = 2 \times \dfrac{4!}{2!} = 24$

$\{6,1,0,0\}$ arrangements that make arrangements of $\{6,6,0,0\}$ by adding $5$ are counted twice.

$S3 = \dfrac{1}{2} \times \dfrac{4!}{2!} = 6$

$\{5,2,0,0\}$ arrangements that make arrangements of $\{5,2,5,0\}$ by adding $5$ are counted twice.

$S4 = \dfrac{4!}{2!} = 12$

$\{5,1,1,0\}$ arrangements that make arrangements of $\{5,1,1,5\}$ by adding $5$ are counted twice.

$S5 = \dfrac{1}{2} \times \dfrac{4!}{2!} = 6$

Total valid arrangements $= 480 - (S1+S2+S3+S4+S5) = 420$.

Answer 3

Here's an inclusion-exclusion approach, where the four properties are $x_i \ge 5$, and at most two of them can hold simultaneously because $\lfloor 12/5 \rfloor = 2$: $$ \sum_{k=1}^2 (-1)^{k-1} \binom{4}{k}\binom{12-5k+4-1}{4-1} =\binom{4}{1}\binom{10}{3}-\binom{4}{2}\binom{5}{3} = 480-60=420 $$ The idea is that once you specify $k$ of the properties, you use stars-and-bars to count the nonnegative integer solutions to $y_1+y_2+y_3+y_4=12-5k$.