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 anm-element set onto an-element set.If, for example, , then there is one function from

XtoYand it is onto. If , there are ????? functions fromXtoY. Of these, one skips because it maps to , and one skips because it maps to . Thus there are ????? functions fromXontoY.Now if , there are ????? functions from

XtoY. 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 differenceis 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

XontoYis thenThe same kind of argument with gives the following. There are ????? functions from

XtoY. These functions could skip 1, 2, or 3 (but not all 4) elements ofY. 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 quantityThe 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 anm-element set onto an-element set is ?????

Wed Sep 30 08:36:10 EDT 1998