Basis Lab

Answers · The mathematics underneath

Why do I divide by k! when the order doesn't matter?

In shortYou divide by the number of ways to order the chosen items, because the ordered count listed every chosen group that many times.

You divide by k!k! because the ordered count has already counted every chosen set k!k! times. Each set of kk items can be put in k!k! orders, and every set is overcounted by exactly that same factor, so one division removes the duplicates.

Take ten people and a committee of three. If you count with positions, you choose a first member in 10 ways, a second in 9, and a third in 8, so there are 10×9×8=72010\times9\times8=720 ordered triples. That count is not wrong as an ordered count; it is wrong as a committee count because the same trio is being counted several times. A fixed trio has 3 choices for which member is written first, 2 for which is written second, and 1 for the last, so it has 3!=3×2×1=63!=3\times2\times1=6 orders. The 720 therefore contains that trio six times. Dividing 720 by 6 gives 120, and every trio is repaired by the same division.

(103)=10×9×83!=7206=120\binom{10}{3}=\frac{10\times9\times8}{3!}=\frac{720}{6}=120

The numerator in the general formula is the same ordered count. Picking kk distinct items from nn in order gives nn choices, then n−1n-1, down to n−k+1n-k+1, so the product has kk factors. The denominator is k!k!, the number of ways to reorder those kk chosen items among themselves. The formula n!/(k!(n−k)!)n!/(k!(n-k)!) is the same statement with the numerator written as n!/(n−k)!n!/(n-k)!. The (n−k)!(n-k)! cancels the tail of n!n! that belongs to the items not chosen; the unchosen items never appear in the selection, so their order is irrelevant and must not be divided out.

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

Computing the formula is worth doing in the cancelling order. For 10 choose 3, write 10×9×810\times9\times8 over 3×2×13\times2\times1. Cancel 3 into 9 to get 3, and 2 into 8 to get 4, leaving 10×3×4=12010\times3\times4=120. The factorial form produces the same number, but the cancelled product keeps the intermediate numbers small and shows where the orderings have gone.

The natural guess is to divide by kk, or to stop after kk descending factors. Stopping after kk factors leaves the positions labelled first, second, third, so the overcount is still there. Dividing by kk removes only one label, not all orderings: for k=3k=3, 720/3=240720/3=240, which is still twice the true count of 120. The correct divisor is 3!=63!=6, because there are six orders of three items, not three. For larger kk the gap gets worse: 5!=1205!=120 orders of five items, not five.

Why the division is exact

The division is legitimate only because the overcount is uniform. If one trio were counted six times and another trio were counted four times, no single division by six could repair 720; the arithmetic would produce a number that counts neither ordered triples nor committees. For choosing kk distinct items from nn, uniformity is automatic: every subset of size kk has exactly k!k! orderings, no more and no fewer. That is the sentence to check before dividing. When it fails, split into cases where it holds and add.

A smaller check: choose two from five. Ordered picks give 5×4=205\times4=20. A fixed pair has 2!=22!=2 orders, because the two members can be written in two sequences. Dividing gives 20/2=1020/2=10. Listing the pairs agrees, but the arithmetic does not need the listing: the division is exact because every pair has the same two orders.

One free check is nn choose kk equals nn choose n−kn-k. Choosing which kk items go in is the same act as choosing which n−kn-k stay out, so the two counts must match. For instance 100 choose 98 equals 100 choose 2, which is 100×99/2=4950100\times99/2=4950. Counting the smaller side is usually easier.

Nor do you divide by the orderings of all ten people. The seven people left out never enter the committee, and their internal order cannot make a different committee. Only the chosen three have been arranged in the ordered count, so only their 3!3! orders need removing.

When the divisor is wrong

The rule stops being true when the selected items are not distinct or when repeats are allowed. If two chosen items are identical, swapping them does not create a new order, so that selection is overcounted by less than k!k!. Dividing the ordered count by k!k! then undercounts. The safe move is to split into cases with uniform overcount, or to use a count designed for repeated items. The divisor k!k! belongs to selections of kk distinct items, not to every selection problem.

Worth keeping

  • Every selection of k distinct items has exactly k factorial orderings, so the ordered count overcounts each selection by the same factor.
  • The divisor is k factorial, not k, because three items have six orders, not three.
  • A single division is valid only when every selection has the same overcount; otherwise split into cases.

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 When Order Does Not Matter, 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. How come lining up only some of the things still involves factorials?Because you multiply only the choices for the places you fill, so a partial line-up is a factorial with the unused tail divided out.
  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