Choosing what to leave out, and the rule that builds each count from two smaller ones

0:00Here are five objects, and you have to choose three of them. Circle the three you want. Now look at what you have just done from the other end. By circling those three you also, in the very same movement, named the two you did not want. There was one act, and it has two names. You can call it choosing three, or you can call it throwing back two, and the picture on the board does not change at all.

0:28So the number of ways to choose three from five and the number of ways to choose two from five are not two numbers that happen to come out equal. They are one number, counted once, under two different descriptions. Both of them are ten. That is a claim about a correspondence, so let us go and exhibit the correspondence. Here are the ten choices of three, and here are the ten choices of two.

0:57Take each choice of three and write down what it leaves behind. Three separate things have to hold, and not one of them is automatic. What a choice leaves behind has to be a choice of two - and it always is. No two different choices of three may leave behind the same pair - and none do. And every choice of two has to be left behind by something - and every one is.

1:24One for one, and nothing missed. That was checked at all forty-five shapes with up to eight objects, and it never once fails. Notice what the argument did not do. It never wrote down a formula and it never cancelled anything. You can also reach this by writing both counts as factorial quotients and noticing that the two denominators are the same product in the other order, and that is a perfectly good confirmation.

1:55But it tells you the two numbers are equal. It does not tell you they were never two numbers. Here is what that buys you when you are actually computing. Suppose you need the number of ways to choose eight objects out of ten. Done head-on, that is an eight-object job. Read it the other way round and it is the number of ways to choose two out of ten, which you can do in your head.

2:22Forty-five, both times. Nothing was simplified there and no trick was applied. The hard-looking question and the easy-looking question were the same question all along. Turn the identity round now and ask a different question. When do two of these counts, taken from the same number of objects, come out equal? There are two ways it can happen, and only two. Either you were choosing the same number both times, which is not interesting.

2:56Or the two numbers you were choosing add up to the number of objects available - which is the identity we have just been through. That claim is worth testing rather than believing. Over collections of up to twelve objects there are forty-two pairs of different lower numbers whose counts agree. Every single one of the forty-two has its two numbers adding up to the number available. And it runs the other way as well: whenever they do add up, the counts really do agree.

3:30So there is no third way for two of these counts to collide. Which turns a fiddly problem into a single line. Here is the problem. For some number of objects, choosing nine and choosing eight give exactly the same count. How many objects are there, and what is the count when you choose all of them? The long route writes both sides as factorial quotients, cancels what they have in common, and lands on a linear equation.

4:02Solve it and you get seventeen. The short route is this. Nine and eight are different numbers, so they must be the pair that adds up to the total. Nine and eight make seventeen, and that is the answer. Same result, one line, nothing cancelled. And then choosing all seventeen of the seventeen can be done in exactly one way - take the lot. The same shortcut settles another one immediately: if choosing eight and choosing two give the same count, there are ten objects, and the count is forty-five.

4:40Which is the number we were looking at two scenes ago. Now the second identity, and it is a different kind of statement altogether. It does not say that two counts are equal. It says that one count is built out of two smaller ones. Choosing three from five is ten. Choosing two from five is also ten. Add those together and you get twenty - which is exactly the number of ways of choosing three from six.

5:12Say that carefully, because it is easy to garble. The two lower numbers stay where they are, three and two. It is the number of objects available that goes up by one. Lay the counts out in rows, one row for each number of objects, and something becomes visible. Every entry inside the array is the sum of the two sitting just above it. All fifteen of the inside entries, for collections up to six objects.

5:44There is an algebraic proof of that, and it is four moves long. Write both counts as factorial quotients. Pull out the part they have in common, which leaves one over r inside one bracket and one over n minus r plus one inside the other. Add the two fractions, and the numerator collects into n plus one. And what you are left with is the quotient for the larger collection.

6:13Every one of those four expressions is the same number, checked at twenty-one different shapes. So the proof is correct. And if you forget it under exam pressure, you have got nothing. It confirms that the identity holds. It does not tell you why it had to hold. Here is why it had to. You have six objects and you are choosing three of them. Single out one of the six - any one at all, it does not matter which.

