The binomial coefficient basically provides the number of ways to choose a set of $k$ from $n$ sets. To me, it can be considered the number of unique ways to pick $k$ amount of "cards" from a deck of $n$.

However, I don't see why this provides the coefficient of the polynomial. Why does the number of unique ways to pick $k$ numbers from a set of $n$ provide the coefficient of the polynomial?

I already looked at the combinatorial explanation offered by Wikipedia, however I do not understand it.

up vote 7 down vote accepted

When you expand $(a+b)^n$, in each term of the sum you make $n$ decisions whether to pick $a$ or $b$, e.g. $(a+b)^3 = (a+b)(a+b)(a+b)$. But then you group all the terms with the same number of $a$ and $b$ (and if the number of $a$s is fixed, then so are $b$s, because $\#b = n-\#a$). So the coefficient before $a^kb^{n-k}$ is the number of ways you can pick $k$ copies of $a$ out of $n$ possible choices (and at the same time $n-k$ copies of $b$), and thus we have $\binom{n}{k}a^kb^{n-k}$.

  • Perfect, thank you. – user26649 Apr 22 '12 at 20:58

Consider the pascal triangle of powers of $\,(a+b)$ :

\begin{array} {lc} n&(a+b)^n\\ \hline 0&1\\ 1&a+b\\ 2&a^2 + 2ab + b^2\\ 3&a^3 +3a^2b+3ab^2+b^3\\ 4&a^4 +4a^3b+6a^2b^2+4ab^3+b^4\\ \end{array} To go from $1$ to (say) $a^2b$ using only multiplication by $a$ or $b$ you may use different paths (from top to bottom) :

  • $1\to a\to a^2\to a^2b\ $ (we choose $b$ at the third bifurcation)
  • $1\to a\to ab\to a^2b\ $ (we choose $b$ at the second bifurcation)
  • $1\to b\to ab\to a^2b\ $ (we choose $b$ at the first bifurcation)

From the three possible paths we will add three terms and get $3$ in front of $\,a^2b$.

If you forget $a$ (i.e. set $a:=1$) you may think that you choose or not to multiply by $b$ at each of the three iterations corresponding to one choice between three : $\,\large{\binom{3}{1}}$.
To get to $\,ab^2\,$ instead you would have to choose $b$ two times between three : $\,\large{\binom{3}{2}}$ and so on.

Except for $a^n$ we may come from the upper left or the upper right only so that the total number of paths from $1$ to $\,a^{n-k}b^k\;$ (in $(a+b)^n$ with $b$ to power $k>0$) will be given by :

$\{$number of paths to $a^{n-k}b^{k-1}\}+\{$number of paths to $a^{n-k-1}b^k\}$ : $\,\displaystyle\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$
that is $\large{\binom{3}{1}=\binom{2}{0}+\binom{2}{1}}\,$ in our $a^2b$ example.

  • :Could you tell how b -> ab -> a^2b came? – justin Dec 30 '15 at 9:35
  • @justin: Hmm in fact there was an old typo : The text should have been "To go from 1 to say $a^2b$" and not "from $a$ to"... I edited my answer a little. Thanks to notice anyway! – Raymond Manzoni Dec 30 '15 at 11:03

Without using the commutativity of multiplication, the binomial theorem is actually simpler and does not involve binomial coefficients: it reads $$ (a+b)^n=\sum_{w\in\{a,b\}^n} \Pi(w), $$ where $\{a,b\}^n$ designates the set of $n$-letter words over the two-letter alphabet $\{a,b\}$, and for such a word $w$ the notation $\Pi(w)$ means multiply together the values designated by the letters of $w$, in order. For instance for $n=3$ this becomes (writing multiplication as usual simply by juxtaposition) $$ (a+b)^3=aaa+aab+aba+abb+baa+bab+bba+bbb. $$ Now if one does assume commutativity, some of these terms are equal. All that really counts in a product is the number $k$ of factors $a$ and the number $n-k$ of factors $b$ it contains. The set of terms that thus contribute a factor $a^kb^{n-k}$ is obtained from the set of words $w\in\{a,b\}^n$ that contain $k$ letters $a$ and (therefore) $n-k$ letters $b$. The number of such words equals the number of distinct ways to choose $k$ positions for the letters $a$ among the available $n$ positions, and this number is by definition $\binom nk$. Now grouping similar terms gives the usual binomial formula (for the commutative case) $$ (a+b)^n=\sum_{k=0}^n\binom nka^kb^{n-k}. $$

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.