- Let's say that there
are four people in a room. And you're probably tired of me naming the people with letters, but I'm going to continue doing that. So the four people in the room
are people A, B, C, and D. And they are all told,
"You don't know each other. "So I want you to all meet each other. "You need to shake the hand, exactly once, "of every other person in the
room so that you all meet." So my question to you is,
if each of these people need to shake the hand of every
other person exactly once, how many handshakes are going to occur? The number of handshakes
that are going to occur. So, like always, pause the video and see if you can make sense of this. Alright, I'm assuming
you've had a go at it. So one way to think about it is, if you say there's a handshake, two people are party to a handshake. We're not talking about
some new three-person handshake or four-person handshake, we're just talking about the traditional, two people shake their right hands. And so, there's one person and there's another person in this party. There's four possibilities of one party. And if we assume people aren't
shaking their own hands, which we are assuming, they're always going to shake someone else's hand. For each of these four
possibilities who's this party, there's three possibilities
who's the other party. And so you might say that there's four times three handshakes. Since there's four times
three possible handshakes. And what I'd like you to
do is think a little bit about whether this is
right, whether there would actually be 12 handshakes. You might have thought
about it, and you might say, there's four times three, this is actually counting the permutations. This is counting how
many ways can you permute four people into two
buckets, the two buckets of handshakers, where you care about which bucket they are in. Whether they're handshaker number one, or handshaker number two. This would count A being
the number one handshaker and B being the number two handshaker as being different than B
being the number one handshaker and A being the number two handshaker. But we don't want both
of these things to occur. We don't want A to shake B's hand, where A is facing north
and B is facing south. And then another time,
they shake hands again where now B is facing north
and A is facing south. We only have to do it once. These are actually the same thing, so there's no reason for
both of these to occur. So we are going to be double counting. So what we really want to do
is think about combinations. One way to think about it
is, you have four people. In a world of four people
or a pool of four people, how many ways can you choose two? Because that's what we're doing. Each handshake is just really a selection of two of these people. And so we want to say, how many ways can we select two people? So that each combination,
each of these ways to select two people
should have a different combination of people in it. If two of them have the same, AB and BA, these are the same combination. And so this is really
a combinations problem. This is really equivalent to saying, how many ways are there
to choose two people from a pool of four? Or four choose two. And so this is going to
be, well how many ways are there to permute four
people into three spots? Which is going to be four times three. Which we just figured out
right over there, which is 12. Actually want to do it in that green color so you see where that came from. So four times three. And then you're going to divide that by the number of ways you
can arrange two people. Well you can arrange two
people in two different ways. One's on the left, one's on the right, or the other one's on the left or the other one's on the right. Or, you could also view
that as two factorial, which is also equal to two. So we could write this down as two. This is the number of ways
to arrange two people. This up here, that's the permutations. That's the number of permutations if you take two people
from a pool of four. So here you would care about order. And so one way to think about it, this two is correcting for this
double counting here. And if you want to apply
the formula, you could. I just kind of reasoned through it again. You could literally say,
four times three is 12. We're double counting because there's two ways to arrange two people. So you just divide it by two. And then you are going
to be left with six. You can think of it in terms of this, or you could just apply the formula. You could just say, four choose two, or the number of combinations of selecting two from a group of four. This is going to be four
factorial over two factorial times four minus two factorial. And I'm going to make this
color different just so you can keep track of how
I'm at least applying this. And so what is this going to be? This is going to be four times
three times two times one, over two times one times
this right over here is two times one. So that would cancel with that. Four divided by two is two. Two times three divided
by one is equal to six. And to just really hit the point home, let's actually draw it out. A could shake B's hand. A could shake C's hand. A could shake D's hand. Let me just do what we
calculated first, the 12. B could shake A's hand. B could shake C's hand. B could shake D's hand. C could shake A's hand. C could shake B's hand. C could shake D's hand. D could shake A's hand. D could shake B's hand. D could shake C's hand. And this is 12 right over here, and this is the permutations. If D shaking C's hand
was actually different than C shaking D's hand,
then we would count 12. But we just wanted to say, how many ways, they just have to meet each other once. And so we're double counting. So AB is the same thing as BA. AC is the same thing as CA. AD is the same thing as DA. BC is the same thing as CB. BD is the same thing as DB. CD is the same thing as DC. And so we would be left with, if we correct for the double counting, we're left with one,
two, three, four, five, six combinations. Six possible ways of choosing
two from a pool of four. Especially when you don't care about the order in which you choose them.