Counting: Set Operations and the Pigeonhole Principle (9.3, 9.4)

Practice Problems

9.3 .- 8bcd, 19, 29efghj, 32, 34.

9.4 .-13, 28, 31.

Concepts

Addition rule

If and   are mutually disjoint sets, then:

Difference rule

If is a finite set and   is a subset of  , i.e   then:

Inclusion Exclusion Rule (for 2 sets)

If  and  are finite sets then:

Inclusion Exclusion Rule (for 3 sets)

If  and  are finite sets then:

The pigeonhole principle

A function from one set  to a smaller set  cannot be one-to-one. There must be two elements in  that have the same image in .

Called the pigeonhole principle because, if you were to have more pigeons than pigeonholes, then you are bound to have a hole with more than one pigeon in it.

Generalized Pigeonhole principle

Let  be a set of  elements,  be a set of  elements, and  be a function from  to  .  i.e .

For any integer ,  if   then there is some element  such that    is the image of at least  elements of  .

Generalized Pigeonhole principle (Contrapositive Form)

Let  be a set of  elements,  be a set of  elements, and  be a function from  to  .  i.e .

For any integer ,  if each element  has at most  elements of  mapping to it, then  has at most elements. In other words, .

.