Motivation
A counting formula is only as reliable as the correspondence between its objects and the choices being counted. Ordered selections, subsets and functions answer different questions even when the same integers occur in their formulas. The main discipline is to specify the objects first, then decide whether choices are independent, cases are disjoint, or forbidden properties overlap.
Definitions
Definition 2.1.1
(Selections and forbidden properties)
For integers and , the binomial coefficient counts the -element subsets of an -element set. An ordered selection without repetition has possibilities. A permutation of is a bijection of that set to itself; a derangement is a permutation with no fixed point. A function is surjective when each target has at least one preimage.
Each -subset has orderings, so , with . Division by is justified by a uniform fiber size, not by the mere appearance of repetition. If the objects have differing numbers of encodings, division by a single factor need not work.
Theorem/Proposition
Theorem 2.1.2
(Inclusion–exclusion)
For subsets of a finite universe , the number of elements avoiding every is
where the intersection for is .
Theorem 2.1.3
(Derangements and surjections)
For , the number of derangements is . For a domain of size and a labeled target of size , the number of surjections is
using when counting functions from an empty domain.
Proof sketch or proof idea
Proof
(Each element contributes one or zero)
Fix one element and suppose it belongs to exactly forbidden sets. It lies in exactly when is a subset of those indices, so its total contribution to the inclusion–exclusion sum is . This is when and otherwise, which counts exactly the permitted elements. Summing these contributions over the finite set proves the theorem without assuming the forbidden sets are disjoint.
Proof X-ray
The exchange of summation order does all the work
The one non-obvious move is to stop reading the right side set by set and read it element by element: the sum of intersection sizes over index sets equals, for each element, the number of index sets whose intersection contains it. Finiteness of is what licenses this exchange. After it, the many-set formula collapses to a one-variable binomial sum. The empty index set, whose intersection is by convention, supplies the term 1; it is exactly why a permitted element, with equal to zero, keeps weight one. Disjointness of the forbidden sets is never used, which is why overlaps of every level are corrected at once.
Proof
(Derangements and surjections from the general formula)
For derangements, take the universe of permutations and let mean that position is fixed. Fixing a specified set of positions leaves permutations on the other positions. There are such sets, so inclusion–exclusion gives the formula.
For surjections, the universe is all functions. Let mean that target is missed. Missing specified targets leaves functions, since every domain element independently chooses one remaining target. Again group the inclusion–exclusion terms by .
If , the surjection count is zero: a function from fewer domain elements cannot hit every target. This is a structural check on the formula, not an additional correction term.
Worked examples
Worked example 2.1.4
(Distinguishing subsets from functions)
Choose three committee members from seven people: order is irrelevant, so there are committees. Assign a chair, secretary and treasurer to distinct people: now positions are labeled and there are assignments. If one person may hold several offices, each office independently chooses one of seven people and the answer becomes .
Worked example 2.1.5
(A complete derangement calculation)
For four labeled letters placed into four labeled envelopes,
The final two terms correspond to three fixed letters and four fixed letters. Three fixed letters force the fourth to be fixed too, but inclusion–exclusion deliberately retains those overlapping events; deleting them would spoil the cancellation.
Concept lensAnalytic
Derangements as a truncated exponential series
Dividing the formula by gives , the partial sum of the series for . The alternating tail after is smaller in size than , so
and is the integer nearest to : for , rounds to . The proportion of derangements among all permutations tends to .
Worked example 2.1.6
(Onto allocations to labeled boxes)
Place five distinct objects into three labeled nonempty boxes. A placement is a surjection from the objects to the boxes, so the count is . If boxes are unlabeled, every partition into three nonempty blocks has exactly labelings, giving . Nonemptiness makes this division uniform.
Counting the same object in two ways
A double-counting proof begins with one clearly defined finite set, then computes its size by two different decompositions. The force of the argument comes from using the same objects both times. If the two sides count different kinds of labeled or unlabeled objects, an apparent identity may instead hide a missing factor.
For example, count pairs consisting of a subset of a fixed size and one distinguished element of that subset. Choosing the subset first gives its binomial count multiplied by its size. Choosing the distinguished element first leaves a smaller subset to choose from the remaining elements. Equating these counts proves the familiar identity relating adjacent binomial coefficients. The distinguished element is not decoration: it explains why the extra multiplicative factor appears.
Another useful double count partitions a selected subset according to how many elements come from each of two disjoint populations. Choosing a subset from their union gives one binomial coefficient. Summing the products of the two population-specific choices over every feasible split gives the same total. The cases are disjoint because each subset has one uniquely determined split size. This proves the binomial convolution identity and shows why the summation range may safely include impossible choices only if their binomial coefficients are defined as zero.
Repetition and the stars-and-bars correspondence
Choosing with repetition is a different model from choosing a subset. Suppose a nonnegative integer total is distributed among a fixed positive number of labeled boxes. Each distribution is a tuple of nonnegative counts whose sum is the total.
Theorem 2.1.7
(Stars and bars)
Let and be integers. The number of tuples of nonnegative integers with is . The number with every is when , and zero when .
Proof
(A string of stars and bars encodes each distribution once)
Represent the units by stars in a row and separate the box contents by bars. Consecutive bars represent an empty box, and bars at the ends allow the first or last box to be empty. The arrangement has positions, so choosing the bar positions counts the strings.
The correspondence is bijective: reading the numbers of stars before, between and after the bars recovers exactly one count tuple; constructing the arrangement from a tuple recovers exactly one string of stars and bars. This proves the first formula.
If every box must receive at least one unit, remove one unit from each box first. The map is a bijection onto nonnegative tuples with total . If that is negative, there are no distributions. Otherwise the first formula with total gives .
The boxes are labeled by their order in the arrangement. Removing labels changes the problem to integer partitions and invalidates that direct formula. A lower-bound condition is handled by a reversible shift, not by an ad hoc subtraction from the final count.
For a concrete example, distribute eight identical units among three labeled nonempty boxes. Removing one from each leaves five units, and choosing two bar positions among seven positions gives possibilities. Distinct objects would require a different model: a count tuple does not say which particular objects went into each box. That missing information is why the onto-function example has a much larger count.
Why the alternating signs are forced
Inclusion–exclusion can look like a rule for remembering alternating signs. Its proof gives a better interpretation. An object violating several conditions is first counted too often; subtracting pair intersections corrects that but then overcorrects higher overlaps. The binomial cancellation checks all these corrections at once, for each individual object. The signs are forced by the requirement that every forbidden object have net contribution zero.
One should also identify the universe before defining forbidden properties. For derangements the universe already contains only bijections, so fixing positions leaves a permutation of the remaining labels. For surjections the universe contains all functions, so missing target labels leaves independent choices for every input. Confusing those universes would replace a factorial by a power or vice versa, producing an incorrect formula even if the signs were remembered perfectly.
A recursive view of derangements
There is a second way to organize derangements that complements inclusion–exclusion.
Proposition 2.1.8
(Derangement recurrence)
With and , the derangement numbers satisfy for .
Proof
(Split by whether the first label lies in a two-cycle)
In a derangement of , the image can be any of the other labels. Fix . There are then two cases: , making a two-cycle, or .
In the two-cycle case, remove the labels and . The remaining permutation of labels must be a derangement, and every such derangement reconstructs uniquely after the two-cycle is restored. In the other case, remove from its cycle: the predecessor that used to point to now points to . Since that predecessor is not , no fixed point is created, and this leaves a derangement on the labels other than . Conversely, from such a derangement, insert immediately before in its cycle. This reconstruction is unique and belongs to the second case.
For each of the choices of , the two cases therefore contribute . For the first case uses , the empty permutation, and the second uses .
The recurrence can be checked numerically against the alternating-sum formula, but the bijective argument explains why it must agree. The two methods reveal different structures in the same objects.
When division by symmetry is justified
The labeled-box example divides by a factorial because every unlabeled partition into the fixed number of nonempty blocks has exactly that many labelings. Each block is distinguishable by its actual elements, so assigning distinct box labels gives the full factorial number of different labeled allocations. Empty blocks would destroy this simple uniform description: exchanging two empty labeled boxes does not change an allocation in the same way as exchanging two nonempty contents.
Margin Note
Ask for the size of each encoding fiber
Before dividing a count, define the map that forgets labels or order. Then prove every target object has the same number of preimages. If the fiber sizes vary, a single division factor cannot be justified. More advanced symmetry methods handle varying stabilizers, but they are not needed to repair an elementary counting model here.
This fiber viewpoint is also a useful way to audit answers. A proposed formula should remain sensible at the smallest possible input and vanish when the requirements are impossible. Such boundary checks do not replace a proof, but they often expose an incorrect model before lengthy arithmetic begins.
Common mistakes
Common mistake
(Adding counts of overlapping properties)
Adding counts requires disjoint cases. Summing counts an element once per property it has, which is why overlaps must be corrected. Conversely, multiplying counts requires that the number of options at each step is known for every previous choice. Independence in counting is a statement about these option counts, not necessarily probabilistic independence.
Common mistake
(Pigeonhole proves existence, not a count)
The pigeonhole principle says that placing more than objects into boxes forces a box with at least objects: otherwise the total would be at most . It proves existence, not the number of allocations. Do not substitute it for a counting formula when the question asks for an exact total.
The division step of the labeled-box example is the place where a hypothesis is most easily dropped.
Counterexample mode
Dividing by the number of labelings when boxes may be empty
Claim: the number of ways to put five distinct objects into three unlabeled boxes, empty boxes allowed, is the labeled count divided by 3 factorial. The labeled count is 3 to the power 5, which is 243, and 243 divided by 6 is 40.5, not an integer, so the claim fails. Counting directly by the number of nonempty blocks gives 1 partition into one block, 15 into two blocks and 25 into three blocks, 41 in all. A partition into one block has only 3 labelings, whereas partitions into two or three blocks have 6 each, and indeed 3 + 90 + 150 = 243: the fibers are not uniform. The division is valid exactly when every box is required to be nonempty, as in the worked example.
Summary
Bijections and uniform encoding counts justify multiplication and division. Inclusion–exclusion counts objects with no forbidden properties by canceling each object's excess contributions. Derangements forbid fixed points; surjections forbid missed targets.
Exercises
Quick check
(Count length-six strings over four letters in which every letter occurs.)
Positions are distinct and letters are labeled.
Solution · Answer
A string is a function from the six positions to the four letters, and requiring all four letters is precisely surjectivity. The count is . The final term is zero. Repeated letters are allowed.
Quick check
(Prove that any six integers contain two with difference divisible by five. Explain why the conclusion does not specify a unique pair.)
Use residue classes as boxes.
Solution · Answer
Put each integer into its remainder class modulo . Six integers in five boxes force two entries in the same class, whose difference is divisible by . Several boxes may contain pairs, or one box may contain three or more entries, so the existence proof supplies no uniqueness assertion.
Quick check
(Compute from the recurrence, and check it against the alternating-sum formula.)
The recurrence needs and .
Solution · Answer
From and , the recurrence gives , and . The alternating sum gives , in agreement.