Principle of Inclusion and Exclusion

The purpose of this post is to record a small observation about the Principle of Inclusion and Exclusion that I haven’t seen before, but I’m sure must be well known.

Take the usual setup of a finite set X containing subsets A_1, A_2, \ldots, A_n. Let C = X \backslash (A_1 \cup A_2 \cup \cdots \cup A_n). The inclusion-exclusion formula states that

| C | = \sum_{I \subseteq \{1,2,\ldots, n\}} (-1)^{|I|} |A_I|

where A_I = \bigcap_{i \in I} A_i.

Suppose that we truncate the sum in the inclusion-exclusion formula so that we only sum over sets I of size at most r. If c_r denote the resulting integer then

c_r \le c_{r+2} \le \cdots \le |C| \le \cdots \le c_{r+1} \le c_{r-1}

for all odd r \ge n/2. Thus the c_r eventually provide successively better approximations to |C| = c_n.

This result can be proved quite easily by adapting one of the standard proofs of the inclusion-exclusion formula. Let

f_r(x) = \sum_I (-1)^{|I|} \mathbf{1}_{A_I}(x)

where the sum is over all I \subseteq \{1,2,\ldots, n\} of size at most r and \mathbf{1}_{A_I} is the indicator function of the set A_I. Let x \in X. If x belongs to at most r of the sets A_1, A_2, \ldots, A_r then, as in the standard proof, f_r(x) = 1 if x \in C and f_r(x) = 0 otherwise. Suppose that x belongs to exactly s > r of the sets. Then

f_r(x) = \sum_{k=0}^r (-1)^k \binom{s}{k} = (-1)^r \binom{s-1}{r}.

Let x_s be the number of elements of X which belong to exactly s of the sets A_1, A_2, \ldots, A_n. We have

c_r = |C| + (-1)^r e_r

where

e_r = \sum_{s > r} \binom{s-1}{r} x_s

The difference between successive error terms is

e_{r-1} - e_r = \sum_{s > r} \bigl( \binom{s-1}{r-1} - \binom{s-1}{r} \bigr) x_s + \binom{r-1}{r-1} x_r.

Since

\binom{s-1}{r-1} - \binom{s-1}{r} = \binom{s-1}{r-1} \bigl( 1 - \frac{s-r}{r} \bigr) = \binom{s-1}{r-1} \frac{2r-s}{r}

this shows that the error terms e_r are decreasing for r \ge n/2.

Advertisements

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: