Learn · The Concrete Discrete Math of Real Systems

growing

Too Many Pigeons, Not Enough Holes

More objects than codes make duplication a theorem, not an accident — and one question about order separates permutations from combinations.

discrete-math, counting, pigeonhole, combinations, collisions, learn

The fundamental problem of communication is that of reproducing at one point either exactly or approximately a message selected at another point.

— Claude E. Shannon, A Mathematical Theory of Communication, 1948

Chapter 6 showed that some infinite spaces cannot fit into a numbered list. This chapter returns to finite spaces and asks what arithmetic forces before probability enters. You will prove that a smaller code space cannot name a larger source without collision, derive the least crowding any assignment must contain, decide whether order makes two selections different, and derive permutations, combinations, and the binomial recurrence instead of choosing formulas by memory.

Two hundred fifty-seven objects, two hundred fifty-six names

An eight-bit identifier has 256 possible values. Imagine a service that must hold 257 live objects and promises each one a distinct identifier. Can a sufficiently clever assignment keep the promise?

Commit before the assignment is revealed. Can 257 live objects receive distinct eight-bit identifiers?

Call the objects items and the identifier values boxes. Place each item in the box bearing its assigned identifier. If every box held at most one item, the 256 boxes could hold at most 256 items. But 257 items were placed. Therefore some box holds at least two.

This is the pigeonhole principle: more items than boxes forces a collision. The birds are decorative. The sizes do the proof.

Injection — a function that never sends two different inputs to the same output. In plain language: distinct inputs keep distinct names. Learn more.

The collision law. No function from a larger finite set into a smaller finite set can keep every input distinct.

If a finite set of items has more members than a finite set of boxes, then every assignment of items to boxes puts at least two items in one box.

Assume, for contradiction, that no box receives two items. Then every occupied box contains exactly one item, so the number of assigned items cannot exceed the number of boxes. That contradicts the premise that there are more items than boxes. Therefore at least one box receives two or more items.

In plain English: a collision-free assignment spends one box per item. When the boxes run out first, the promise is already impossible.

Note

The name behind the drawers. The pigeonhole principle is also called Dirichlet's drawer principle, after Johann Peter Gustav Lejeune Dirichlet (1805–1859), who used a drawer form of the argument in nineteenth-century number theory. The idea was printed at least two centuries earlier: a 1622 book gave a same-number-of-hairs example, and a 1624 treatment stated the general mechanism. The conventional name records later association, not first invention.

Count the spaces before blaming the algorithm

The theorem diagnoses impossible lossless compression. Suppose every input is exactly 1,000 bits, while every compressed output is at most 999 bits. The source has $2^{1000}$ possible inputs. The destination has fewer possible bit strings. A collision is forced: two inputs must produce the same compressed output, so a decoder cannot recover both exactly.

Real compressors escape by allowing some outputs to be longer, by restricting the admitted inputs, or by losing information. The theorem does not say compression is useless. It says every input becomes shorter without loss is an arithmetically false contract.

The same check applies to truncated hashes and database keys. Before estimating how likely a collision is, compare the number of possible live objects with the number of available names. If the live objects outnumber the names, probability has nothing left to decide.

Diagnose the contract, not the hash function.

How crowded must one box become?

The basic theorem promises a pair. Counting gives a sharper result. Put ten jobs onto three workers. If every worker received at most three jobs, the workers would hold at most nine. Therefore some worker receives at least four.

In general, divide the item count by the box count and round up. With $n$ items and $m$ available boxes, some box receives at least

$\lceil \frac{n}{m} \rceil$

items. Read the ceiling marks as “round up.” The average occupancy may not be an integer, but a real box must meet or exceed the rounded-up average.

Suppose every box held fewer than the rounded-up average. Then every box would hold at most one less than that bound. Multiplying that smaller integer by the number of boxes produces fewer than $n$ places, so the boxes could not contain all $n$ items. Therefore at least one box meets the bound.

This is a lower bound, not a load-balancing guarantee. It says some worker must carry at least four of ten jobs. A poor scheduler may place all ten on one worker. Arithmetic locates the unavoidable floor; policy determines how much worse reality becomes.

The one question behind two formulas

Choose three servers from eight. How many choices are there?

The question is incomplete. Are the servers receiving distinct roles such as primary, secondary, and tertiary? Or are they an unordered review group? Rearranging the same three names changes the first object and leaves the second unchanged.

Decide identity before counting. Does order create a new object?

When order matters, fill the roles one at a time: eight choices for primary, seven remaining choices for secondary, and six for tertiary. The product rule gives

$8 \times 7 \times 6 = 336.$

These are permutations: ordered selections without repetition.

For an unordered group, the same three people were counted once for each internal ordering. Three distinct people have $3 \times 2 \times 1 = 6$ orderings. Divide the ordered count by six:

$336 / 6 = 56.$

These are combinations: selections where only membership matters. The binomial coefficient “eight choose three,” written $\binom{8}{3}$ , is 56.

Factorial — the product of the positive integers down to 1. Thus $3! = 3 \times 2 \times 1 = 6$ . It counts the orderings of three distinct objects. Learn more.

The formulas are receipts for the reasoning:

$\text{ordered selections} = \frac{n!}{(n-r)!}$

$\text{unordered selections} = \binom{n}{r} = \frac{n!}{r!(n-r)!}.$

Words came first because the decisive step is not algebra. It is choosing the right notion of sameness.

The triangle that remembers every choice

Take a fixed person, Mira, among $n$ candidates. Every group of size $r$ either contains Mira or does not.

Groups containing Mira choose their remaining $r-1$ members from the other $n-1$ people.
Groups excluding Mira choose all $r$ members from the other $n-1$ .

The cases do not overlap and cover every group, so

$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}.$

That recurrence builds the triangular array commonly called Pascal's triangle. Each interior number is the sum of the two above it because every selection splits into “contains Mira” and “does not.”

Complete the recurrence by classifying one distinguished member.

Note

The person behind the triangle. Blaise Pascal (1623–1662), working in seventeenth-century France on geometry, calculation, and games of chance, gave a systematic treatment in his Treatise on the Arithmetical Triangle, written in 1654. It was published posthumously in 1665. The array was studied centuries earlier in India, Persia, China, and elsewhere. “Pascal's triangle” records the later European naming tradition, not sole invention.

Where certainty stops

The pigeonhole principle tells you that 257 objects in 256 boxes must collide. It does not tell you whether 100 randomly assigned objects in a million boxes are likely to collide. Both outcomes remain possible; now the assignment process and its probabilities matter.

Likewise, combinations count possible groups but do not say which groups are likely under a biased selection process. Counting supplies the outcome space. Probability adds weights.

This boundary is useful: ask the deterministic question first. If arithmetic already forces failure, a probability calculation can only decorate the post-mortem.

Lessons

More items than boxes forces a collision; randomness cannot enlarge the destination space.
Counting source and destination spaces can disprove an injective ID, encoding, or compression contract before implementation begins.
With $n$ items in $m$ boxes, at least one box reaches the rounded-up average occupancy.
Permutations and combinations differ by one modeling decision: whether rearrangement creates a different object.
Pascal's recurrence follows by splitting selections into two disjoint cases around one distinguished member.
Certainty ends before every collision question; probability begins when collision is possible but not forced.

Practice

Retrieval — find the forced occupancy.

Discrimination — permutation or combination?

Transfer — audit an encoding claim.

Possible is not yet likely

Counting has now separated two questions. When the source is larger than the destination, collision is certain. Before that boundary, collisions may still arrive surprisingly early.

How can we estimate a likely collision without listing every possible assignment?

References

Shannon. “A Mathematical Theory of Communication.” Bell System Technical Journal, 1948. — the epigraph's primary source and the exact-versus-approximate communication problem
Rittaud & Heeffer. “The Pigeonhole Principle, Two Centuries Before Dirichlet.” The Mathematical Intelligencer, 2014. — documentary history of the 1622 and 1624 statements and the later Dirichlet association
O'Connor & Robertson. “Johann Peter Gustav Lejeune Dirichlet.” MacTutor History of Mathematics, 2000. — institutional biography and mathematical context
Pascal. “Traité du triangle arithmétique.” Desprez, 1665. — Pascal's posthumously published systematic treatment of the arithmetical triangle
O'Connor & Robertson. “Blaise Pascal.” MacTutor History of Mathematics. — institutional biography and explicit warning that Pascal was not the first to study the triangle

A fixed-width identifier feels like a promise: every object receives a compact name, and different objects receive different names. But the second half is not an implementation detail. It is a claim about the sizes of two spaces. If a service may create 257 distinct objects and the identifier stores only eight bits, then there are 257 objects competing for 256 names. No hash function, random generator, database index, or careful retry policy can make the mapping one-to-one. At least two objects must meet. The collision is not bad luck; the design asked arithmetic for an impossibility. That same habit—count the source and destination before discussing the algorithm—unlocks the rest of finite counting. When three servers are assigned distinct primary, secondary, and tertiary roles, order changes the assignment. When three servers merely form a review group, rearranging their names changes nothing. Permutations and combinations are not two formulas to memorize. They are the two answers to one question: does rearrangement create a different object? Ask that first, and the formula follows instead of being guessed.