Filling a row of places one at a time from a supply of distinct objects

0:00Nothing new gets counted here. Something already counted gets a name. Take six unlike letters and fill three places from them, using no letter twice. There are a hundred and twenty ways. Take four unlike letters and fill four places. Twenty-four ways. Both of those are arrangements: objects put into places, one to a place, in a definite order. And the important half of that is the word some. An arrangement does not have to use everything you were given.

0:35Three places filled from six letters leaves three letters unused, and it is still an arrangement. So there is a symbol for it, written n P r, and there is a rule for working it out. The rule is short, and one small piece of it is where everybody goes wrong. That piece is what this is about. First, what definite order buys you. It does not mean alphabetical, and it does not mean sorted by size. It means that two different sequences of the same objects are two different things.

1:12Here is what that is worth. Of those hundred and twenty three-letter arrangements, how many use exactly the letters M, N and U? Six. M N U, M U N, N M U, N U M, U M N, U N M. Same three letters every time. Six different arrangements, because the order is part of the answer. And how many different trios of letters turn up at all, across the whole hundred and twenty? Twenty.

1:43Every one of those twenty appears in exactly six arrangements. Twenty groups of six. Which comes to a hundred and twenty, and that is worth holding on to, because a later problem is exactly this one with the six taken back out. Now build the hundred and twenty, with no rule at all. Just three empty places and a supply of six letters. The first place can take any of the six.

2:14Whatever went in there, that letter is spent. The second place has five letters left. And the third has four. Six, then five, then four. Every first choice leaves the same number open at the next place, so those multiply, and the answer is a hundred and twenty. Change one thing. Allow a letter to be used again, and every place has all six available. Six times six times six. Two hundred and sixteen, which is ninety-six more than before.

2:50Ninety-six arrangements that exist only because you were allowed to repeat. From here on, no repeats. Now the general rule, and the claim it makes is very specific. You have n unlike objects and r places to fill, one object to a place, nothing used twice. The count is a product. It starts at n, and each factor is one less than the one before it. And it stops at n minus r plus one.

3:23That last expression is the entire content of the rule. Everything else is obvious. Starting at n is obvious. Falling by one each time is obvious. Where to stop is not obvious, and it is where the mistake lives. So the rest of this is one question: why does the product stop at n minus r plus one, rather than at n minus r? The answer comes from the boxes, not from the algebra.

3:55Draw the r places as a row, and under each one write how many objects are still standing, untouched, at the moment you fill it. Before the first place, nothing has been used. The supply is n. Before the second place, one object is gone. The supply is n minus one. Before the third, two are gone. So before place k, exactly k minus one objects have been spent, and the supply is n with that many taken off it.

4:28Those numbers under the boxes are the factors. There is no separate formula: the product is just the supply, read off left to right. And it does not matter which object you spend. Take the first one each time, or the last one, or one from the middle, and the numbers under the boxes come out six, five, four every time. The contents change. The count does not, which is exactly the condition that lets you multiply at all.

5:03Now go to the last box, the rth one, and ask what is standing in front of it. You have filled r minus one places. So r minus one objects are gone, not r. So the supply is n with r minus one taken off it. And n with r minus one taken off it is n minus r plus one. That is the whole of it. The plus one is not a correction bolted onto the formula. It is there because the last place has not been filled yet when you count the supply in front of it.

5:41Watch what happens if you get it wrong. Six letters, three places. The right factors are six, five, four, and they multiply to a hundred and twenty. Stop at n minus r instead and the factors are six, five, four, three, which multiply to three hundred and sixty. Three times too large. And the three is not a mystery: it is the extra factor itself, sitting on the end where it does not belong.

6:13There is a way to catch that without doing any arithmetic at all. You have r places. Each place contributes exactly one factor. So the product has r factors. Always, whatever n is. Six letters into three places gives three factors. Not four. Anyone who stops at n minus r produces four factors for three places, and you can see that at a glance. This is checkable across the board, not just in one example.

6:46Take every pair of n and r where the rule applies, with n up to seven. There are twenty-eight of them. For all twenty-eight, the right rule gives a factor count that matches r exactly. For all twenty-eight, the wrong one gives exactly one too many. Never two too many, never right. One, every single time. So counting the factors is not a rule of thumb. It catches that error everywhere it can occur.

7:18Which raises a fair question. If the error is that consistent, why does anyone survive it? Score the wrong rule against the true count on all twenty-eight pairs. It gets twenty-two of them wrong. So it fails most of the time, which is what you would expect. But it gets six of them right, and those six are not scattered. They are exactly the pairs where r is one below n.

7:46Look at why. When r is n minus one, the extra factor on the end is n minus r, which is one. And multiplying by one changes nothing. The product is wrong in its length and right in its value. That is a nasty way for an error to behave. Once per value of n, the wrong method quietly gives the right answer. If that is the case you happened to practise, nothing told you. Counting the factors would have.

8:19Two other rules people reach for, scored the same way. The first is that n P r means n times r. It gets twenty of the twenty-eight wrong. The ones it survives are every pair where there is only one place to fill, which is no achievement: one place, one factor, and that factor is n. There is exactly one other pair where n times r is right, and it is three objects into two places.

8:50Three times two is six, and three into two places really is six. A coincidence, and worth knowing it is one. The second is to always run the product all the way down to one. That gets fifteen of the twenty-eight wrong, and the thirteen it survives are exactly the pairs where you are using every object, or all but one. Every one of these rivals is right somewhere. That is why they persist. None of them is right everywhere, and only one of them is right for a reason.

9:27Take the case where r equals n: every object used, every place filled. The last factor is n minus n plus one, which is one. So the product runs all the way down to one, and for four letters into four places that is four times three times two times one. Twenty-four. Which is the number this started with, arriving a second time by a completely different route. And here is the sharpest illustration of why the factor count matters.

10:01Five objects, taken two at a time, then three, then four, then five. Twenty. Sixty. A hundred and twenty. And a hundred and twenty again. The last two counts are the same number. Their products are not the same product: one has four factors, the other has five. The fifth factor is one, because there is one object left and one place to put it in. Same value, different length, and the length is the thing that tells you which question you answered.

10:36Two edges. First, what happens if you ask for more places than you have objects. Four objects, six places. Fill the first four and the supply is empty. The procedure does not give you zero. It stalls, at the fifth place, because there is nothing left to put in it. That is why the rule carries the condition r at most n. It is not a technicality; it is the point at which the boxes run out.

11:07Ask for three places from two objects and it stalls at the third. Same reason, one step sooner. Second edge: what if r is nought? No places at all. There is exactly one way to fill no places, which is to do nothing, and that is a genuine arrangement of length nought. But the product for r equals nought has no factors in it whatsoever. Not a factor of one. No factors.

11:37There is nothing there to multiply, so the rule as usually stated asks for r strictly above nought. That is deliberate, not an oversight, and it gets settled properly later. So, the symbol. n P r: the number of ways to fill r places from n unlike objects. The n tells you where the product starts. The r tells you how many factors it has. That is all either of them does.

12:08It does not mean n times r. For nine and three, it is five hundred and four, not twenty-seven. And it is not a second method that competes with the boxes. It is a name for what the boxes give you. Nine digits, three places, no digit twice: nine times eight times seven, five hundred and four. If that number feels familiar, it should. It is the same count as three unknown wheels of a lock drawn from nine digits — a problem that looked nothing like this one.

12:44Two named posts filled from eight people, nobody holding both: eight times seven, fifty-six. Two places, two factors. The rule works. But writing out a product of, say, forty factors is not something anyone wants to do. Which is the next problem: the same count, written in a form you can actually handle.