# Questions relating to inclusion-exclusion principle

Today I came across the inclusion-exclusion principle for the first time. I believe I have understood it, however when I tried solving some questions on it, I got severely stuck. I couldn't solve any of them. Could you please suggest some questions of escalating difficulty, so that I can get a good grasp on the topic at hand? One of the questions is this one :inclusion-exclusion problem - sitting arrangement , It was in a Greek contest-math book and I also found it on this site.

The other question I couldn't find it on the internet, so I'll translate it:

Find the number of solutions to the equation $$x_1+x_2+x_3=100$$, if for every $$3\ge i\ge1$$, xi is a non negative integer with $$40\ge x_i$$.

I have found the solutions to both of these questions, the reason which I am posting them as well, is to give a better understanding to the reader of the post (as pointed out in the comments), of what level of questions in inclusion-exclusion principle are giving me difficulty

• Maybe it would be better if you would post the questions you did not succeed to solve, so we can see what kind of difficulties you have. – TheSilverDoe Aug 16 '20 at 16:47
• ok sure, I'll post some links to those which already exist in English, and I'll translate the others – user814992 Aug 16 '20 at 16:49
• within 5 minutes I'll have edited the post – user814992 Aug 16 '20 at 16:49
• The art of problem solving usually has good problems. – lulu Aug 16 '20 at 16:49

The second, translated, question doesn't really need inclusion-exclusion; it's quite easily done using stars and bars, which is another technique well worth learning (if you haven't already done so):

Let's write $$u_i=40-x_i$$, so that the restriction is $$u_i\ge0$$, and then rewrite the equation to solve as

$$u_1+u_2+u_3=20$$

(This comes from $$100=x_1+x_2+x_3=(40-u_1)+(40-u_2)+(40-u_3)=120-(u_1+u_2+u_3)$$, and then moving stuff around.) Stars and bars now says the number of non-negative triples summing to $$20$$ is

$${22\choose2}={22\cdot21\over2}=231$$

To be honest, I think I'd have a hard time solving this problem using inclusion-exclusion; I'd be interested myself in seeing if there's an easy way to do so.

• I added an inclusion-exclusion solution just now. – RobPratt Aug 23 '20 at 21:32

Here's the inclusion-exclusion approach for the second problem, where $$k$$ is the number of $$i\in\{1,2,3\}$$ with $$x_i \ge 41$$: \begin{align} \sum_{k=0}^2 (-1)^k \binom{3}{k} \binom{100-41k+3-1}{3-1}&=\binom{102}{2}-3\binom{61}{2}+3\binom{20}{2}\\&=5151-3 \cdot 1830+3 \cdot 190\\&=\color{red}{231}. \end{align} The $$\binom{100-41k+3-1}{3-1}$$ part comes from a stars-and-bars count of the nonnegative integer solutions to $$x_1+x_2+x_3=100$$ with $$x_i \ge 41$$ for $$k$$ specified $$i\in\{1,2,3\}$$, equivalently, the nonnegative integer solutions to $$y_1+y_2+y_3=100-41k$$.