Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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 at 3:41
    
@EricTowers Right...that's what I need help figuring out... –  user134788 Mar 13 at 3:44
    
@EricTowers How can I solve for that? –  user134788 Mar 13 at 3:44
1  
Start with: Home many solutions have $a\geq 7$, $b \geq 7$, $c \geq 7$, and $d \geq 7$? –  Eric Towers Mar 13 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 at 3:58

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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 at 17:48
1  
@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 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 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 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 at 18:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.