Basis Lab

Answers · The mathematics underneath

How come lining up only some of the things still involves factorials?

In shortBecause you multiply only the choices for the places you fill, so a partial line-up is a factorial with the unused tail divided out.

The number of ordered line-ups of kk things chosen from nn is n(n−1)⋯(n−k+1)n(n-1)\cdots(n-k+1), which is n!n! divided by (n−k)!(n-k)!. The division is not arbitrary: (n−k)!(n-k)! is the number of orders of the things you left on the table, and those orders were never part of the count. You are not correcting a mistake in the multiplication. You are removing a set of orderings that the full factorial included only because it lined up every item.

n(n−1)⋯(n−k+1)=n!(n−k)!n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}

Three medals from ten

Ten runners, three different medals. The first medal has ten candidates. Once that runner is chosen, the second has nine. Once both are chosen, the third has eight. The product is 10×9×8=72010\times9\times8=720. It stops after three factors because there are only three places to fill. A full line-up of all ten would be 10!=10×9×8×7×6×5×4×3×2×1=3,628,80010!=10\times9\times8\times7\times6\times5\times4\times3\times2\times1=3{,}628{,}800. That larger number counts an order for every runner, including the seven who won nothing.

The stopping product is not a different rule. It is the multiplication rule with the options running out at three places instead of ten. The first place has ten options, the second has nine, the third has eight, and there is no fourth place, so the next factor is never multiplied. The number of factors equals the number of places filled, so a partial line-up is a factorial cut short rather than a factorial altered. This is why the answer is smaller than 10!10! but still built from the same descending factors. Nothing was divided yet; the product simply stopped.

The tempting repair is to take 10!10! and divide by 3!3!, because three medals were awarded. That gives 10!/3!=3,628,800/6=604,80010!/3!=3{,}628{,}800/6=604{,}800, which is not 720720. Dividing by 3!3! would be the repair for three indistinguishable medals, not for leaving seven runners out. The seven non-medalists are not arranged as first, second and third leftovers. They are simply the rest of the field, with no order attached.

10!3!=3,628,8006=604,800,10!7!=3,628,8005,040=720.\frac{10!}{3!}=\frac{3{,}628{,}800}{6}=604{,}800,\qquad \frac{10!}{7!}=\frac{3{,}628{,}800}{5{,}040}=720.

What the denominator removes

For every medal result, the seven remaining runners can be ordered in 7!7! ways. Since 7!=7×6×5×4×3×2×1=5,0407!=7\times6\times5\times4\times3\times2\times1=5{,}040, each genuine medal line-up is counted 5,0405{,}040 times by the full factorial. Dividing by 7!7! collapses those copies back to one. The quotient is not a correction invented to make the answer smaller; it is the exact overcount. The denominator is the size of the group whose internal order you decided not to care about. That group is the leftovers, not the medal places.

Take one medal result: A first, B second, C third. The full factorial counts A, B, C, D, E, F, G, H, I, J and A, B, C, J, I, H, G, F, E, D as different, because the last seven are in different orders. Both give the same three medals. For each medal result there are 5,0405{,}040 such tail orders, so the full count is 5,0405{,}040 times too large. Divide and the tail disappears.

10!7!=10⋅9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅17⋅6⋅5⋅4⋅3⋅2⋅1=10⋅9⋅8=720.\frac{10!}{7!}=\frac{10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}=10\cdot9\cdot8=720.

Why the factorial keeps appearing

The top factorial is the full pile. The bottom factorial is the untouched pile. Stopping the product before the untouched pile is the same as dividing by the number of orders inside that pile. If you fill five of ten places, the product is 10×9×8×7×6=30,24010\times9\times8\times7\times6=30{,}240, and the quotient is 10!/5!=3,628,800/120=30,24010!/5!=3{,}628{,}800/120=30{,}240, because the five leftovers have 5!5! internal orders. The shape is always the same: full factorial over leftover factorial, with the number of filled places deciding where the tail is cut.

If all ten are lined up, the untouched pile is empty and 0!=10!=1, so the quotient is 10!/0!=10!10!/0!=10!, as it should be. If the seven leftovers did have to be ordered, then the problem is a full line-up of ten and the answer is 10!10!, not 10!/7!10!/7!. If some of the three chosen are identical, a further division is needed for their swaps. The partial factorial rule assumes the chosen items are distinct and that their order matters; if either assumption fails, the denominator changes.

Worth keeping

  • A partial line-up is the full factorial divided by the factorial of the items left unordered, because those leftovers were never arranged.
  • Dividing by the number of filled places is wrong: the leftovers, not the places, are what the full factorial overcounts.
  • If the leftover items do have to be ordered, then the problem is a full line-up and the denominator disappears.

Where this goes next

This question is one step of Counting Without Listing, a course that works through its subject from the beginning. The page that teaches this part of it is Putting Things in Order, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that pageThe whole course

Other questions people ask about this

  1. Why is 0! equal to 1?Zero factorial is one because there is exactly one way to arrange nothing: the empty arrangement, with nothing left to place.
  2. Why do I divide by k! when the order doesn't matter?You divide by the number of ways to order the chosen items, because the ordered count listed every chosen group that many times.
  3. How does having more items than slots guarantee that two of them share a slot?If you put more items into fewer slots, at least one slot must hold two, because if every slot held at most one you could not fit them all.
  4. Why do I have to subtract the overlap when I add two groups together?Because anything in both groups gets counted twice, so you take one copy back out to leave it counted once.
  5. What is the difference between variance and standard deviation?They measure the same spread: variance is the average squared distance from the mean, standard deviation is its square root, so you report the standard deviation and calculate with the variance.
  6. How do you make a vague claim precise enough to tell whether it's true?Fix what is being talked about, what is asserted, which cases are covered and the cut-off, then name an observation that would prove it false.

Read alongside