Every selection was counted once per arrangement of itself

0:00Three players stand in front of you - X, Y and Z - and you have to pick two of them for a team. Counting with order is the tool you already have, so use it. There are three players who could take the first place and two left over for the second, which makes six ordered rows. Here they are, all six of them, written out. Now count the teams.

0:24There are three. Six is not the answer, and it is not a mistake either. Six is the honest count of something else - of ordered rows, when what you were asked for was teams. Every team up there has been written down twice, once in each order, and the whole of this video is about making that sentence exact enough to divide by. Look at the first two rows: X then Y, and Y then X.

0:55Those are two rows and one team. A team does not know which of its two players you happened to write down first. So the six rows fall into three groups of two, and each group is one team wearing two names. X with Y, X with Z, and Y with Z. Six rows, in blocks of two, is three teams. That division is the only move in this whole video.

1:21Everything from here is about earning the right to make it - about what that two really has to be, and about when there is no such number at all. Two more questions where the order is thrown away, and both are worth doing before any formula turns up. Twelve people are in a room, and everyone shakes hands with everyone else. You could line them up two at a time - twelve choices for the first, eleven for the second, a hundred and thirty-two ordered rows.

1:55Then notice that when I shake your hand, you do not separately shake mine. That leaves sixty-six handshakes. Here is the same answer along a route with no theorem in it at all. Each of the twelve people has eleven hands to shake, so there are a hundred and thirty-two hand-ends in the room. Every handshake owns exactly two of them. A hundred and thirty-two hand-ends, two to a handshake, is sixty-six handshakes.

2:26Seven points on a circle, joined in pairs, give twenty-one chords by exactly the same argument. Four objects now - A, B, C and D - and two of them to be chosen. Keeping order there are twelve rows: four ways to fill the first place, three to fill the second. Here are six of them: A B, A C, A D, B C, B D and C D. And here are the other six, the ones nobody would bother to write: B A, C A, D A, C B, D B and D C.

3:03Six and six is twelve, which is the ordered count. Look at what that second list actually is. It is the overcount, written out in full. Every block of two holds exactly one row from the left-hand list and exactly one from the right, so the doubling is not a claim about the answer. It is a column you can point at. Before going any further, be exact about what makes two rows the same choice.

3:34Two rows are the same choice when they hold the same objects - the same ones, each of them as many times. Not when they merely look alike. Those two tests agree as long as every object is unlike the rest, and they come apart at the end of this video, so keep them apart from now on. A row and its reversal hold the same objects, and they are not the same row.

4:01Sameness of choice is something we are choosing to define, and having defined it we can go and measure with it. Take one choice - A, B and C - and open it out. How many rows on the ordered board hold exactly those three objects? A B C, A C B, B A C, B C A, C A B, C B A. Six of them. Now take a different choice, A, B and D, and do the same thing.

4:31Six again. And that is not luck. Whatever three objects you chose, the rows that hold exactly those three are the orderings of those three, and how many ways there are to order three things does not depend on which three they are. Six every single time. Checked at every shape up to six objects, every choice supplies the same number of rows, and that number is the factorial of how many you chose.

5:04Which gives us the sentence the whole subject rests on. The ordered count equals the selection count, times r factorial. Read that left to right and it looks like a way of getting the ordered count, which you did not need. Read it right to left and it tells you what the ordered count was made of. To build an ordered row you make a choice, and then you put the things you chose in order.

5:31Those are two separate jobs, and the second one costs the same r factorial no matter what the first one picked. That last clause is the theorem. Every selection has the same number of orderings, and that is why you may divide. One size up, to watch it hold. Five objects and three places: five, then four, then three - sixty ordered rows. Each choice of three supplies six of them, so there are ten choices.

6:05Here they are: A B C, A B D, A B E, A C D, A C E, A D E, B C D, B C E, B D E and C D E. Ten triples, sixty rows, six apiece. One warning about that list, though. Written in any other sequence it is the same ten, because a selection list is judged on completeness and never on order. But a list of ten with one triple written twice is not the same ten, and neither is a list of ten that has dropped one and let a stranger in.

