# 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}$$

-
+1. That's pretty neat. –  Felix Marin Aug 10 '14 at 17:40
I am still slightly confused on the concept. If we count the number of ways of arranging 2 x's in your first example, isn't there a possibility we get x^2? IF the second two groups don't form y^2, then we get a different product than expected. (i.e., xxx*y = x^3*y) 4 choose 2 essentially means we're filling 2 slots, _ _, so doesn't the possibility as stated above exist? It is confusing. –  Jason Aug 12 '14 at 0:08
@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
I am just a little confused, because I learned combinations were the ways you could get k non-unique groups from n, that is n choose k. This means we have n total objects, with only k slot arrangements: if k = 3 and n=5, we have _ _ _ slots to fill with n objects. in your example 4 choose 2 and 4 choose 1, I don't understand how you figured out how to pick 2 or 1 for k. In 4 choose 2, we have _ _ slots to fill. I.e., 4*3/2=6. But we have to multiply 4 terms, not 2. So if we only pick 2 terms from the 4, we can only pick xx,yy,xy,yx. –  Jason Aug 12 '14 at 14:15
Then, if we pick say xx we still have to multiply this by (x+y)(x+y), so xx*(x+y)(x+y) which gives the possibility of getting a term like x^3y or x^4 or x^2y^2. Obviously this can't be true, so my thought process can't be right. –  Jason Aug 12 '14 at 14:16

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.

-