The Sieve — elementary combinatorial applications

One powerful tool in the theory of enumeration as well as in prime number theory is the inclusion-exclusion principle (sieve of Erathosthenes). This relates the cardinality of the union of certain sets to  the cardinalities of the intersections of some of them, these latter cardinalities often being easier to handle. However, the formula does have some handicaps, it contains terms alternating in sign, and in general it has too many of them!

A natural setting for the sieve is in the language of probability theory. Of course, this only means a division by the cardinality of the underlying set, but it has the advantage that independence of occurring events can be defined. Situations in which events are almost independent are extremely important in number theory and also arise in certain combinatorial applications. Number theorists have developed ingenious methods to estimate the formula when the events (usually divisibility by certain primes) are almost independent. We give here the combinatorial background of some of these methods. Their actual use, however, rests upon complicated number theoretic considerations which are here illustrated only by two problems.

It should be emphasized that the sieve formula has many applications in quite different situations.

A beautiful general theory of inclusion-exclusion, usually referred to as the theory of the Mobius function is due to L. Weisner, P. Hall and G. C. Rota.

Question 1: In a high school class of 30 pupils, 12 pupils like mathematics, 14 like physics and 18 chemistry, 5 pupils like both mathematics and physics, 7 both physics and chemistry, 4 pupils like mathematics and chemistry. There are 3 who like all three subjects. How many pupils do not like any of them?

Question 2: (a) The Sieve Formula:

Let $A_{1}, \ldots, A_{n}$ be arbitrary events of a probability space $(\Omega, P)$. For each

$I \subseteq \{ 1, \ldots , n\}$, let

$A_{I}= \prod_{i\in I}A_{i}$, $A_{\phi}=\Omega$

and let $\sigma_{k}=\sum_{|I|=k}P(A_{I})$, $\sigma_{0}=1$

Then, $P(A_{1}+\ldots + A_{n})=\sum_{j=1}^{n}(-1)^{j-1}\sigma_{j}$

Question 2: (b) (Inclusion-Exclusion Formula)

Let $A_{1}, \ldots, A_{n} \subseteq S$, where S is a finite set, and let

$A_{I}=\bigcap_{ j \in J}A_{j}$, $A_{\phi}=S$. Then,

$|S-(A_{1}\cup \ldots \cup A_{n})|=\sum_{J \subset \{ 1, \ldots n\}}(-1)^{|I|}|A_{I}|$

Hints:

1) The number of pupils who like mathematics or physics is not $12+14$. By how much is 26 too  large?

2) Determine the contribution of any atom of the Boolean Algebra generated by $A_{1},, \ldots A_{n}$ on each side.

Solutions.

1) Let us subtract from 30 the number of pupils who like mathematics, physics, chemistry, respectively:

$30-12-14-13$.

This way, however, a student who likes both mathematics and physics is subtracted twice; so we have to add them back, and also for the other pairs of subjects:

$30-12-14-13+5+7+4$.

There is still trouble with those who like all three subjects. They were subtracted 3 times, but back 3 times, so we have to subtract them once more to get the result:

$30-12-14-13+5+7+4-3=4$/

2) (a) Let $B=A_{1}A_{2}\ldots A_{k}\overline A_{k+1}\ldots \overline A_{n}$

be any atom of the Boolean algebra generated by $A_{1}, A_{2}, \ldots A_{n}$ (with an appropriate choice of indices, every atom has such a form.) Every event in the formula is the union of certain (disjoint) atoms; let us express each $P(A_{I})$ and $P(A_{1}+A_{2}+\ldots +A_{n})$ as the sum of the probabilities of the corresponding atoms. We show that the probability of any given atom cancels out.

The coefficient of $P(B)$ on the left hand side is

$1, if k \neq 0$ and $0, if k=0$

B occurs in $A_{I}$ if $I \subseteq \{ 1, \ldots k\}$. so its coefficient on the right hand side is

$\sum_{j=1}^{k}\left( \begin{array}{c} k \\ j \end{array} \right) (-1)^{j}=1-(1-1)^{k}=1, k \neq 04, and$latex 0 if k =0\$.

Thus, $P(B)$ has the same coefficient on both sides, which proves part a.

Solution (b):

Choose an element x of S by a uniform distribution. Then, $A_{i}$ can be identified with the event that

$x \in A_{I}$, and we have

$P(A_{i})=\frac{|A_{i}|}{|S|}$

So, we have, by the above,

$P(A_{1}+A_{2}+\ldots + A_{n})=\sum_{j=1}^{n}(-1)^{j-1}\sum_{|I|=j}\frac{|A_{I}|}{|S|}$, where

$\sum_{\phi \neq I \subseteq \{ 1, \ldots n\} }(-1)^{|I|-1}\frac{A_{I}}{|S|}$, or equivalently

$P(\overline{A_{1}}\ldots \overline{A_{n}})=1-P(A_{1}+\ldots + A_{n})$, which in turn equals,

$1- \sum_{\phi \neq I \subseteq \{ 1, \ldots , n\}}(-1)^{|I|-1}\frac{|A|}{|S|}$

The assertion (b) follows on multiplying by $|S|$.

More later,

Nalin Pithwa

This site uses Akismet to reduce spam. Learn how your comment data is processed.