The Inclusion-Exclusion Principle

In this section we assume that all sets under consideration are finite.

If we have two finite sets and , how big is ? Show by example that it is not always the true that . What is the correct formula for ? \

If we have three finite sets , find a formula for . \

If we have four finite sets , find a formula for . \

Try to extend to k finite sets . \

This is an example of the Inclusion-Exclusion principle.

Perhaps this will help to understand the following argument from Kenneth P. Bogart in Introductory Combinatorics, pp. 64-65:

Find a formula for the number of functions from an m-element set onto a n-element set.

If, for example, , then there is one function from X to Y and it is onto. If , there are ????? functions from X to Y. Of these, one skips because it maps to , and one skips because it maps to . Thus there are ????? functions from X onto Y.

Now if , there are ????? functions from X to Y. Of these, ????? functions skip because they map into . In fact, for each of the sets , there are ????? functions that skip the element of . However, the difference

 

is smaller than the number of onto functions because some functions that skip skip as well, and thus are subtracted twice. In fact, each of the ????? sets is skipped by exactly one function. Thus we have subtracted too many functions in the difference (1). The number of functions from X onto Y is then

 

The same kind of argument with gives the following. There are ????? functions from X to Y. These functions could skip 1, 2, or 3 (but not all 4) elements of Y. The number skipping each of the ????? sets is ?????. In the difference , we subtract the functions that skip each of the ????? two-element sets at least twice. Let us examine the quantity

 

The functions that skip exactly one element are excluded from the quantity exactly once. The functions that skip exactly two elements are excluded from the quantity twice, but are included back in the term exactly once, and so are excluded exactly once by the quantity in (3). However, the functions that skip the three-element set are excluded three times in the negative term and are included three times (once for each two-element subset of ) in the term . Thus they have yet to be excluded from the sum. Only functions that skip three elements have yet to be taken care of; there are ????? such functions still to be excluded. Thus we have

 

functions from an m-element set onto a four-element set. Formulas (2) and (4) suggest immediately that the number of functions from an m-element set onto a n-element set is ?????