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

Introduction:

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 |

##### Counting problems
Content covered:
Counting problems
More Less
##### A student can choose a computer project from one of three lists. The t...

A student can choose a computer project from one of three lists. The three lists contain 23, 15, and 19 possible projects, respectively. No project is on more than one list. How many possible projects are there to choose from?

The student can choose a project by selecting a project from the first list, the second list, or the third list. Because no project is on more than one list, by the sum rule there are 23 + 15 + 19 = 57 ways to choose a project.
##### There are 32 microcomputers in a computer center. Each microcomputer h...
There are 32 microcomputers in a computer center. Each microcomputer has 24 ports. How many different ports to a microcomputer in the center are there?