# Binomial theorem combinatorics derivation

We can split any term $(x+y)^n$ into a choice tree with $2^n$ path choices. Also, we can represent each factor in terms of $x^ky^{n-k}$

It is logical to deduce we can express this with summation notation:

$$\sum_{k=0}^{n}{cx^ky^{n-k}}$$

where c is the coefficient of the term. Everything makes sense to me, except how we can find c. Apparently, we can define c as $$\binom{n}{k}$$

But this is confusing for me, and the only definition I can find is a very intense mathematical one:

The coefficient of $x^ky^{n-k}$ for a particular k is just the number of ways to choose k factors of y from the n factors of (x+y), with factors of x coming from the remaining (n−k) factors. The number of ways to choose k objects from a collection of n objects (without replacement, order not important) is just $\binom{n}{k}$.

I understand everything logically, and I've been trying to figure this out all day. I'm not new to combinatorics as I've taken a few statistics classes. But these were the basics, such as the number of ways to chose 2 fruits from a set of 3 fruits (say an apple, orange, banana).

Firstly, there are n+1 factors, and $2^n$ paths. So I just don't get the logic behind all of this, even though it does work.

• You go back and forth a lot. First you say you understand everything logically, then you say you don't understand the logic. First you call the definition of the binomial coefficient "very intense," then you say you're not new to combinatorics. These are contradictions! – blue Aug 9 '14 at 2:26
• Yes. I've taken the high school classes for statistics (the absolute basics) and I understand everything logically up until I have to define c as n choose k. – Jason Aug 9 '14 at 2:27
• I answered a more general question (regarding the multinomial theorem) once, you may find it helpful...then again, you may not...math.stackexchange.com/questions/750182/number-of-terms/… – Jared Aug 9 '14 at 2:44
• Is the statistics tag warranted? – robjohn Aug 9 '14 at 6:20

Distributing multiplication over addition in expanding $(x+y)^4$, we choose one of $x$ or $y$ in each of the $4$ terms.
To count the number of products resulting in $x^2y^2$, we count the number of ways to arrange $2$ $x$s and $2$ $y$s: \left.\begin{align} % xxyy \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(x+\color{#00A000}{y})}^{\large\color{#00A000}{y}} \overbrace{(x+\color{#00A000}{y})}^{\large\color{#00A000}{y}}\\ % xyxy \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(x+\color{#00A000}{y})}^{\large\color{#00A000}{y}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(x+\color{#00A000}{y})}^{\large\color{#00A000}{y}}\\ % xyyx \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(x+\color{#00A000}{y})}^{\large\color{#00A000}{y}} \overbrace{(x+\color{#00A000}{y})}^{\large\color{#00A000}{y}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}}\\ % yxxy \overbrace{(x+\color{#00A000}{y})}^{\large\color{#00A000}{y}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(x+\color{#00A000}{y})}^{\large\color{#00A000}{y}}\\ % yxyx \overbrace{(x+\color{#00A000}{y})}^{\large\color{#00A000}{y}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(x+\color{#00A000}{y})}^{\large\color{#00A000}{y}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}}\\ % yyxx \overbrace{(x+\color{#00A000}{y})}^{\large\color{#00A000}{y}} \overbrace{(x+\color{#00A000}{y})}^{\large\color{#00A000}{y}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \end{align}\right\}\binom{4}{2}x^2y^2 To count the number of products resulting in $x^3y$, we count the number of ways to arrange $3$ $x$s and $1$ $y$: \left.\begin{align} % xxxy \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(x+\color{#00A000}{y})}^{\large\color{#00A000}{y}}\\ % xxyx \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(x+\color{#00A000}{y})}^{\large\color{#00A000}{y}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}}\\ % xyxx \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(x+\color{#00A000}{y})}^{\large\color{#00A000}{y}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}}\\ % yxxx \overbrace{(x+\color{#00A000}{y})}^{\large\color{#00A000}{y}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}} \overbrace{(\color{#00A000}{x}+y)}^{\large\color{#00A000}{x}}\\ \end{align}\right\}\binom{4}{1}x^3y In $(x+y)^n$, the number of $x$s and the number of $y$s total to $n$. Thus, summing over all the possible numbers of $x$s, we get $$(x+y)^n=\sum_{k=0}^n\binom{n}{k}x^ky^{n-k}$$
• @Jason: From each $(x+y)$, we must choose either $x$ or $y$; that is, $2$ choices for each of the $(x+y)$s. Thus, there are $2^n$ terms that look like $x^ky^{n-k}$. In the examples above, $n=4$, so the sum of the exponents of $x$ and $y$ must be $4$. Therefore, we cannot get $x^2$. Am I missing the point of your question? – robjohn Aug 12 '14 at 0:31
• @Jason: These are the same combinations that you are talking about. $$\hphantom{ab\leftrightarrow}abcd\\cd\leftrightarrow xxyy\\ bd\leftrightarrow xyxy\\ bc\leftrightarrow xyyx\\ ad\leftrightarrow yxxy\\ ac\leftrightarrow yxyx\\ ab\leftrightarrow yyxx$$ A $y$ in the right column picks the letter in that position for the left column. $$\hphantom{a\leftrightarrow}abcd\\d\leftrightarrow xxxy\\ c\leftrightarrow xxyx\\ b\leftrightarrow xyxx\\ a\leftrightarrow yxxx$$ – robjohn Aug 12 '14 at 14:27
You can go factor by factor through the product $(x+y)\cdots(x+y)$, at each one choosing whether you want to pick the $x$ or the $y$. Or, you can pick which of the $n$ factors you want to pick the $x$s out of all at once, which automatically determines which the $y$s must be. This specifies the same information, really.