0
$\begingroup$

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_{1\le i\le k}N(c_i) + \sum_{1\le i\le j \le k}N(c_ic_j) - \sum_{1\le i\le 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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What does N denote here? The number of all possible objects? Could you give a concrete example of this? $\endgroup$ – user140161 Nov 24 '18 at 19:03
  • $\begingroup$ @user140161 Yes, $N$ is the number of all objects. One of my solutions using PIE is math.stackexchange.com/questions/2032110/…. Another is math.stackexchange.com/questions/2879280/… $\endgroup$ – awkward Nov 24 '18 at 20:23
  • $\begingroup$ I think I get it now. So for example if you have sets ABC in a universe U, then what we are really doing is counting ABC by PIE, and then subtracting that from U to calculate $(ABC)^c$. It's kind of like a complement version of PIE $\endgroup$ – user140161 Nov 24 '18 at 20:46
  • $\begingroup$ I think the only confusion I have left is why the last term has $(-1)^k$ $\endgroup$ – user140161 Nov 24 '18 at 20:47
  • $\begingroup$ @user140161 Suppose you have two sets $A$ and $B$; then $|A \cup B| = |A| + |B| - |A \cap B|$. If you add the sizes of two sets together, you've counted the stuff in their intersection twice, so you have to subtract it out. PIE is just the generalization to more than two sets. $\endgroup$ – awkward Nov 25 '18 at 12:50

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.