A beautiful combinatorics argument

Today a teacher in my department was struggling to understand algebraically and conceptually why:

binom

He was on the way to making a neat Pascal’s Triangle argument. Look at that 70. That’s $\binom{8}{4}$ :

pascal

He started working backwards, and saw that 70=35+35.

But each of those 35s came from 15 and 20. So 70=(15+20)+(20+15).

And then going backwards more, we see the 15 comes from 5 and 10, and the 20 comes from 10 and 10. So 70=((5+10)+(10+10))+((10+10)+(10+5)).

And then going backwards once more, we see the 5 comes from 1 and 4, and the 10 comes from 4 and 6. So 70=(((1+4)+(4+6))+((4+6)+(4+6)))+(((6+4)+(6+4))+((6+4)+(4+1)))

In other words, 70=1*1+4*4+6*6+4*4+1*1.

By the time we make our way down from the 1-4-6-4-1 row to 70, we see that:

The first one in the 1-4-6-4-1 row just is added once when making the 70.
The first four in the 1-4-6-4-1 row is added four times when making the 70.
The six in the 1-4-6-4-1 row is added six times when making the 70.
The second four in the 1-4-6-4-1 row is added four times when making the 70.
The second one in the 1-4-6-4-1 is added just once when making the 70.

In other words: 70=1^2+4^2+6^2+4^2+1^2.

The other teacher and I realized we could generalize this. But we were left unsatisfied. It was a Pascal’s Triangle argument, but I wanted to see the answer with an understanding of combinations. I wanted something even more conceptual. So my friend and I started thinking, and he had an awesome insight. And I want to record it here so I don’t lose it! It made me so happy — little mathematical endorphins exploding in my head!

Let’s assume we have a set of 2n letters, where n letters are A and n letters are B.

Blergity blerg, let’s just keep things concrete, and have 8 letters, where 4 are As and 4 are Bs. (We can generalize later, but I want to just see this happen!) Given 4As and 4Bs, there are $\binom{8}{4}$ ways to arrange them to make different 8 letter words [1]. Great! That was the easy part.

Now we are going to construct a whole bunch of different sets of 8 letter words, in a particular way (using AAAABBBB), so that when we add up all those sets, we’re going to get all possible 8 letter arrangements of AAAABBBB.

How are we going to do this? We are going to create special of 4 letter words and concatenate them together to make 8 letter words.

Set 1: We are going to create a 4 letter word with 0As (and thus by default, 4Bs) and a 4 letter word with 4As (and thus by default, 0Bs).

How many ways can we create 4 letter words with 0As? $\binom{4}{0}$ . To be clear, this is just 1. The word is {BBBB}.

How many ways can we create 4 letter words with 4As? $\binom{4}{4}$ . To be clear, this is just 1. The word is {AAAA}.

And when we concatenate them, we are going to have $\binom{4}{0}\cdot\binom{4}{4}$ eight letter words. But we know $\binom{4}{0}=\binom{4}{4}$ . So this is simply $\binom{4}{0}\cdot\binom{4}{0}$ . And this is just 1, because the only eight letter word possible is {BBBBAAAA}.

This is a degenerate case, so it’s hard to really see what’s going on here. So let’s move on.

Set 2: We are going to create a 4 letter word with 1A (and thus by default, 3Bs) and a 4 letter word with 3As (and thus by default, 1Bs).

How many ways can we create 4 letter words with 1As? $\binom{4}{1}$ . To be clear, this is just 4. The words are {ABBB, BABB, BBAB, BBBA}.

How many ways can we create 4 letter words with 3As? $\binom{4}{3}$ . To be clear, this is just 4. The words are {AAAB, AABA, ABAA, BAAA}.

And when we concatenate them, we are going to have $\binom{4}{1}\cdot\binom{4}{3}$ eight letter words. But we know $\binom{4}{1}=\binom{4}{3}$ . So this is simply $\binom{4}{1}\cdot\binom{4}{1}$ . And this is 16 eight letter words. (Each of the first four letter words can be paired with each of the second four letter words… so this is merely 4*4. Just to be clear, I’ll list the first few eight letter words out: ABBBAAAB, ABBBAABA, ABBBABAA, ABBBBAAA, BABBAAAB, BABBAABA, …

Set 3: We are going to create a 4 letter word with 2As (and thus by default, 2Bs) and a 4 letter word with 2As (and thus by default, 2Bs).

How many ways can we create 4 letter words with 2As? $\binom{4}{2}$ . To be clear, this is just 6. The words are {AABB, ABAB, ABBA, BAAB, BABA, BBAA}.

And when we concatenate them, we are going to have $\binom{4}{2}\cdot\binom{4}{2}$ eight letter words. And this is 36. (Each of the first four letter words can be paired with each of the second four letter words… so 6*6 eight letter words.)

Set 4: We are going to create a 4 letter word with 3As (and thus by default, 1B) and a 4 letter word with 1As (and thus by default, 3Bs). By the same logic as above, we are going to end up with $\binom{4}{3}\cdot\binom{4}{3}$ eight letter words. This is just 4*4 eight letter words.

Set 5: We are going to create a 4 letter word with 4As (and thus by default, 0Bs) and a 4 letter word with 0As (and thus by default, 1B). By the same logic as above, we are going to end up with $\binom{4}{4}\cdot\binom{4}{4}$ eight letter words. This is just 1*1 eight letter words.

Now look at all the different eight letter words created by this process, from Set 1, Set 2, Set 3, Set 4, and Set 5. We have captured every single possible eight letter word with four As and four Bs. Let’s check a few random words:

AABABBAB… okay this is in Set 4.
BAABAABB… okay this is in Set 3.
BBBABAAA… okay this is in Set 2.

Cool! I only have to look at the first four letters to decide which set it is going to be in!

But look at what we’ve done. We’ve shown that we can get all eight letter words in these five sets… so the number of eight letter words is:

$\binom{4}{0}\cdot\binom{4}{0}+\binom{4}{1}\cdot\binom{4}{1}+\binom{4}{2}\cdot\binom{4}{2}+\binom{4}{3}\cdot\binom{4}{3}+\binom{4}{4}\cdot\binom{4}{4}$

If we simply write the squares out…

$\binom{4}{0}^2+\binom{4}{1}^2+\binom{4}{2}^2+\binom{4}{3}^2+\binom{4}{4}^2$

But we saw at the very start that the number of eight letter words is simply $\binom{8}{4}$

So the two are equal.

All the hard work is done, so I leave it as an exercise to the reader to generalize.

P.S. I take no credit for this amazingly wonderful letter rearrangement solution. I just bore witness as my friend figured it out, and I got giddier and giddier. I love it because it’s abstract, but still understandable to me. But it’s close to my threshhold of abstraction!

[1] If you don’t quite see this, imagine 8 blank slots.

___ ___ ___ ___ ___ ___ ___ ___

You choose four of them to put the As into. There are $\binom{8}{4}$ ways to choose four of these slots. Put As into those four. By default the rest of the slots must be filled with Bs — they are forced! So there are $\binom{8}{4}$ ways to create eight letter words with four As and four Bs.

Continuous Everywhere but Differentiable Nowhere

I have no idea why I picked this blog name, but there's no turning back now

A beautiful combinatorics argument

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply