Counting Gets Interesting When Things Start Repeating

One thing I keep running into as I dig deeper into discrete math is how deceptive "simple" counting problems can be. You think the answer is obvious, you write down a formula that makes total sense, and then — it's wrong. Not because the logic was bad, but because the counting was subtly off.

The core issue: when objects repeat or overlap, naive counting breaks down. And the techniques for fixing it — complement counting, the quotient rule, bijections — turn out to be some of the most reusable ideas in all of combinatorics.

So in this post, I wanted to walk through the progression from basic string counting to permutations to anagrams, because it's a journey from "this is easy" to "wait, why is this so tricky?" to "oh, that's actually elegant."

Counting "at least one" by removing what you don't want

Here's a classic problem: how many 8-character passwords (using digits, lowercase, and uppercase letters) contain at least one uppercase letter?

The direct approach — pick an uppercase letter, pick a position, fill the rest — sounds right. But trying to count "at least one" directly is messy. There's a cleaner way.

The trick is complement counting: count everything, then subtract the ones you don't want.

The first term is every possible 8-character password — 62 characters (digits + lowercase + uppercase), 8 positions, each position can be anything. The second term is passwords with no uppercase at all — only 36 characters available per position. Subtract, and you're left with exactly the ones that have at least one uppercase letter.

This works because the "at least one" condition is hard to count directly, but "none at all" is easy. The complement does the heavy lifting.

The overcounting trap

Now here's the wrong answer that looks really convincing:

The logic: pick one of 26 uppercase letters, pick one of 8 positions for it, fill the remaining 7 positions with anything. That sounds perfectly reasonable. But it's wrong — and the reason is overcounting.

What this expression actually counts is 3-tuples: (uppercase letter, position, 7-character string). But a single password with multiple uppercase letters gets generated by more than one 3-tuple. The string "FA65B227" can be produced by choosing F for position 1 or by choosing A for position 4 — two different 3-tuples, one string.

Here's a dead giveaway that something is wrong: 26 × 8 × 62⁷ is actually larger than 62⁸, which is the total number of all possible passwords. You can't have more passwords with at least one uppercase than passwords total.

This is a common trap. If the mapping from your constructed objects to your desired set isn't one-to-one (a bijection), you're overcounting.

Practice: four-digit strings with at least one zero

Same idea, smaller scale. How many four-digit strings (using 0-9) have at least one zero?

There are multiple correct answers — and that's part of what makes this interesting.

Approach B: Complement counting

Total strings minus strings with no zeros. Clean and direct.

Approach C: Count by number of zeros

This uses the sum rule — partition the set into non-overlapping categories (exactly 1 zero, exactly 2, exactly 3, exactly 4) and add them up. The 6 in the second term represents "4 choose 2" — the number of ways to choose which 2 of the 4 positions get zeros. We'll see combinations formally in a future post, but the idea is intuitive.

Approach D: Count by position of the first zero

If the first zero is in position 1: the remaining 3 positions can be anything (10³). If the first zero is in position 2: position 1 must be non-zero (9), the rest can be anything (10²). And so on.

Three correct approaches, three wildly different-looking expressions, all equal to 3,439. Every time you find a new way to count the same set, you get a mathematical identity for free. The counting argument proves the algebra.

Approach A: The wrong one

4 × 9³ = 2916. This counts strings with exactly one zero — it picks a position for the single zero and fills the rest with non-zero digits. It's not wrong as a formula; it just answers a different question. It misses strings with 2, 3, or 4 zeros.

From strings to candy: bijections as a counting tool

Here's a problem that looks nothing like string counting: how many ways can you distribute 10 different candies to 4 different children?

