[Common Math 1 Part 22] Permutations and Combinations

In the previous post, we emphasized that counting begins by deciding what makes cases different. In this post, we focus on one important standard: order.

Learn factorials, permutations, and combinations, and distinguish between ordered selections and unordered selections.

The key ideas are:

• $n!$ counts the ways to arrange $n$ distinct objects in a line.
• A permutation is a selection where order matters.
• A combination is a selection where order does not matter.
• The combination formula comes from dividing out repeated counting in permutations.
• After understanding the mathematics, we can generate actual arrays with Python.

1. Factorial

Before permutations and combinations, we need factorial notation.

means the product of all natural numbers from $n$ down to 1.

For example,

Also,

We define $0!=1$ because it makes many counting formulas work consistently. It also means that there is exactly one way to choose or arrange nothing: do nothing.

2. Arranging all objects

Suppose we arrange A, B, C in a line.

For the first position, there are 3 choices. After one is chosen, 2 remain. For the last position, 1 remains.

So the number of arrangements is

The actual arrangements are:

In general, the number of ways to arrange $n$ distinct objects in a line is

3. Permutations: order matters

Now suppose we choose 2 objects from A, B, C and arrange them in order.

For the first position, there are 3 choices. For the second position, there are 2 remaining choices.

So the number is

The actual ordered arrays are:

Here $AB$ and $BA$ are different because order matters.

The number of ways to choose $r$ objects from $n$ distinct objects and arrange them in order is written as

and the formula is

4. Why the permutation formula works

The formula comes directly from the product rule.

When we fill $r$ positions:

• 1st position: $n$ choices
• 2nd position: $n-1$ choices
• 3rd position: $n-2$ choices
• ...
• $r$th position: $n-r+1$ choices

Therefore,

This is the same as

because the unused factors cancel.

For example,

5. A recurrence view of permutations

A permutation can also be generated from smaller permutations.

To make an ordered array of length $r$:

1. choose the first element;
2. generate an ordered array of length $r-1$ from the remaining elements;
3. attach the first element in front.

Symbolically,

This is not just a formula. It describes how lists are actually generated.

6. Combinations: order does not matter

Now suppose we choose 2 objects from A, B, C, but order does not matter.

Then $AB$ and $BA$ represent the same selection. The possible selections are:

There are 3 cases.

The number of ways to choose $r$ objects from $n$ distinct objects without considering order is written as

7. Why the combination formula works

First count as if order matters. That gives

But each unordered group of $r$ objects has been counted $r!$ times, because the same selected objects can be arranged in $r!$ orders.

Therefore,

Using the permutation formula,

For example,

8. A recurrence view of combinations

Combinations can be built by asking whether the first element is included.

For a fixed element A, every selection falls into one of two groups.

1. Selections that include A
2. Selections that do not include A

If A is included, we choose the remaining $r-1$ objects from the other $n-1$ objects. If A is not included, we choose all $r$ objects from the other $n-1$ objects.

So

This is Pascal's identity.

9. Important properties of combinations

Symmetry

Choosing $r$ objects to include is the same as choosing $n-r$ objects to exclude.

For example,

Edge cases

There is exactly one way to choose nothing, and exactly one way to choose everything.

10. Math first, code later

The code below generates actual arrays, not just counts.

def permutations(items, r):
    if r == 0:
        return [[]]

    result = []
    for i, item in enumerate(items):
        rest = items[:i] + items[i+1:]
        for tail in permutations(rest, r - 1):
            result.append([item] + tail)
    return result

print(permutations(['A', 'B', 'C'], 2))
print(len(permutations(['A', 'B', 'C'], 2)))

def combinations(items, r):
    if r == 0:
        return [[]]
    if not items:
        return []

    first = items[0]
    rest = items[1:]

    with_first = [[first] + tail for tail in combinations(rest, r - 1)]
    without_first = combinations(rest, r)
    return with_first + without_first

print(combinations(['A', 'B', 'C'], 2))
print(len(combinations(['A', 'B', 'C'], 2)))

11. Summary

• $n!$ counts the ways to arrange all $n$ distinct objects.
• ${}_nP_r$ counts ordered selections.
• ${}_nP_r=\dfrac{n!}{(n-r)!}$
• ${}_nC_r$ counts unordered selections.
• ${}_nC_r=\dfrac{n!}{r!(n-r)!}$
• Combinations can be understood by dividing ordered cases by $r!$.
• Recurrence relations show how the arrays themselves can be generated.