Combinatorics

Count the same objects through a bijection

A bijection pairs every object in one finite collection with exactly one object in another, with no omissions or repetitions. The two collections therefore have the same size.

Consider six-position binary strings with exactly two ones. Each string is determined by the two positions occupied by its ones. For example, $010010$ corresponds to the subset $\{2,5\}$ of $\{1,2,3,4,5,6\}$. Every two-position subset produces exactly one such string, so the count is

This argument is stronger than noting that two formulas happen to match. It explains why the objects themselves correspond. A coding rule that sent two different strings to the same subset would not be a bijection.

Double-count a marked selection

Choose a three-person committee from seven people and designate one member as chair. Count these marked committees in two ways.

First choose the chair, then select the other two members from the remaining six:

Alternatively, choose the committee first, then select its chair:

Both procedures count each committee-with-chair exactly once. The same reasoning proves, for integers $1\le r\le n$,

An unmarked committee is a different object. Forgetting the chair divides this count by three, not by seven.

Correct overlapping counts with inclusion-exclusion

How many integers from 1 through 30 are divisible by two or three? There are 15 multiples of two and ten multiples of three. Five numbers are multiples of both because they are multiples of six.

Subtracting the overlap once corrects the fact that it was counted twice in the first two totals. Ten of the thirty integers belong to neither category.

For three sets, the corresponding rule is

Each pairwise intersection here includes objects in all three sets. An object belonging to all three was counted three times, then subtracted three times, so it must be added back once. Venn Diagrams gives a region-by-region way to track the same calculation.

Guarantee a repetition with the pigeonhole principle

If more than k objects are placed into k categories, at least one category contains more than one object. More generally, placing n objects into k labelled categories, with $k\ge1$, guarantees that some category contains at least $\lceil n/k\rceil$ objects. The categories themselves need not all receive an object.

With 23 objects and five boxes, some box must contain at least five. If every box contained at most four, the total could not exceed twenty. This proves the guarantee without specifying which box is crowded.

A less obvious application begins with six distinct integers chosen from 1 through 10. Group the ten available integers into five pairs:

Selecting six numbers must completely select at least one pair. That pair sums to eleven. Five choices would not be enough to guarantee this: choosing $1,2,3,4,5$ takes only one number from each pair.

Count paths by their steps

On an integer grid, travel from $(0,0)$ to $(4,3)$ using only unit steps east and north. Every route has seven steps: four east and three north. Choosing the three positions of the north steps determines the route.

Now require the route to pass through $(2,1)$. The first segment needs two east and one north step, giving $\binom31=3$ choices. The remaining segment needs two east and two north steps, giving $\binom42=6$ choices.

Every allowed route reaches that point at most once, so this split counts each qualifying route once. The number avoiding it is $35-18=17$.

Allowing west steps, diagonal steps or revisits would change the problem. The binomial count is tied to the stated move restrictions, not merely the endpoint coordinates.

Distribute identical objects into labelled groups

Suppose seven identical counters are distributed among three labelled boxes, with empty boxes allowed. Let the box counts be $x_1,x_2,x_3$. We seek non-negative integer solutions of

Represent the seven counters by stars and separate the three groups with two bars. For example, **|***|** represents $(2,3,2)$. The nine-symbol string is determined by the two bar positions:

Adjacent bars represent an empty middle box; a bar at an end represents an empty first or last box. The boxes are labelled, so $(2,3,2)$ and $(3,2,2)$ are different allocations.

If each box must contain at least one counter, place one in each first. Distributing the remaining four gives $\binom62=15$ allocations.

Add an upper bound

Keep empty boxes allowed, but require $x_1\le3$. Start with the unrestricted 36 and subtract allocations with $x_1\ge4$. Set $y_1=x_1-4$. Then

There are $\binom52=10$ excluded allocations. Therefore $36-10=26$ satisfy the upper bound. The shift is a bijection: each excluded allocation corresponds to exactly one solution of the smaller sum.

Check the counting object before accepting the answer

A valid count must include every permitted object once. Check order, repeated objects, labels, empty choices and overlapping categories. These questions decide whether a product, quotient, complement or case split is valid.

For example, the stars-and-bars calculation does not assign probabilities to the allocations. A physical experiment that throws seven distinguishable counters into boxes generally gives different probabilities to different box-count triples. A count becomes a probability only after a selection model specifies the weights.

Related topics

Counting Principle, Permutations and Combinations provide focused technique references. Recurrence Relations counts arrangements through smaller cases, while Graph Theory: Introduction changes the emphasis from counting selections to describing connections.