We want to find the number of different [[Number of Subsets|subsets]] of size $k$ where the [[Sample Space]] has size $n$ and the order does not matter. This is also called the “binomial coefficient”. $ \binom{n}{k}=\frac{n!}{k!*(n-k)!} $ ## Derivation We will establish an equality in 2 ways to get the number of $k$-sized subsets where order matters. 1. *Number of subsets with permutation:* There is $\binom{n}{k}$ possible subsets, and each of them can be ordered in $k!$ ways. $ \binom{n}{k}*k! $ 2. *Directly via permutation:* We draw for each of the $k$ slots $k$-times, where the final draw has only $(n-k)$ options left. $ n*(n-1)*\dots*(n-k) = \frac{n!}{(n-k)!} $ ![[subsets-size-k.png|center|400]] **Setting terms equal:** Now that we have two expressions for the number of ordered subsets of size $k$, we can set them equal: $ \begin{align} \binom{n}{k}*k! &=\frac{n!}{(n-k)!} \\[4pt] \binom{n}{k} &=\frac{n!}{k!_(n-k)!} \end{align} $ ## Validating Extreme Cases $ \begin{align} \text{where } k=0: \binom{n}{0}=\frac{n!}{0!(n-0)!}= \frac{n!}{n!}=1\\[6pt] \text{where } k=n:\binom{n}{n} =\frac{n!}{n!(n-n)!}=\frac{n!}{n!}=1\\[6pt] \text{sum all }k: \sum_{k=0}^n \binom{n}{k}=2^n \impliedby\text{(all subsets)} \end{align} $ **Note:** We adopt the convention that $0! =1$