[MUSIC PLAYING]
JOE BLITZSTEIN: Our story begins in an ancient forest
in the remote town of East Vandermonde.
Colin and Sylwia-- two college students on spring break--
are hiking through the forest.
COLIN: Why did you want to come all the way here, Sylwia?
We're in the middle of nowhere.
We should be studying for our probability course.
SYLWIA: Perhaps, we are.
PEACOCK: What are you doing?
These humans won't understand our sacred identities!
TOUCAN: Patience, my friend.
They will learn.
COLIN: What is this?
JOE BLITZSTEIN: Colin and Sylwia don't know what
to make of the scroll they have found.
COLIN: That's impossible.
It looks like they just added the a and b to get a plus b.
And added the k and c minus k to get c.
What kind of bird brain would come up with a formula like this?
SYLWIA: It looks mysterious and beautiful,
but that hardly means it isn't true.
Let's try some examples and see if we can prove or disprove it.
JOE BLITZSTEIN: Colin remembers from STAT110
how a binomial coefficient n choose k can
be defined in terms of factorials, n factorial over n
minus k factorial k factorial.
He tries a couple of examples on his calculator.
It is true in those examples.
So he proceeds to work on a proof using algebra.
[MUSIC PLAYING]
COLIN: [SIGHS] It's more of a mystery than ever.
I wonder if we'll ever know if this formula is always true,
or how anyone could have come up with it.
SYLWIA: Actually, I can prove it in a few sentences with no algebra needed.
COLIN: Huh?
SYLWIA: Look at the birds.
They will show you.
JOE BLITZSTEIN: Sylwia reminds Colin that they learned in STAT110
that the binomial coefficient n choose k can also be defined by a story.
It's the number of ways to choose a committee of size k from n people,
where the order in which people are chosen doesn't matter.
It's the number of subsets of size k for a set of size n.
It's the number of flocks of k birds that
can be formed by choosing birds from a flock of n birds
COLIN: I see peacocks and toucans flying around trying
to get on the top branches, but what does that have
to do with the formula on the scroll?
SYLWIA: Let's say there are a peacocks and b
toucans vying for the 6 top branches.
The number of possibilities for which birds get to perch on top branches
is a plus b choose 6.
That's the right hand side when c is 6.
COLIN: OK, but what about the left hand side?
SYLWIA: The left hand side just breaks this into cases.
If there is 1 peacock perched on a top branch,
there must be 5 toucans perched on top branches.
If there are 2 peacocks, there must be 4 toucans.
If there are k peacocks, there must be c minus k toucans.
So count how many possibilities there are
for which k peacocks and which c minus k toucans are on top branches.
Then sum up the cases since we want the total number of possibilities,
not just the number for one value of k.
JOE BLITZSTEIN: The formula on the scroll
is called Vandermonde's Identity.
Sylwia has just discovered a story proof of this identity.
She has given it an interpretation rather than doing
tedious or intractable algebra.
Both sides of the identity count the same thing, so they must be equal.
Sylwia gave her proof for the case c equal to 6
because she was looking at a tree with 6 top branches.
But the same idea works for any value of c.
Vandermonde's Identity is a handy result that
often comes up in problems involving binomial coefficients.
Thinking about it in terms of a story makes it easier
to remember and understand.
The moral of the story is to look for a story.
[MUSIC PLAYING]