Permutation and Combination
Basic

Video tutorial

Lecture Notes

Whether or not order matters is an important detail:

- If order matters, it is a
__permutation__problem - Otherwise, if order does not matter, it is a
__combination__problem

Formulas:

- Permutation: $P_n^k=n\times (n-1)\times\cdots\times (n-k+1)$
- In particular: $P_n^n = n \times (n-1)\times\cdots\times 2\times 1$

- Combination: $C_n^k={n\choose k}=\frac{P_n^k}{P_k^k}=\frac{n\times (n-1)\times\cdot\times (n-k+1)}{k\times (k-1)\times\cdots\times 1}$

**Tip**: Whether order does or does not matter may be inferred from whether the objects are distinguishable. If the objects are indistinguishable, then the order usually does not matter. For example, if a problem mentioned "$4$ red balls" these balls can usually be assumed to be identical, which means the problem is a combination problem. If a problem metioned "$4$ people", then we need to clarification from the context of the problem to whether these people are identical and whether this problem is a combination or permutation problem.

**Tip**: The denominator, $P_k^k$, in the combination formula accounts for the duplicates. This is because there are this number of "duplicated" cases, i.e. they are treated as the same because order does not matter within this $k$-object group. Accounting for duplicated cases is useful especially when not all objects are distinguishable (e.g. line up $3$ red and $4$ green balls). We will see some examples later involving this technique.

Comments

"**Using two different approaches to count the same problem**" is an advanced technique to prove some combinatorics identities. It will be discussed in the course 25 - Advanced Combinatorics. As a preview, the combination formula can be intepreted with this technique.

The problem to be solved: select $k$ out of $n$ people to form a line

Approach 1: this is the definition of permutation, therefore the answer is $P_n^k = n(n-1)\cdots(n-k+1)$ different ways.

Approach 2: let's compete this task by the following steps:

- Select $k$ out of $n$ people to form a group (i.e. order does not matter). This is the definition of combination. Therefore the count is $C_n^k$.
- Let these $k$ people to form a line. This is a permutation problem and the count is $P_k^k=k(k-1)\cdots 1$.

By the principle of multiplication, there will be $C_n^k\cdot P_k^k$ distinct ways in total.

Because these two approaches should both give the same answer, we have $$P_n^k=C_n^k\cdot P_k^k\implies C_n^k = \frac{P_n^k}{P_k^k}$$