There are 2 different types of selections in this class: permutations and combinations.
Permutations. Selections where the order matters ($ab$ and $ba$ are distinct).
Combinations. Selections where the order does not matter ($QPR$ and $PQR$ are indistinct).
Any selection can be made with replacement, where sampled elements are placed back into the sampling pool, and without replacement, where no sampled element can be chosen again. Counting the number of ways to select $k$ elements out of $n$ total elements, we have the following formulas,
| With Replacement | Without Replacement | |
|---|---|---|
| Permutations | ||
| $n^k$ | $\frac{n!}{(n-k)!}$ | |
| Combinations | $\begin{pmatrix} n - 1 + k \\ k \end{pmatrix} = \begin{pmatrix} n - 1 + k \\ n-1 \end{pmatrix}$ | $\begin{pmatrix} n \\ k \end{pmatrix}$ |
The term appearing in the last row is known as the binomial coefficient and counts the number of ways to choose $k$ elements from $n$ total elements where order does not matter and no element is repeated. For this reason, this is sometimes equivalently thought of as the number of ways to choose subsets of size $k$ from a set of size $n$.
There are three “rules of counting” discussed in this course.
Foundation of combinatorial proofs.
<aside> 💡
If there exists a bijection $f : A \rightarrow B$, then $|A|=|B|$
</aside>
Mainly governs permutations.
<aside> 💡
If an object is made through $k$ ordered choices, where there is $n_1$ ways to choose the first element, and for every choice of the first element there is $n_2$ ways to choose the second element, and so on until for every way of choosing the first $k-1$ elements there is $n_k$ ways to choose the $k$th element, then the number of distinct such objects is $\prod _{i = 1} ^k n_k$
</aside>
There are $\prod_{i=1} ^k n_i$ leaves in this tree.