The closed formula, and how allowing repeats changes the count entirely

0:00You already have a way to count arrangements. Fill three places from six objects and the answer is six times five times four. It is correct and quick, and the trouble only starts when the count has to go inside an equation. Suppose you are told that filling five places from some unknown number of objects gives forty-two times what filling three places gives, and you have to find the number.

0:29Write both counts as products that stop part-way and there is no clean way to divide one by the other: they share their opening factors, but neither has a bottom half to cancel against. So the count gets rewritten. Not to make it a better count, but to give it a shape that algebra can get hold of. Here is the whole move, on six objects and three places. The product is six times five times four. The factors it never reached are three, two and one.

1:04Multiply the product by those three factors, and divide by them again in the same breath. You have changed nothing: multiplying and dividing by the same thing is harmless. But look at what the top has become. Six times five times four times three times two times one is every whole number from one to six. That is six factorial. And the bottom is three times two times one, which is three factorial.

1:36So the count is six factorial over three factorial: seven hundred and twenty divided by six, which is a hundred and twenty. The same hundred and twenty you would have got from six times five times four. There are three routes to this number, and they are worth keeping apart. You can build the arrangements: actually put objects into places, one at a time, and count what you made. You can take the product that stops part-way, six times five times four.

2:12Or you can take the quotient of two factorials, six factorial over three factorial. Score all three against each other on every pair of n and r with n up to six. That is twenty-eight pairs. The pairs where the built count and the quotient disagree: none. The pairs where the built count and the stopped product disagree: none. So the claim is not that the new expression is better arithmetic. It is that it is the same arithmetic wearing a different coat.

2:49Then why bother? Because a quotient can be cancelled against another quotient, and a product that stops in the middle cannot. Take the five-place count divided by the three-place count, for the same n. As quotients, the n factorial on top of each is the same, so it goes, and most of what is underneath goes with it. What survives is n minus three, times n minus four. Nothing else does.

3:18Check that against the counts themselves at every n from five to twelve, and the two agree at every one. That is the entire purchase. Not a faster count, a cancellable one. And nobody ever evaluates both factorials. Filling five places from fifty-two objects has fifty-two factors on top and only five survive the cancelling, giving three hundred and eleven million, eight hundred and seventy-five thousand, two hundred. Now push the new shape to its ends, where a formula tells you what it really is.

3:59Set r equal to n - you are using every object you have - and the bottom becomes nought factorial. Take four objects into four places. Build them by hand and there are twenty-four. Now the formula, with three different values for nought factorial. If it were nought, the expression divides by nothing and gives no answer at all. If it were two, it gives twelve. Half of what is actually there.

4:28If it is one, it gives twenty-four, which agrees with what was built. So the stipulation from before is not decoration here. It is load-bearing, and this is the beam it carries. The other end is stranger. Set r to nought: you are being asked how many ways there are to arrange none of the objects. Argue it in words before touching the formula. To arrange none of them is to leave the whole collection where it is, and there is one way to do that.

5:03Not nought ways. Doing nothing is a thing you can do, and there is exactly one of it. Build it and the arrangement with no places in it is one arrangement. Now check the formula. At r equals nought it gives n factorial over n factorial, which is one. The two agree. Notice the direction. The count was argued and the formula was checked against it, not the other way round.

5:33And notice that this end does not depend on the value of nought factorial at all. Only the r equals n end did. Which means the range you usually see written, r from nought up to n, is two different things stitched together. The upper part was derived. The lower endpoint was decided on counting grounds and then confirmed. So much for the shape. Now change the problem itself, by exactly one clause.

6:06Every count so far has assumed no object is used twice. Drop that. Draw four places twice, and under each row write how many objects stand untouched as each place is filled. With no reuse, that reads four, three, two, one. Every choice you make removes something from the supply. With reuse allowed, it reads four, four, four, four. Nothing is consumed, so nothing shrinks. That is the entire difference. One clause, one row of numbers.

6:41And the counts it gives are twenty-four and two hundred and fifty-six. The result for the reuse case is often left to the reader. It is short, so here it is. The first place can be filled in n ways, because every object is available. Whatever you put there is still available, so the second place can also be filled in n ways. And the third. And every place after it.

7:10There are r places and each one is worth a factor of n, so the count is n multiplied by itself r times. That is the only thing that changed: the factor no longer falls. It stays where it started. Score it: build every arrangement of four places from four objects with reuse allowed, count them, and compare with four multiplied by itself four times. Both come to two hundred and fifty-six.

7:42It is easy to assume the two counts are roughly the same. They are not. Four places from four objects: twenty-four against two hundred and fifty-six, a factor of thirty-two over three. Three places from six objects: a hundred and twenty against two hundred and sixteen. A factor of nine over five. Enormous in one case and small in the other, and the reason is in the two rows of widths.

