Counting becomes difficult when an object can violate several conditions at once. Subtracting each bad set once removes such an object several times. Inclusion–exclusion corrects the count by examining what happens to one object, rather than relying on a diagram with a particular number of regions.
Count assignments that use every label
Definition 1.1.1
(Onto assignment)
A function from the set of tasks to the set of labels is onto, or surjective, when every label is used by at least one task.
Worked example 1.1.2
(Four tasks and three labels)
Four distinct tasks must each receive one of three distinct labels. How many assignments use all three labels? There are assignments without the restriction. Let be the set of assignments that never use label , for . The answer is the size of the complement of .
Each has elements. Each pairwise intersection contains the one assignment using only the remaining label. The triple intersection is empty: four tasks cannot be assigned a label if no label is allowed. Therefore
Here ; no convention about is needed. The tasks and labels are distinguishable: changing which task has a label or exchanging two labels produces a different assignment.
General formula and a boundary case
Theorem 1.1.3
(Alternating sum for onto functions)
For distinct tasks and distinct labels, the number of onto functions from the task set to the label set is
If , this number is zero.
Proof
(Each function contributes one or zero)
For a set of labels, let be the set of functions that use no label of . If , each task may take any of the remaining labels, so . Summing over the sets of size gives the th term , and the whole expression is .
Now fix one function and let be the number of labels it does not use. It lies in exactly when is contained in those unused labels, which happens for sets of size . If , only qualifies and the function contributes exactly . If , its total contribution is
Hence the sum counts each onto function once and every other function zero times, even when several bad sets overlap. If , the answer is zero for a direct reason: each task supplies at most one label, so not all labels can appear. The formula must agree with that argument, even though its individual terms need not be zero.
Proof X-ray
Why the correction must continue past the pairs
The proof changes the count from sets to objects: instead of measuring intersections, it asks how often one function is counted, and the binomial theorem answers . Each term corrects the ones before it. Stopping early is wrong in general: a function missing exactly three labels has contribution after the pairwise terms, so it would be counted although it is not onto. In the four-task, three-label example no function misses three labels, which is why the last term vanished there; with four or more labels that term cannot be dropped.
Worked example 1.1.4
(Fewer tasks than labels)
Take tasks and labels. The sum is . Most terms are nonzero, yet the total agrees with the direct argument that two tasks cannot use three labels.
Worked example 1.1.5
(Five tasks and four labels)
The sum is . Direct check: exactly one label is used twice, so choose the two tasks that share a label in ways, then assign the four labels to the four resulting groups of tasks in ways; .
Common mistake
(Do not subtract only the single-label omissions)
The expression is too small. An assignment using only label 1 misses labels 2 and 3, so it was subtracted twice. The three pairwise intersections each restore one such assignment, producing . Reversing the sign of the whole correction or treating labels as indistinguishable would count a different problem.
Practice
Quick check
(How many length-three strings over use all three symbols?)
Solution · Answer
Each symbol occurs exactly once, so the answer is . Inclusion–exclusion also gives .
Quick check
(How many functions from a two-element set onto a three-element set exist? Explain without calculating an alternating sum.)
Solution · Answer
None: two inputs cannot produce three different outputs.
Quick check
(Four distinct tasks are assigned two distinct labels. How many assignments use both labels?)
Solution · Answer
There are assignments; exclude the two constant assignments, leaving .