[Intermediate] — Counting without enumerating, and the principle that proves compression limits and hash collisions in one line.

Why counting is a subject

“How many?” sounds trivial until the answer is and you need it without listing them.

Counting tells you how big a search space is, which tells you whether brute force is viable, how strong a password is, how likely a hash collision is, and how many test cases would be exhaustive.

The two basic rules

Product rule — independent choices multiply.

An 8-character password from 62 alphanumerics: .

Sum rule — mutually exclusive alternatives add.

Getting these two straight is most of elementary counting. “And” multiplies, “or” (disjoint) adds — the same structure as logic and probability, which is not a coincidence.

Permutations and combinations

Permutation — order matters:

Arrangements of items from . All : just .

Combination — order doesn’t:

The relationship: — divide out the orderings you’re now treating as the same.

The decision procedure, since this is where people slip:

Does order matter?
├── YES → permutation
└── NO  → combination

Can items repeat?
├── YES → nᵏ (ordered) or C(n+k−1, k) (unordered)
└── NO  → P(n,k) or C(n,k)

Identities worth knowing:

The middle one is Pascal’s rule — and it’s a recurrence, so it’s the DP formulation of binomial coefficients. The last one says the subsets of an -set number , counted by size, which connects straight back to power sets.

The pigeonhole principle

Trivially obvious, and it proves things that aren’t.

If items go into boxes, some box holds at least two.

Generalised: items into boxes forces some box to hold at least .

What it proves:

Hash collisions are unavoidable. A hash maps arbitrary-length inputs to fixed-length outputs. More inputs than outputs, so collisions exist — mathematically guaranteed, not a weakness of any particular function. A good cryptographic hash only makes them hard to find. → Hashing and Integrity

Lossless compression cannot shrink every input. There are strings of length and only shorter strings. Any injective map must send some inputs to longer outputs. Every “compresses anything by 50%” claim is provably false, and this is the one-line disproof.

In any set of integers from , two are coprime — a genuinely non-obvious result from a very obvious principle.

Two people in London have the same number of head hairs. Non-constructive: certainly true, and you’ll never know who. → Proof Techniques

Inclusion–exclusion

Counting a union without double-counting overlaps:

Alternating signs, and in general terms — which is why it’s elegant and often impractical for large .

Where it shows up: counting query results across overlapping conditions, derangements (permutations with no fixed point), and Euler’s totient function in number theory.

The birthday problem

The most practically important counting result for a programmer, because the answer is so much smaller than intuition suggests.

How many people before two share a birthday, with probability > 50%?

23.

At this drops below 0.5.

Why intuition fails: you’re not comparing yourself to 22 others — you’re comparing all pairs. Collisions scale with pairs, which is quadratic.

The general rule, and the one to remember:

The consequences are large:

HashOutput bitsBrute forceBirthday attack
MD5128 ← broken
SHA-1160 ← broken
SHA-256256

A hash with bits gives you only bits of collision resistance. This is why “128-bit hash” is not 128 bits of security against collisions, why SHA-1 fell, and why you need 256 bits of output for 128 bits of collision resistance. It’s a counting fact that dictates cryptographic parameter choices.

It’s also why UUID collisions are unlikely but not impossible (122 random bits → expect a collision around UUIDs), and why hash tables need collision handling at far lower load factors than naive reasoning suggests.

Counting and probability

Discrete probability is counting divided by counting, when outcomes are equally likely:

Which is why combinatorics comes first. Full treatment: Probability and Statistics.

The link worth noting: — the binomial distribution — is literally a combination times a product-rule probability. The counts which of the trials succeeded.

Where counting is applied

Security and passwords. Entropy is . A 12-character random password from 94 printable ASCII characters has bits. A memorable passphrase of 5 words from a 7,776-word list has bits — and is far easier to remember. Counting is how you compare them honestly. → Attacks and Threats

Complexity analysis. “How many subsets?” () “How many permutations?” () tells you immediately whether exhaustive search is possible. at is . → Complexity Classes

Hash table sizing. Expected collisions, load factor, and why you resize. → Hash Maps

Test coverage. Combinatorial explosion is why exhaustive testing is impossible and why pairwise testing exists — covering all pairs of parameter values is polynomial where all combinations is exponential.

Distributed systems. Quorum intersection is a counting argument: any two majorities of nodes must overlap, because . That one inequality is why quorums work. → Consensus

Load balancing. “Power of two choices” — picking the lesser-loaded of two random servers reduces maximum load from to . A counting result with real operational impact.

Practical notes

Factorials explode. overflows a 64-bit signed integer at . Use logarithms, or compute incrementally rather than as a ratio of factorials.

Compute binomials without overflow:

result = 1
for i in 0..k:
    result = result * (n - i) / (i + 1)

Multiply then divide, in that order — the intermediate is always an integer.

Check for double-counting. The commonest error. Ask: could I reach the same outcome by two different paths in my counting scheme?

Sanity-check with small cases. Compute by hand for and compare against your formula. Catches most off-by-one and order-matters errors immediately.


↑ Back to Discrete Mathematics