Htykuut

In my notes I have the following as an example for counting by inclusion exclusion.

Let S be a set. Let $c_i(x)$ where $i=1,2,3,4....k$, be a statement that is either true or false for $x in S$.

Denote $N(c_i)= |space {x in S| c_i(x)(is space true)}space|$

$N(c_ic_j)= |space {x in S| c_i(x) wedge}c_j(x)space |$

Then the number of elements of S that satisfy none of $c_1,c_2,c_3.....c_k$
is given by $|S|- sum_{1le ile k}N(c_i) + sum_{1le ile j le k}N(c_ic_j) - sum_{1le ile j le l le k}N(c_ic_jc_l) +........+(-1)^kN(c_1c_2c_3c_4......c_k)$

I am familiar enough with the Exclusion-Inclusion principle that I can express by understanding of it through a simple Venn diagram to convey how overcounting is being corrected. I honestly have no idea whatsoever what is happening in the above example. If someone could translate this into English I would greatly appreciate it. I've been at this for about an hour now so I am looking for a simple and really dumbed down explanation of what's going on.

The following is a somewhat more concrete statement of the principle, copied verbatim from Notes on Introductory Combinatorics by George Polya, Robert E. Tarjan and Donald R. Woods. I personally find this version very useful in actual applications.

"Suppose we have a set of $N$ objects that have various properties $alpha, beta, gamma, dots , lambda$. Each of the objects may have any or none of the properties. Let $N_alpha$ be the number of objects that have property $alpha$. Some of these objects may have other properties in addition to property $alpha$; that doesn't matter. (In fact, that's the whole idea!) Similarly, let $N_beta$ be the number of objects that have property $beta$, and so on. Let $N_{alpha beta}$ be the number of objects that have both property $alpha$ and property $beta$, $N_{alpha gamma}$ be the number that have properties $alpha$ and $gamma$, etc. $N_{alpha beta gamma dots lambda}$ is the number of objects with all the properties. Given this information, we want to find $N_0$, the number of objects that have none of the properties."

"The general formula for computing this is called the Principle of Inclusion and Exclusion (or sometimes PIE for short), and is the following:
$$begin{align}
N_0 = N &- N_alpha - N_beta - N_gamma - dots - N_lambda \
&+ N_{alpha beta} + N_{alpha gamma} + N_{beta gamma} + dots + N_{kappa lambda} \
&- N_{alpha beta gamma} - N_{alpha beta delta} - dots \
& vdots \
& pm N_{alpha beta gamma dots lambda}
end{align}$$

End of quotation.

In actual practice, I might add, the trickiest part may be formulating the problem to fit into this framework. Note that PIE requires that your final answer be the number of objects that have none of the properties. This forces you to "think negatively".