Counting

Fundamental Counting Rule

In a sequence of $n$ events in which the first one has $k_1$ possibilities, and the second event has $k_2$ possibilities, and the third has $k_3$, and so forth, the total number of possibilities of the sequence will be $$k_1 \cdot k_2 \cdot k_3 \cdots k_n$$

As an example, suppose we want to count the number of possibilities resulting from flipping a coin, rolling a single die, and picking a prime number between 1 and 10. There are 2 possible ways to flip a coin (heads and tails), there are 6 possible rolls of a single die (1,2,3,4,5, and 6), and there are 4 primes between 1 and 10. Thus, there are $2 \cdot 6 \cdot 4 = 48$ possibilities for the result of doing all three of these actions.

Factorial

We will often encounter the product of $n$ consecutive integers in calculating counts and probabilities. To this end, we define the factorial of $n$ to be $$n! = n \cdot (n-1) \cdot (n-2) \cdots 3 \cdot 2 \cdot 1 \quad \textrm{ and } \quad 0! = 1$$

For example, $4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$.

Permuatations

The number of ways to arrange $k$ objects from a set of $n$ objects is given by $${}_nP_r = \frac{n!}{(n-k)!}$$ Note that, since we are talking about arrangements, order matters. Also, the objects in question are not reused.

As an example, $${}_7P_4 = \frac{7!}{3!} = \frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{3 \cdot 2 \cdot 1} = 7 \cdot 6 \cdot 5 \cdot 4$$

Permutations Involving Identical Objects

Suppose we have a group of $n$ objects that fall into $k$ groups, where the elements of any one group are indistinguishable from each other, but distinguishable from the elements of any other group. If the numbers of objects in these groups are given by $n_1, n_2, \ldots n_k$, then the number of ways to arrange these $n$ objects is given by $$\frac{n!}{n_1! n_2! \cdots n_k!}$$

As an example, one can arrange the letters of the word MISSISSIPPI in $$\frac{11!}{1!4!4!2!} = 34650 \textrm{ ways}$$

Combinations

The number of ways to choose $k$ objects from a set of $n$ objects is given by $${}_nC_r = \frac{n!}{k!(n-k)!}$$ Note that, since we are simply choosing objects from this group (thus forming a subset), and not arranging these objects in any way -- order does not matter. Also, objects are not reused.

As an example, the number of ways to choose 4 people to serve on a committee out of a group of 8 people, is given by $${}_8C_4 = \frac{8!}{4!4!} = 70$$