Counting | Basic Counting Principles | Product rule | Sum rule | Principle of Inclusion-Exclusion


Counting problems arise throughout mathematics and computer science. For example, we must count the successful outcomes of experiments and all the possible outcomes of these experiments to determine probabilities of discrete events. We need to count the number of operations used by an algorithm to study its time complexity.  

Basic Counting Principles:  

We first learn two basic counting principles, the product rule and the sum rule.  

Product rule:

Suppose that a procedure can be broken down into a sequence of two tasks. If there are n1 ways to do the first task and for each of these ways of doing the first task, there are n2 ways to do the second task, then there are n1n2 ways to do the procedure.  

Sum rule:

If a task can be done either in one of n1 ways or in one of n2 ways, where none of the set of n1 ways is the same as any of the set of n2 ways, then there are n1 +n2 ways to do the task.  

Principle of Inclusion-Exclusion:

The principle of inclusion-exclusion says that in order to count only unique ways of doing a task, we must add the number of ways to do it in one way and the number of ways to do it in another and then subtract the number of ways to do the task that are common to both sets of ways.

The principle of inclusion-exclusion is also known as the subtraction principle.  

For two sets of ways A1 and A2, the enumeration would like-

| A1 U A2 | = | A1 | + | A2 | - |A1 ∩ A2 |