# 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?

• When you foil $(a+b)\cdots(a+b)$, you need to choose $k$ out of $n$ of the factors to pick an $a$ from, and the rest will be $b$s. There are $\binom{n}{k}$ ways of choosing $k$ out of $n$ things. – arctic tern Aug 25 '16 at 16:31
• In some presentations, it's the definition of $\dbinom nk$ (whence its name of binomial coefficient). – Bernard Aug 25 '16 at 16:38

There are $n$ factors of $a+b$ in $(a+b)^n$ and each can contribute an $a$ or a $b$. To get the number of ways those factors can multiply to $a^kb^{n-k}$ we choose $k$ of the factors to contribute an $a$ (and the remaining $n-k$ contribute $b$). That show that there are exactly $\binom{n}{k}$ ways, so that is the coefficient.

• what does mean : "There are $n$ factors of $a+b$ in $(a+b)^n$ and each can contribute an $a$ or a $b$" ? It's difficult to understand why an incomprehensible answer can be accepted (and upvoted) (-1) – idm Aug 25 '16 at 23:58
• Um, it means that $(a+b)^n = \underbrace{(a+b)(a+b)\dots(a+b)}_{n \text{ times}}$ and that when multiplying, each factor contributes an $a$ or a $b$. Was that really unclear? – Michael Biro Aug 26 '16 at 1:41

By definition $$(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^kb^{n-k}.$$

Why this formula ? Let $A$ a set with $a$ elements and $B$ a set with $b$ element s.t. $A\cap B=\emptyset$. $(a+b)^n$ is the number of function from $\{1,...,n\}\longrightarrow A\cup B.$ But you can count them as following : The number of function that send $k$ elements of $\{1,...,n\}$ in $A$ is $$\binom{n}{k}a^kb^{n-k}$$ since you can take $k$ element from $\{1,...,n\}$ with $\binom{n}{k}$ possibilities, and each of those $k$ element has $a$ possibilities in $A$. After, the $n-k$ other are sent on $B$, and each element has $b$ possibilities in $B$. Notice that you can choose $n-k$ other element with $\binom{n-k}{n-k}=1$ possibility (in other way, you don't have the choice). If we denote $f_k$ a function that send $k$ element of $\{1,...,n\}$ in $A$ (and the other in $B$), finally, $$(a+b)^n=\sum_{k=0}^n|\{f_k:\{1,...,n\}\to A\cup B\}|=\sum_{k=0}^n\binom{n}{k}a^kb^{n-k}.$$

To finish, even if I understood what you tried to mean, to talk about the $k-$th coefficient of $(a+b)^n$ has no sense. It would have sense if you would have ask the $k-$th coefficient of $(a+b)^n$ in $\mathbb R[a]$ (or in $\mathbb R[b]$, but it's not the same coefficient).

Write the whole product:

$$(a+b)^n=(a+b)(a+b)\cdot\ldots\cdot(a+b)$$

To get the coefficient of $\;a^k\;$ in the above, you have to take all the possible products of $\;a\;$ with itself $\;k\;$ times, which is just the same as choosing all the subsets with $\;k\;$ elements in a set with $\;n\;$ elements, as each such subset represents just one of the above products.

$$(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}