8:13Allowing reuse switches off the shrinking. Where r is close to n the supply had a long way to fall, so switching that off changes a great deal; where r is small the early factors barely shrink at all, and there is much less to switch off. Now the counts this actually gets used for. Four-digit numbers built from the digits one to nine with no digit used twice: nine times eight times seven times six, three thousand and twenty-four.

8:48Now one worth learning as a habit: numbers between a hundred and a thousand, built from the digits nought to five with no digit twice. Count every three-place arrangement of six digits first: a hundred and twenty. Some of those open with nought, and nought nine two is not a three-digit number. So count the bad ones and take them away. With nought fixed in front, the other two places are filled from the remaining five digits: twenty.

9:22A hundred and twenty take away twenty is a hundred. Counting what you do not want is the standard move whenever the unwanted set is the easier one to describe. Back to the equation this all started with: the five-place count is forty-two times the three-place count. Find n. In the closed shape this now divides. The left side over the right gives n minus three, times n minus four, and that has to equal forty-two.

9:56Expand and you have a quadratic: n squared minus seven n minus thirty equals nought. Search the whole numbers for its roots and you find two: minus three, and ten. Minus three is not a number of objects, so it goes. Ten is the answer, and it checks: both sides come to thirty thousand two hundred and forty. One more of the same kind. The four-place count from n objects, divided by the four-place count from one fewer, equals five over three - and the only n from five to twelve that satisfies it is ten again, where the two counts are five thousand and forty and three thousand and twenty-four.

10:43Now the one that matters, and it is about what an equation is entitled to. Solve this: five times the r-place count from four objects equals six times the count from five objects with one place fewer. The cancelling goes through and you reach six minus r, times five minus r, equals six. Expand: r squared minus eleven r plus twenty-four equals nought. Search for whole-number roots and you get two: three and eight.

11:17It is very easy to stop there and report both. Do not. Take r equal to three back to the original equation. Five times twenty-four is a hundred and twenty. Six times twenty is a hundred and twenty. It holds. Now take r equal to eight back to the original equation. The left side asks you to fill eight places from four objects. You cannot. You run out at the fifth place, because there is nothing left to put in it.

11:50So the left side does not name a number there. Neither does the right. The equation at r equal to eight is not false. It is unsaid. The quadratic is a consequence of the equation, not the same thing as it. Every solution of the equation is a root of the quadratic; the reverse is not guaranteed, and here it fails. So the range comes back at the end, not at the beginning: r at most n, and r at least nought. Roots outside it were never candidates.

12:27If that felt like a one-off, it is not. The r-place count from five objects equals twice the count from six with one place fewer. Its quadratic gives three and ten; the equation holds at three, and at ten neither side names anything. Drop the doubling and solve again. That quadratic gives four and nine; the equation holds at four, and at nine it names nothing. Three problems, three quadratics, six roots, three answers - and every discarded root is discarded for the same reason. Not because it makes the equation false, but because there the equation has nothing to say.

13:13One more family, and it hides a real trap in the wording. Take an eight-letter word with all its letters different, three of them vowels: every arrangement of it is forty thousand three hundred and twenty. How many keep the three vowels together in one block? Treat the block as a single object. That leaves six objects to arrange, seven hundred and twenty ways, and six orders for the vowels inside the block: four thousand three hundred and twenty.

13:47That was an argument. Check it by looking: go through all forty thousand arrangements and count the ones whose vowels landed in consecutive places. The same four thousand three hundred and twenty. Now the question that traps people. How many arrangements do not have all the vowels together? That is the negation of what we just counted, so it is everything else: forty thousand three hundred and twenty minus four thousand three hundred and twenty, which is thirty-six thousand.

14:23But read what that includes. Arrangements where two vowels sit side by side and the third is elsewhere do not have all three together, so they count. It is not the number with no two vowels touching. That is a different and smaller question: fourteen thousand four hundred. The gap between them is twenty-one thousand six hundred arrangements with exactly two vowels adjacent - not all three together, and not no two together either.

14:55Not all of them together is a much weaker condition than none of them together, and the wording will not warn you. So, what to carry away. The closed form is the same count: the tail was multiplied in at the top and divided straight out at the bottom, and the value never moved. It was worth doing because a quotient cancels inside an equation and a stopped product does not.

15:26Allowing an object to be reused divides by nothing. It stops the supply shrinking, so every factor stays at n and the count goes up. And when an equation hands you a quadratic, the quadratic is a consequence, not a substitute. Take every root back to the counts it came from, and keep only the ones those counts can name.