# Determining number of solutions with inclusion-exclusion

NOTE: I know there are similar questions to this, but the ones on this website are much more complex, and I'd like to get a basic understanding before moving on to them. Please do not mark this as a duplicate.

On a practice quiz:

Use inc-exc to determine the number of solutions to $a+b+c+d = 15$ with $0 \leq a,b,c,d \leq 6$

## Here's what I have so far:

Let $A_1$ be the solution to $a+b+c+d=15$ with $a\geq 7, 0\leq b,c,d$

Let $A_2$ be the solution to $a+b+c+d=15$ with $b\geq 7, 0\leq a,c,d$

Let $A_3$ be the solution to $a+b+c+d=15$ with $c\geq 7, 0\leq a,b,d$

Let $A_4$ be the solution to $a+b+c+d=15$ with $d\geq 7, 0\leq a,b,c$

$|A_1 \cup A_2 \cup A_3 \cup A_4| = C(4,1) \cdot C((4+4-1), 4) - \dotsb$

And this is where I get stuck. I found my first term using the logic that I want to count $|A_1|+|A_2|+|A_3|+|A_4|$. How do I continue this to find the rest of the terms? I know what to do after I find the number of non-solutions, just subtract it from the total non-restricted solutions...but I can't figure out how to find the number of non-solutions!

Any help would be greatly appreciated, thanks.

-
How many solutions have $a \geq 7$ and $b \geq 7$. We have to over-include if we're going to use inclusion-exclusion. – Eric Towers Mar 13 '14 at 3:41
@EricTowers Right...that's what I need help figuring out... – user134788 Mar 13 '14 at 3:44
@EricTowers How can I solve for that? – user134788 Mar 13 '14 at 3:44
Start with: Home many solutions have $a\geq 7$, $b \geq 7$, $c \geq 7$, and $d \geq 7$? – Eric Towers Mar 13 '14 at 3:46
@EricTowers 0 solutions. I'm still not getting it though. Some help would be appreciated...completely stuck here and I have nowhere else to turn. – user134788 Mar 13 '14 at 3:58

Generating Functions

Look at the coefficient of $x^{15}$ in $\left(1+x+x^2+x^3+\dots+x^6\right)^4$: \begin{align} \left(\frac{1-x^7}{1-x}\right)^4 &=\sum_{j=0}^4(-1)^j\binom{4}{j}x^{7j}\sum_{k=0}^\infty(-1)^k\binom{-4}{k}x^k\\ &=\sum_{j=0}^4(-1)^j\binom{4}{j}x^{7j}\sum_{k=0}^\infty\binom{k+3}{k}x^k \end{align} which is $$\sum_{j=0}^2(-1)^j\binom{4}{j}\binom{18-7j}{3}=180$$

Inclusion-Exclusion

Without restriction on the size of the terms, using the standard $\mid$ and $\circ$ argument ($15$ $\circ$s and $3$ $\mid$s), there are $\binom{15+3}{3}$ ways to choose 4 non-negative integers that sum to $15$. $$\text{one sum for each arrangement}\\ 2+4+6+3=\circ\,\circ\mid \circ\circ\circ\,\circ\mid \circ\circ\circ\circ\circ\,\circ\mid \circ\circ\circ$$ Now let's count how many ways there are to have terms greater than $6$. There are $\binom{4}{1}$ ways to choose which $1$ term should be greater than $6$. To count the number of sums with $1$ term at least $7$, that would be $\binom{15-7+3}{3}$. $$\text{consider the red group atomic}\\ 2+8+4+1=\circ\,\circ\mid\color{#C00000}{\circ\circ\circ\circ\circ\circ\circ}\,\circ\mid\circ\circ\circ\,\circ\mid\circ$$ There are $\binom{4}{2}$ ways to choose which $2$ terms should be greater than $6$. To count the number of sums with $2$ terms at least $7$, that would be $\binom{15-14+3}{3}$. $$7+0+7+1=\color{#C00000}{\circ\circ\circ\circ\circ\circ\,\circ}\mid\mid\color{#C00000}{\circ\circ\circ\circ\circ\circ\circ}\mid\circ$$ There is no way for $3$ terms to be greater than $6$. Inclusion-Exclusion says there are $$\binom{18}{3}-\binom{4}{1}\binom{11}{3}+\binom{4}{2}\binom{4}{3}=180$$ ways for $4$ terms to sum to $15$ with each term at most $6$.

-
This is awesome thank you!!! On the answer key it reads that the # non solutions is: $\binom{4}{1} \cdot \binom{8+4-1}{8} - \binom {4}{2} \cdot \binom {1+4-1}{4}$ These are equivalent, but would you be able to explain the reasoning behind the difference? – user134788 Mar 13 '14 at 17:48
@user134788: $\binom{11}{8}=\binom{11}{3}$ and $\binom{4}{1}=\binom{4}{3}$. Are you sure it is $\binom{1+4-1}{4}$ and not $\binom{1+4-1}{1}$? – robjohn Mar 13 '14 at 18:02
Positive, that's what my prof emailed me. Not saying you're wrong I'm just trying to understand how they are equivalent logically. I get why they're equivalent numerically. – user134788 Mar 13 '14 at 18:09
actually scratch that, they come out to different numbers. My professor's solution comes out to 654 total non-solutions, while yours comes out to 636 total non-solutions. – user134788 Mar 13 '14 at 18:12
@user134788: without seeing your prof's reasoning, I can't say why we get different answers. Since both of my approaches give the same result (and the same sums), I am pretty sure that my answer is correct. Does your prof get a different final answer? – robjohn Mar 13 '14 at 18:35