Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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}$.

share|cite|improve this answer
    
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.

share|cite|improve this answer
    
: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}. $$

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.