Why does n choose k give the number of ways to choose k copies of a's in binomial theorem?

Question

In the expression $(a+b)^n$, I understand that we are summing together all of the combinations of length $n$ involving $a$ and $b$.

What I don't understand is why $n$ choose $k$ corresponds to the number of ways to choose k copies of $a$'s in each term on an intuitive level.

How is the number of $a$'s related to $n$ and $k$ in the combinations formula? If we are forming a combination using $k$ a's, wouldn't our combination still have $n$ terms, so we would need to choose $n$ rather than choose $k$?

Thanks.

Answer 1

To illustrate the idea, let $\ n = 3\ $ and $\ k = 2$.

If we compute $(a + b)^3$ as

$$(a + b)\cdot(a + b)\cdot(a + b)$$

we will obtain

$$aaa+aab+aba+abb+baa+bab+bba+bbb.$$

How many addens contains exactly two $a$'s?

                                              

So we choose $2$ positions from $3$, OK?

In general, we choose $k$ positions from $n$, and there are $\binom n k $ such combinations.

Answer 2

If you are familiar with the fact that $\binom{n}{k}$ gives the number of $k$-element subsets from an $n$-element set, the following might also be useful.

• In the following we use the notation $[n]:=\{1,2,3,\ldots,n\}$ to denote the set of the natural numbers from $1$ to $n$. When we consider a subset \begin{align*} S\subseteq [n] \end{align*} this means that \begin{align*} S\in\{&\emptyset,\tag{$\to\binom{n}{0}$}\\ &\{1\},\{2\},\{3\},\ldots,\{n\},\tag{$\to\binom{n}{1}$}\\ &\{1,2\},\{1,3\},\{1,4\},\ldots,\{n-1,n\},\tag{$\to\binom{n}{2}$}\\ &\ldots,\\ &\{1,2,3,\ldots,n\}\tag{$\to\binom{n}{n}$}\} \end{align*} and we note that the number of subsets of $[n]$ with $k$ elements is $\binom{n}{k}$.

We obtain \begin{align*} \color{blue}{(a+b)^n}&=\prod_{j=1}^n(a+b)\tag{1}\\ &=\sum_{S\subseteq[n]} a^{|S|}b^{n-|S|}\tag{2}\\ &=\sum_{k=0}^n\sum_{{S\subseteq[n]}\atop{|S|=k}}a^kb^{n-k}\tag{3}\\ &=\sum_{k=0}^n\left(\sum_{{S\subseteq[n]}\atop{|S|=k}}1\right)a^kb^{n-k}\tag{4}\\ &\,\,\color{blue}{=\sum_{k=0}^n\binom{n}{k}a^kb^{n-k}}\tag{5}\\ \end{align*}

Comment:

• In (1) we write$(a+b)^n$ as product of $n$ copies of $(a+b)$, namely as \begin{align*} \prod_{j=1}^n(a+b) =\underbrace{(a+b)\cdots(a+b)}_{\mathrm{n\ times}} \end{align*}

• In (2) we consider the $n$ copies of $(a+b)$ enumerated from $1$ to $n$, and we expand the product as follows:

  • For each subset $S\subseteq [n]$ we take precisely the $a$ from those binomials which are given in $S$. We obtain this way the factor $a^{|S|}$.

  • We select $b$ from all the other binomials, i.e the binomials which are numbered from $[n]\setminus S$ and we get $b^{n-|S|}$.

  • We do this for all possible subsets from $[n]$ which means we sum over all the subsets $S\subseteq[n]$.

• In (3) we rearrange the summands and sort them according to the number of elements of the subset $S$ which ranges from $0$ to $n$. This sorting scheme is already indicated in the list at the beginning of this answer.

  • Since we sorted them according to $k$ we can now write $a^kb^{n-k}$ instead of $a^{|S|}b^{n-|S|}$.

• In (4) we factor out $a^kb^{n-k}$ leaving an inner sum which sums up $1$s only.

• In (5) we note that the inner sum counts the number of $k$-element subsets of an $n$-element set. This is $\binom{n}{k}$, which we established at the very beginning.

Answer 3

Think of a group of $k$ numbers chosen from $n$ as being a list of the positions of the letter "a" in a string of $n$ letters containing only "a" and "b"

For instance for $k=3, n=5$, the choice of $\{1, 2, 5\}$ corresponds to the string "aabba" and $\{ 3, 4, 5\}$ to "bbaaa"

Answer 4

Imagine we have $k$ a's and $n-k$ b's. Any shuffle yields $k$ a's, and there are $n!$ such shuffles.

However, exactly $k!$ of the shuffles have the a's in the same place as another shuffle, and the same with the $(n-k)!$ b's, so these can be removed.

This leaves that the number of shuffles is $$\frac{n!}{k!(n-k)!}$$.