Recipe
Divide out a uniform overcount
Use when: you have (or can compute) a naive count that treats genuinely identical outcomes as different, and suspect every real outcome got duplicated the same number of times
Goal: the exact true count, valid only once the overcount is confirmed uniform
Taught in Overcounting and dividing out
Quick recipe
-
1
Before dividing anything, confirm that every genuine outcome gets duplicated by the same fixed amount under the naive count, not just some of them.
Example
Arrange the 4 letters of LULU in a row, treating all 4 tiles as distinct for now (24 orderings). Swapping the two L tiles never changes how the word looks, and that holds for every one of the 24 orderings, not just a few. Swapping the two U tiles has the same property.
- every outcome duplicated by the same fixed amount — continue to Step 2.
- the duplication amount varies from outcome to outcome — stop; dividing by a single number would be wrong here, and a different tool (such as Burnside's lemma, later in this course) is needed instead.
Why: dividing by a number that isn't the true, constant overcount factor produces a result that isn't the count of anything real.
-
2
Identify every independent source of duplication and combine them; each source contributes its own multiplier.
Example
The two L's can be swapped 2! ways with no visible change, and independently the two U's can be swapped 2! ways with no visible change. The two sources multiply: r = 2! \times 2! = 4.
Why: r has to be exact, not estimated, since the whole method depends on dividing by precisely that number.
-
3
Compute N/r using the naive count N and the factor r found in Step 2.
Example
24 / 4 = 6.
Why: dividing by r removes exactly the duplicate copies that uniform overcounting created, leaving each genuine outcome counted once.
-
4
List the distinct outcomes directly for a small enough case and confirm the count from Step 3 matches.
Example
The 6 distinct arrangements of LULU are LLUU, LULU, LUUL, ULLU, ULUL, and UULL. Listing them confirms the count of 6.
Why: a direct listing catches a wrong overcount factor before it propagates into a problem too large to list by hand.
Common mistakes
- Assuming the overcount is uniform without checking; some counting problems genuinely have a duplication amount that varies by outcome.
- Accounting for only one source of duplication (only the L swaps, say) and forgetting a second independent source (the U swaps) that also needs to be folded into r.
- Confusing the number of ways to arrange the repeated items with the overcount factor itself; they're the same number here, but that's specific to this kind of problem, not a general identity.
- Getting the naive count N itself wrong before dividing, so a correct division still lands on the wrong final answer.