Why is the binomial coefficient related to the binomial theorem? 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.
 A: 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}$.
A: 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.
A: 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}.
$$
