2
$\begingroup$

Find the number of solutions to the equation $x_1+x_2+x_3+x_4=19$ with $0\leq x_i\leq 8$.

I know that I should use inclusion-exclusion, but I don't quite see why.

If I had this problem:

Find the number of solutions to the equation $x_1+x_2+...+x_5=10$ with no restrictions to $x_i$:

The solution to this would be $14 \choose 10$ (like a stars-bars problem).

Back to the first problem, I see why can't use that... Let's say I want to solve something equivalent such as:

$(x_1+8)+(x_2+8)+(x_3+8)+(x_4+8)=19$ with no restrictions to $x_i$.

That would be $x_1+x_2+x_3+x_4=-13$ which doesn't make sense as I'm working with natural numbers.

Can someone explain me why inclusion-exclusion applies to this? I understand the theorem but I don't get why I should use it on this.

$\endgroup$
  • $\begingroup$ Have you considered using generating functions? Like here, here or here. $\endgroup$ – rtybase Aug 16 at 22:14
  • $\begingroup$ @rtybase I can't really use it since i'm not there yet at my discrete math course :/ $\endgroup$ – Moria Aug 16 at 22:16
1
$\begingroup$

The stars and bars strategy is a good start, but it leaves you with solutions you don't want like $19+0+0+0=19$. So then you use I/E to subtract out solutions where $x_1>8$, which is just like $(y_i+8)+x_2+y_2+z_2=19$, but of course there are more cases than that, and then you have to add back in solutions where two variables are greater than eight yadda yadda yadda. ^_^

$\endgroup$
3
$\begingroup$

Hint: Let $A_i$ be a set of all $(x_1,x_2,x_3,x_4)$ such that $x_i\geq 9$. Then use a PIE.

$\endgroup$
1
$\begingroup$

One can apply a generating function approach $$ \begin{align} \left[x^{19}\right]\left(1+x+\dots+x^8\right)^4 &=\left[x^{19}\right]\left(\frac{1-x^9}{1-x}\right)^4\\ &=\left[x^{19}\right]\left(1-x^9\right)^4\sum_{k=0}^\infty(-1)^k\binom{-4}{k}x^k\\ &=\left[x^{19}\right]\left(1-4x^9+6x^{18}-4x^{27}+x^{36}\right)\sum_{k=0}^\infty\binom{k+3}{3}x^k\\ &=\binom{22}{3}-4\binom{13}{3}+6\binom{4}{3}\\[9pt] &=420 \end{align} $$ Note that the last two lines are same as in an answer using stars-and-bars and inclusion-exclusion.

$\endgroup$
  • $\begingroup$ I just saw the comment that you haven't gotten to generating functions yet, but I will leave this for completeness and for those who can use generating functions. $\endgroup$ – robjohn Aug 17 at 12:42
  • $\begingroup$ Thank you! I'll later have to use generating functions on this type of problems so this will come handy:-) $\endgroup$ – Moria Aug 18 at 0:24

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.