[Discrete Mathematics] Counting

1. Basics of Counting

A wide variety of counting problems will be introduces in this section

The Product Rule
Suppose that a procedure can be broken down into a sequence of two tasks. If there are $n_1$ ways to do the first task and for each of these ways of doing the first task, there are $n_2$ ways to do the second task, then there are $n_1n_2$ ways to do the procedure.

The Sum Rule
If a task can be done either in one of $n_1$ ways or in one of $n_2$ ways, where none of the set of $n_1$ ways is the same as any of the set of $n_2$ ways, then there are $n_1 + n_2$ ways to do the task.

1.4 Substracting Rule (Inclusion-Exclusion for Two Sets)

The Subtraction Rule
If a task can be done in either $n_1$ ways or $n_2$ ways, then the number of ways to do the task is $n_1 + n_2$ minus the number of ways to do the task that are common to the two different ways.

1.5 The Division Rule

The Division Rule
There are $n/d$ ways to do a task if it can be done using a procedure that can be carried out in $n$ ways, and for every way $w$, exactly $d$ of the $n$ ways correspond to way $w$.

2. The Pigeonhole Principle

[Theorem 1] The Pigeonhole Principle
If $k$ is a positive integer and $k+1$ or more objects are placed into $k$ boxes, then there is at least on box containing two or more of the objects.

3. Permutations and Combinations

4. Binomial Coefficient

5. Generalized Permutations and Combinations

6. Generating Permutations and Combinations

Reference

Kenneth H. Rosen - Discrete Mathematics and Its Applications : Chapter 06