দেওয়া-নেওয়া / গ্রহণ-বর্জন (ইনক্লুশন-এক্সক্লুশন) নীতি

The Principle of Inclusion-Exclusion (PIE) is a theorem that allows one to calculate the number of elements in a union of multiple finite sets.

First, consider two sets, $A$ and $B$. PIE states that: $$|A \cup B| = |A| + |B| - |A \cap B|$$ where $|S|$ denotes the cardinality of a set $S$ (the cardinality of a set is the number of elements in the set).

Why does this work? Well, the union of $A$ and $B$ can be thought of in terms of $3$ different regions: the elements in $A$ and not in $B$, the elements in $B$ and not in $A$, and the elements in both $A$ and $B$. (These regions can be seen very clearly in a Venn diagram.)

As an example, take the elements in both $A$ and $B$. When one adds $|A|$ and $|B|$, these elements are counted twice; however, when $|A \cap B|$ is subtracted, these elements are removed once, so they are counted a total of once, as desired. Similarly, one can check that the elements in the other two regions are also counted exactly once each.

Now, consider three sets: $A$, $B$, and $C$. PIE states that: $$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|.$$

Consider the region containing elements in all $3$ sets. The first three terms count these elements $3$ times; the second three terms subtract these elements $3$ times; and the last term adds these elements once. In total, they are counted $3 - 3 + 1 = 1$ time, as desired. (One can check that the same holds for the other $6$ regions of the union of $A, B,$ and $C$.

PIE can be extended to any finite number of finite sets. To compute the cardinality of the union of $n$ finite sets:

1. Add the cardinalities of the sets.

2. Subtract the cardinalities of the pairwise intersections.

3. Add the cardinalities of the triple-wise intersections.

4. Subtract the cardinalities of the quadruple-wise intersections.

5. Continue, until the cardinality of the $n$-tuple-wise intersection is added (if $n$ is odd) or subtracted ($n$ even).

This can be written in terms of an equation, but it tends to be easier to understand the method explained above rather than the equation.

The union of $n$ sets has $2^n - 1$ regions. Consider a region that contains the elements from exactly $k$ of the $n$ sets, where $k$ is an integer from $1$ to $n$. Then, the first step counts these elements $k = {k\choose 1}$ times. The second step excludes these elements ${k\choose 2}$ times. This continues, until, on the $k$th step, the elements are included (if $k$ is odd) or excluded (if $k$ is even) exactly $1 = {k\choose k}$ time. Therefore, the number of times the elements are included (denoted $N$) is: $$N = {k\choose 1} - {k\choose 2} + {k\choose 3} - {k\choose 4} + ... + (-1)^{k-1} {k\choose k}$$ $$N = 1 - (1-1)^k$$ $$N = 1$$ where the second step follows from the Binomial Theorem. Thus, every element is counted exactly once, as desired!

Here, rather than give a standard exercise or practice problem, I will explore some implications that PIE yields for positive real numbers.

We first recall what PIE is:

$|A_1 \cup A_2 \cup ... \cup A_n|$ is equal to

$\displaystyle\sum_{i=1}^n |A_i| - \displaystyle\sum_{i,j=1, i \neq j}^n |A_i \cap A_j| + \displaystyle\sum_{i,j,k=1, i \neq j \neq k \neq i}^n |A_i \cap A_j \cap A_k| - ...$

and so on until we reach the final term, which is

$(-1)^{n-1}|A_1 \cap A_2 \cap ... \cap A_n|$.

Now, let's translate this into the language positive real numbers.

For each $r_i \ge 0$, define $R_i$ to be the interval set of a given $r_i$. (Ok, I am just making this terminology up at this point as it is mostly original.)

What is this interval set to be exact? Let $\epsilon$ be a small positive number. We define

$R_i = [ \epsilon, 2\epsilon, .. n\epsilon]$ where $n$ is the positive integer such that

$n\epsilon \le r_i < (n+1)\epsilon$

Now, the main idea is this- for regular sets, we define the magnitude of $R_i$, denoted $|R_i|$, to be the number of elements in $R_i$- in this case, it is the $n$ mentioned previously.

Here, we will denote the special magnitude of $R_i$ by $|R_i|$ so as to not confuse it with the regular magnitude, and we will set

$|R_i| = |R_i| \cdot \epsilon$

Thus we see that as $\epsilon$ becomes arbitrarily small, $|R_i| = r_i$.

Now, we can do some really cool things with these sets $R_i$.

When first introduced to the new notation, this may seem like a difficult question.

However, WLOG let $r_i \ge r_j$. Then we see that $R_i$ actually completely includes $R_j$, since for each positive integer $n$ the statements $n\epsilon \le r_j$ and $n\epsilon \in R_j$ are equivalent.

But note that the first statement also means that $n\epsilon \le r_i$ so that $n\epsilon \in R_i$, so we easily see that $R_j$ is included in $R_i$ and then $|R_i \cap R_j| = |R_j| = r_j$

This is a very important fact: In general, it tells us that for $m$ interval sets $R_1, R_2, R_3, .. R_m$ that

$| R_1 \cap R_2 \cap ... \cap R_m| = \min (r_1, r_2, ... r_m)$.

As expected, (and this is easy to prove), we know that

$|R_1 \cup R_2 \cup .. \cup R_m| = \max ( r_1, r_2, ... r_m)$.

Now that we know these two formulas, let's take any $n$ positive reals $r_1, r_2, ... r_n$. We'll let their interval sets be $R_1, R_2, ... R_n$ as usual and we'll plug the two formulas into our PIE formula.

We obtain that

$\max (r_1, r_2, .. r_n)$ is equal to $$\displaystyle\sum_{i=1}^n r_i - \displaystyle\sum_{i,j=1, i \neq j}^n \min (r_i, r_j) + \displaystyle\sum_{i,j,k=1, i \neq j \neq k \neq i}^n \min (r_i, r_j, r_k) - ...$$

and ending in $(-1)^{n-1} \min (r_1, r_2, ... r_n)$.

This is clearly a generalization of the trivial

$r_1 + r_2 = \max (r_1, r_2) + \min (r_1, r_2)$.

Hopefully this post showed you how occasionally, one can change certain sets with certain positive numbers to deduce, not necessarily new, but nontrivial or non-obvious results, and we have used PIE as an example.