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.

to keep it simple: Given

$(a+b)^3=\binom{3}{0}a^3+\binom{3}{1}a^2b+\binom{3}{2}ab^2+\binom{3}{3}b^3$

Could you please give me an intuitive combinatoric reason to why the binomial coefficients are here? for instance, what does $\binom{3}{2}ab^2$ mean combinatorially?

Thank you very much.

share|improve this question

3 Answers 3

up vote 6 down vote accepted

$\binom{3}{2}$ means the number of possibilities to choose two elements from a three-element set without replacement. More generally, $\binom{n}{k}$ means how many ways there are to chose a $k$-element subset of an $n$-element set.

Now, $(a+b)^3 = (a+b)(a+b)(a+b)$, so there are three factors; let's call them $1,2,3$. Now, when expanding this product into a sum, we must consider all possible pairings of summands. Since they all have the same form, we can basically just use a subset of $\{1,2,3\}$ to denote from which factors we take the $a$; the rest of the factors will then be $b$.

So, taking a subset $S \subseteq \{ 1,2,3 \}$, we get a term that takes the $a$ terms from the factors listed in $S$, and the $b$ terms from the factors not in $S$. Some further thought shows that this just gives a term $a^{|S|} b^{3-|S|}$. Now, there are exactly $\binom{3}{|S|}$ subsets of size $|S|$, so you get $\binom{3}{|S|}$ terms of the form $a^{|S|}b^{3-|S|}$. The binominal theorem follows from this, since you need to consider all subsets.

share|improve this answer
    
Thank you very much for the in-depth answer. I think I got it, if i'll have question about it i'll ask it later today. Thanks again :) –  Anonymous Apr 4 '12 at 9:34

$\binom{3}{2}ab^2=abb+bab+bba$

share|improve this answer

This isn't as rigorous as the accepted answer, but explores the question a bit from another perspective.

Take your example,

$(a+b)^3=\binom{3}{0}a^3+\binom{3}{1}a^2b+\binom{3}{2}ab^2+\binom{3}{3}b^3$

Let us consider this small rewrite of the same example: $(a+b)^3=\binom{3}{0}{a}\cdot{a}\cdot{a}+ \binom{3}{1}{a}\cdot{a}\cdot{b}+ \binom{3}{2}{a}\cdot{b}\cdot{b}+ \binom{3}{3}{b}\cdot{b}\cdot{b}$

Consider that the binomial if expanded would take on the following product:

$(a+b)^3 = (a+b)(a+b)(a+b)$

To compute this product we have to pick one summand in each of the $(a+b)(a+b)(a+b)$ and multiply them together. We then do this in all possible ways adding each term together. Since there's $2$ possibilities for each of $3$ choices there's $2^3=8$ total possibilities. In essence, we are forming all length 3 strings over the alphabet $\{a,b\}$.

That may be hard to follow, but it's easy to see it written out:

$(a+b)^3 = (a+b)(a+b)(a+b) = $ ${a}\cdot{a}\cdot{a} + {a}\cdot{a}\cdot{b} + {a}\cdot{b}\cdot{a} + {b}\cdot{a}\cdot{a} + {b}\cdot{b}\cdot{a} + {b}\cdot{a}\cdot{b} + {a}\cdot{b}\cdot{b} + {b}\cdot{b}\cdot{b}$

So there's $8$ possibilities, so let's think about it intuitively as you asked:

  1. How many length 3 strings can we make over $\{a,b\}$ where we are allowed to choose $0 b$'s? Well, there's $\binom{3}{0}$ of those: $\{aaa\}$. Hence the first term, $\binom{3}{0}a^3$.

  2. How many length 3 strings can we make over $\{a,b\}$ where we are allowed to chose $1 b$? Well, there's $\binom{3}{1}$ of those: $\{aab,aba,baa\}$. Hence the second term, $\binom{3}{1}a^2b$.

  3. Same as above, but we choose $2 b$'s? $\{bba,bab,abb\}$. To get third term, $\binom{3}{2}ab^2$. This is what Marc van Leeuwen's terse answer is conveying, and is in essence the "combinatorial meaning" you asked for in your example.

  4. Now we choose $3 b$'s? $\{bbb\}$. To get fourth term, $\binom{3}{0}b^3$.


Dave L. Renfro makes a good point:

none of the current answers explain why (a+b)(a+b)(a+b) can be expanded by considering the sum of all possible ordered products of three elements, where the first element comes from the first factor of (a+b), the second element comes from the second factor of (a+b), and the third element comes from the third factor of (a+b).

I'll do my best to explain this one. You see, we're actually repeatedly applying the distributive law of multiplication over addition.

For this example, consider this:

$(a+b)(a+b)(a+b)$

$= ((a+b)a + (a+b)b)(a+b)$ Here you distribute the first factor into the second.

$= (aa + ba + ab + bb)(a+b)$ Distribute again.

$= (aa(a+b) + ba(a+b) + ab(a+b) + bb(a+b))$ Distribute again.

$= aaa + aab + baa + bab + aba + abb + bba + bbb$

Intuitively as we distribute an $(a+b)$ we are "choosing" a or b, but recording both results... in a way.

In effect if we say distribute $c$ over $(a+b)$ we are effectively recording what happens to c when we choose a, and also when we choose b, e.g. $c(a+b) = ca + cb$

share|improve this answer
1  
This isn't as rigorous as the accepted answer ... In informal discussions, I think the degree of rigor is sometimes in the eye of the beholder. I certainly don't see your answer as less rigorous. Indeed, as regards to rigor, I notice that none of the current answers explain why $(a+b)(a+b)(a+b)$ can be expanded by considering the sum of all possible ordered products of three elements, where the first element comes from the first factor of $(a+b),$ the second element comes from the second factor of $(a+b),$ and the third element comes from the third factor of $(a+b).$ –  Dave L. Renfro Sep 20 '13 at 17:07

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.