6:44Now put a single question to every selection: are you taking that object, or are you not? Every selection answers, and every selection answers exactly one way. If it takes the object, then its other two come from the remaining five, and there are ten ways to do that. If it leaves the object alone, then all three come from the remaining five, and there are ten ways to do that.

7:13So the twenty selections fall into a pile of ten and a pile of ten. And those are not merely the right sizes - look at what is actually in them. Drop the singled-out object from every member of the first pile, and what you have is exactly the choices of two from five: all ten of them, nothing extra and nothing missing. The second pile is exactly the choices of three from five.

7:41That is the whole identity, and it is one question asked once. That argument leaned on something worth naming, because it is where splits like this go wrong. Two conditions. Nothing may fall into both piles. And nothing may fall outside both. Miss either one and adding the parts together is simply not allowed. Here are two splits that fail, one each way. Take four cards from a pack, and split them into hands holding an ace and hands holding a king.

8:17A single hand can hold both of those, so the two cases overlap, and adding them counts some hands twice. Now split instead into hands that are all red and hands that are all black. Nothing is in both of those - but almost everything is in neither, so adding them misses most of the pack. The in-or-out question passes both tests by construction, and that is exactly why it works.

8:48One more distinction before the cards, because two different operations are about to turn up in one problem. Choose three people from a group of two men and three women. Three from five is ten ways in all. Split those ten by how many men they contain - no men, one man, or two men. One, six and three, and they add straight back to ten. Now look at the middle case on its own: one man and two women.

9:17There are two ways to pick the man and three ways to pick the women, and here you multiply. Six. Which is the six the split had already found. The multiplying is safe here for a specific reason, and it is worth saying out loud. Whichever man you took, the women are still being chosen from the same three. When the later count depends on which choice you made earlier, you may not multiply.

9:47Four cards, drawn from a pack of fifty-two. Thirteen cards in each of four suits, and twenty-six of each colour. With no restriction at all there are two hundred and seventy thousand, seven hundred and twenty-five hands. Now five restrictions. All four from a single suit: choose the suit four ways, then four of its thirteen cards - two thousand, eight hundred and sixty. One card from each suit: four independent stages of thirteen, multiplied together - twenty-eight thousand, five hundred and sixty-one.

10:26All four drawn from the twelve court cards: four hundred and ninety-five. Two red and two black: three hundred and twenty-five ways to take two of the twenty-six reds, and the same for the blacks, multiplied - a hundred and five thousand, six hundred and twenty-five. And all four of one colour: twice the fourteen thousand, nine hundred and fifty ways of choosing four from twenty-six - twenty-nine thousand, nine hundred.

10:59Now the best thing in this topic, and it is something you can check for yourself every time. Look again at those last two answers. Two red and two black was a hundred and five thousand, six hundred and twenty-five. All four the same colour was twenty-nine thousand, nine hundred. Those are two of the possible colour splits, and there are exactly two more. Three red with one black, and one red with three black.

11:29Each of those is the two thousand, six hundred ways of choosing three of the reds, times the twenty-six blacks - sixty-seven thousand, six hundred, and the same again the other way round. Now add all four of them. A hundred and five thousand six hundred and twenty-five, plus twenty-nine thousand nine hundred, plus sixty-seven thousand six hundred, twice. Two hundred and seventy thousand, seven hundred and twenty-five. Which is the unrestricted count you started from.

12:05That is not a coincidence and it is not decoration. A split that recovers the whole is a split with no overlap and no gap, and that is the same property the addition rule needed. You can test your own case splits this way, every single time, and it costs one addition. Two identities, then, and two kinds of reason for them. The first one: choosing what you keep and choosing what you discard are a single act, so the two counts were never two counts.

12:40The second one: single out an object and ask every selection whether it takes that object - two piles, no overlap, no gap. Both of those have algebraic proofs, and both of the proofs are correct. But an algebraic proof answers the question, is this true. The counting arguments answer a different question: why did it have to be. And that is the one you can rebuild out of nothing, at the moment you need it.