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