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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: