Take the 2-minute tour ×
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.

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|improve this question

2 Answers 2

up vote 4 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|improve this answer
    
Perfect, thank you. –  user26649 Apr 22 '12 at 20:58

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

$$1$$ $$a+b$$ $$a^2 + 2ab + b^2$$ $$a^3 +3a^2b+3ab^2+b^3$$ $$a^4 +4a^3b+6a^2b^2+4ab^3+b^4$$

To go from $a$ to say $a^2b$ 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)

Each time you multiply by either $a$ or $b$ and here three paths are possible. If you forget $a$ (or 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.
In fact at any point we may come from the upper left or the upper right so that the total count of paths to $a^2b$ is the count of paths to $a^2$ plus the count of paths to $ab$ : $\binom{3}{1}=\binom{2}{0}+\binom{2}{1}$ terms.

share|improve this answer

Your Answer

 
discard

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