6:43Now the mistake. The divisor is r factorial, where r is how many you chose. It is not n factorial. Only the objects you picked up are being reshuffled; the ones you left on the table are not being touched at all. Four objects, two at a time: twelve rows over two is six, and six is the answer. Twelve over twenty-four is one half, which is not even a whole number.

7:13So on that example the wrong divisor announces itself. It does not always. Score the two rules against every shape up to six objects - twenty-one shapes. Dividing by the factorial of how many you chose misses nothing at all: twenty-one out of twenty-one. Dividing by the factorial of how many were available gets fifteen of them wrong, and gets six of them right. Those six are exactly the shapes where you chose all of them.

7:45There, r and n are the same number, so the wrong rule and the right rule are the same rule. Which is how somebody carries this mistake a very long way: once for every size of collection it quietly hands back the right answer, and nothing says a word. Two more rules, priced the same way. Always dividing by two is right on exactly five shapes - every shape where you chose two.

8:14That is every handshake problem there is. And dividing by the factorial of how many you left behind is right on three of them: the shapes where you took exactly half. Turn the sentence into a formula. The selection count is the ordered count, divided by r factorial. And the ordered count is n factorial over the factorial of what you left behind. Put those together and the selection count is n factorial, over r factorial times the factorial of n minus r.

8:52It says nothing the picture did not already say. Underneath the line, r factorial is the orderings of what you chose, and the factorial of n minus r is the orderings of what you did not. Scored against every count built in this video, at all twenty-one shapes, it disagrees nowhere. Two ends of the range are left, and they do not behave the same way as each other. Choose all five of five objects.

9:24There is one way to do that - take the lot. The ordered board has a hundred and twenty rows on it, and every single one of them holds the same five objects, so all hundred and twenty are one block. One block, one choice. Now choose none of them. To select nothing is to leave the whole collection standing where it is, and there is one way to do that, so the count is one and not zero.

9:54Neither of those two came out of the formula. The formula cannot reach either end on its own, because at both ends it asks for the factorial of nothing, and a product of no factors will not say its value. So build the two ends first, and then ask what value would let the formula reach them. One works at both ends. Two disagrees at both. And nought makes the formula refuse to speak at all.

10:25One more thing the table shows, which is easy to get wrong. A selection count is not always smaller than the matching ordered count. Line the two of them up for every shape up to six objects. They come out equal in exactly two columns: where you chose one, and where you chose none. Choose one of six and there are six rows and six choices, because a row with one place in it has nothing to reorder.

10:55Choose none and both counts are one. From two upward they separate, at all fifteen of the remaining shapes, because two is where the factorial of what you chose starts exceeding one. Everything so far has quietly assumed the objects were unlike one another. Watch what happens when two of them are not. Three objects on the table: two of them show the letter A, and the third shows B.

11:25Two at a time, keeping order, there are still six rows. Group those six by which objects they hold and you get three blocks of two, exactly as before. Group them by what they look like and there are only two selections - A with A, and A with B. Those blocks are of size two and size four. They are not equal. So there is no one number to divide by, and the division is simply not available.

11:55Divide anyway, by two, and you get three. Three is a whole number, and it is the wrong answer. Coming out exact was never the licence. Equal blocks was the licence, and the blocks were equal because the objects you chose were unlike one another. One last thing worth carrying away from all this. That formula - n factorial over r factorial times the factorial of n minus r - is an expression.

12:27You can evaluate it long before you know what it counts. At five objects with two chosen it comes to ten, and that is arithmetic anybody can do. What this video has been doing is giving the ten a meaning: it is how many pairs you can choose out of five things. Choose three from five, as it happens, and you also get ten. That is worth being curious about, and nothing in today's argument explains it.

12:57What today's argument does explain is why there is a division there at all. The ordered count had been counting every selection once for each way of shuffling the objects you chose, and that number was the same for every selection alike, so it could be divided out.