Why does $n \choose k$ get you the $k^{th}$ (starting from 0) coefficient of $(a+b)^n?$ I'm aware of the connection between Pascal's triangle and the binomial theorem, and how each edge, left and right if we consider the triangle to be a graph, represents multiplying by $a$ or $b.$ But how do we relate this to combinatorics?

$$(a+b)^n=\underbrace{(a+b)(a+b)\cdots(a+b)}_{\text{n times}}$$ To get a term of the form $a^kb^{n-k}$ we need to choose an $a$ out of the $n$ factors $k$ times and a $b$ out of the remaining $(n-k)$ factors $(n-k)$ times. Hence the coefficient of  $a^kb^{n-k}$ in the expansion is 
$$\binom{n}{k}\binom{n-k}{n-k}=\binom{n}{k}$$
As an example consider 
$$
\begin{align}
(a+b)^3
&=(a+b)(a+b)(a+b)\\
&={aaa}+{aab+aba+baa}+{abb+bab+bba}+bbb\\
&=\binom{3}{3}a^3+\binom{3}{2}a^2b+\binom{3}{1}ab^2+\binom{3}{0}a^0b^3
\end{align}$$ 