The candies are distinct (Twix, Skittles, M&M's...). The children are distinct. Every candy goes to exactly one child. Any child can get zero, one, or all ten.

The answer is 4¹⁰. And the reason is a bijection — a one-to-one mapping to something we already know how to count.

Think of it this way. Build a string of length 10 over the alphabet {A, B, C, D}. Each position represents a candy. The character at that position tells you which child gets it.

The string "DDCADACCAA" corresponds to exactly one distribution: child D gets Twix, M&M's, and Three Musketeers; child C gets Skittles, Mounds, and Almond Joy; child A gets Kit Kat, Snickers, Reese's, and Hershey's; child B gets nothing.

Every distribution maps to exactly one string, and every string maps to exactly one distribution. That's a bijection. So the number of distributions equals the number of strings of length 10 over a 4-character alphabet: 4¹⁰ = 1,048,576.

The power of bijections is that they let you transform a confusing counting problem into a familiar one. If you can show the mapping is one-to-one and onto, the sizes must be equal.

Permutations: when repetition isn't allowed

Strings over an alphabet allow repeats — you can use the same character multiple times. But what if each character can only appear once?

How many 3-letter strings can you make from {A, B, C, D, E} with no repeats?

Each time you fill a position, you have one fewer character available. Position 1: 5 choices. Position 2: 4 choices. Position 3: 3 choices. Total: 5 × 4 × 3 = 60.

This is called a permutation — specifically, an r-permutation where r is the number of positions you're filling.

The general formula

The number of ways to arrange r objects from n distinct objects:

This product has exactly r factors. You can also write it as:

where n! = n × (n-1) × (n-2) × ... × 1 is the factorial of n.

The factorial form works because the denominator (n-r)! cancels out the "tail" of the factorial that we don't need. For example:

Try it yourself — change n and r below:

When r equals n: arranging everything

When you're arranging all n objects (not just a subset), you get:

Using the formula:

For this to give us n!, we need 0! = 1. And there are two good reasons for that convention:

1. Algebraic: it makes the formula work. Without 0! = 1, you'd need a special case for r = n.
2. Combinatorial: how many ways can you arrange zero objects? Exactly one — do nothing. There's only one empty arrangement.

The convention isn't arbitrary. It's the only value that makes both the algebra and the combinatorics consistent.

Anagrams: what happens when letters repeat

Permutations assume all objects are distinct. But what if some are identical? That's where anagrams come in — rearrangements of a collection that may contain repeated elements (a multiset).

All distinct: MILES

The letters M, I, L, E, S are all different. The number of anagrams is just 5! = 120.

Some of them happen to be real words: Miles, Slime, Limes. But we're counting all rearrangements, not just English words.

One repeat: EETS

Now consider the letters E, E, T, S. If all letters were distinct — say, E₁, E₂, T, S — there would be 4! = 24 permutations.

But since the two E's are identical, swapping E₁ and E₂ produces the same string. For every distinct anagram, there are 2! identical-looking permutations.

We can verify by listing them all — 4 starting with each of the non-E letters (S and T), and 4 more starting with E but differing in the remaining positions:

That's 6 + 3 + 3 = 12. The formula gives us 4!/2! = 12, which checks out.

The point is the strategy: make duplicates distinct, count everything, then divide by the number of ways those duplicates can be rearranged internally.

Multiple repeats: ASSESSOR

This is where the formula really shines. A-S-S-E-S-S-O-R has 8 letters:

Applying the formula:

The general formula is:

where N is the total number of letters, and k₁, k₂, ..., kₘ are the counts of each distinct letter.

A nice consistency check: the sum of all the kᵢ values must equal N. For ASSESSOR: 4 + 1 + 1 + 1 + 1 = 8. If that sum doesn't match, something's wrong with your frequency count.

The coloring trick

Here's the mental model that makes this click. Take ASSESSOR and color each S a different shade — S₁ in red, S₂ in blue, S₃ in green, S₄ in orange. Now all 8 characters are distinct, so there are 8! permutations.

But every real anagram corresponds to multiple colored permutations — specifically, 4! of them, because you can rearrange the 4 colored S's among themselves without changing the actual string.

This is called the quotient rule — you expand to an easier set, count that, then divide by the size of each equivalence class (the number of "duplicates" per real element).

Try it yourself

Type any word below and see the anagram count update in real time:

The visualization colors each letter group distinctly and shows the full formula breakdown. Try words with more repeats (like "MISSISSIPPI") to see how dramatically the count drops compared to N!.

The quotient rule is everywhere

The anagram formula is one instance of a broader technique: counting by categories.

1. Expand to a larger, easier-to-count set (e.g., treat identical objects as distinct)
2. Count that expanded set
3. Divide by the number of elements in each category that correspond to a single element in the original set

This pattern shows up everywhere — counting geometric shapes with symmetry, counting chemical compounds with identical atoms, counting arrangements of cards in hands where suit order doesn't matter. The strategy is always the same: make things different, count, then account for the symmetries.

A few things I'm taking away

• Complement counting is often the cleanest way to handle "at least one" conditions — count everything, subtract what you don't want
• Overcounting happens when your construction can produce the same object multiple ways — always check if your mapping is a bijection
• A quick sanity check: if your "at least one X" count exceeds the total count, something is wrong
• Multiple correct approaches to the same problem give you mathematical identities for free — the algebra must agree because the sets are the same
• Bijections let you transform an unfamiliar counting problem into a familiar one — if the mapping is one-to-one and onto, the counts must match
• Factorials count arrangements of distinct objects: n! ways to arrange n things
• 0! = 1 is both algebraically necessary and combinatorially natural — there's exactly one way to arrange nothing
• Permutations P(n, r) count arrangements of r objects from n, with each factor representing one fewer available choice
• Anagrams of a multiset use the quotient rule: N! divided by the product of the repeat-group factorials
• The coloring trick is the key insight — make identical things distinguishable, count, then divide out the symmetries
• When the denominator factorials sum to the numerator, you know you've accounted for every letter
• The quotient rule generalizes beyond anagrams to any situation where you can expand to an easier set and divide by equivalence class size

That last one — the quotient rule — is the pattern I keep seeing come back. It's the same idea whether you're counting anagrams, symmetries of geometric shapes, or arrangements where certain positions are interchangeable. Make things different when that makes counting easy, then divide out the sameness. Once you see it, you start noticing it everywhere.