Introduction

In this unit, we continue our discussion of the previous unit on combinatorial techniques. We particularly focus on two principles of counting – the pigeonhole principle and the principle of inclusion-exclusion.

Then, you will see how obvious the pigeonhole principle is. Its proof is very simple, and amazingly, it has several useful applications. We shall also include some of these in this section

Then, we focus on the principle (or formula) of inclusion-exclusion. As you will see, this principle tells us how many elements do not fit into any of n categories. We prove this result and also give a generalisation. Following this,  we give several important applications of inclusion-exclusion. 

Objectives

After studying this unit, you should be able to:

• prove the pigeonhole principle, and state the generalised pigeonhole principle;
• identify situations in which these principles apply, and solve related problems;
• prove the principle of inclusion-exclusion;
• apply inclusion-exclusion for counting the number of surjective functions, derangements and for finding discrete probability.