Permutations & Combinations


Permutations

Suppose that distinct objects are drawn sequentially, ordered from left to right in row. Keep in mind that order matters and that objects are drawn without replacement, that is, the pool of objects to be drawn from decreases with each selection.

  1. The number of ways to arrange distinct objects in a row is

    where the symbol is described as “factorial”.

    For example, consider three numbered balls; They can be arranged different ways.

    image

  2. The number of ways to arrange objects selected from distinct objects is

    where the notation describes “n taken to r terms”. An alternative expression for this is

    For example, consider again three numbered balls; Two balls can be arranged different ways.

image



Combinations

Suppose that order does not matter and as before, objects are drawn without replacement.

Now, the number of ways to choose objects from n distinct objects is

where the symbol is “n choose r”.

Proof From permutations rule 2, recall that the ways we can arrange objects from objects is . Any choice of objects can be ordered different ways. It follows that

Concretely, the image below is nearly identical to the example for permutations rule 2 except that, since order is ignored, we group those with identical elements with a dotted box, leaving three events rather than the previous six

image