Combinatorics

Basic Counting Principles §

The Product rule §

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

The Sum Rule §

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

The Subtraction Rule / Principle of inclusion–exclusion §

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

The Division Rule §

There are ways to do a task if it can be done using a procedure that can be carried out in ways, and for every way , exactly of the ways correspond to way .

The Pigeonhole Principle §

If is a positive integer and or more objects are placed into boxes, then there is at least one box containing two or more of the objects.

The Generalized Pigeonhole Principle §

If objects are placed into boxes, then there is at least one box containing at least objects.

Combinations §

The combination is selection of elements without repetition from a collection when order doesn’t matter.

Without repetition:

Also:

With repetition:

Permutations §

A permutation is a mathematical technique that determines the number of possible arrangements in a set when the order of the arrangements matters.

With repetition:

Without repetition, using all elements:

is the notation of n factorial.

Without repetition, using some () elements: