4
$\begingroup$

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.

3 Answers 3

6

$\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.

  • 0
    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 :)2012-04-04
6

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

3

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$

  • 2
    *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).$2013-09-20