Why a counting rule needs a model
A multiplication is not justified merely because a question contains several numbers. Before counting, specify what one answer is and how a sequence of choices determines it. Does every valid answer arise? Can two different choice sequences produce the same answer? A counting rule answers the question only after these issues are settled.
Cases and fibers
Definition 2.4.1
(Disjoint cases and fibers)
A family of subsets of a set is a disjoint cover of when its members are pairwise disjoint and their union is ; we allow empty members. For a function , the fiber over is . Empty fibers are allowed.
Theorem 2.4.2
(Sum and fiber rules)
If a finite set has a disjoint cover by finitely many sets , then . If is a function between finite sets, then
In particular, if every fiber has the same size , then .
Proof
(Why no object is lost or counted twice)
For the sum rule, every element of belongs to at least one case because the cases cover , and to at most one because they are disjoint. Counting each case once therefore counts every element exactly once. For the fiber rule, each lies in the unique fiber labeled by . The fibers form a disjoint cover of , including any empty ones. The uniform formula follows by summing identical terms. It remains valid for ; then as well.
The direction of the map matters. An encoding map from descriptions to objects may have several descriptions in one fiber. If every object has exactly descriptions, dividing the number of descriptions by gives the number of objects. A surjection alone only says that each fiber is nonempty; it does not imply that the fibers have equal size.
Worked example 2.4.3
(Unequal fibers cannot be divided away)
Let the descriptions be and let send to and to . There are five descriptions and two objects. The fibers have sizes and , so dividing by either or does not give the number of objects. The correct sum is . A divisor is justified by a proved common fiber size, not by the fact that some objects are repeated.
Multiplication and dependent choices
Theorem 2.4.4
(Product rule with conditional choices)
Suppose a finite construction has stages. There are choices at stage one, and for each valid prefix of length there are exactly possible choices at stage , for . Then the number of valid complete choice sequences is . For there is one sequence, the empty sequence, so the empty product is .
The available choices may depend on earlier choices: only their number must be constant at each stage.
Proof
(Induction on prefixes)
Let be the set of valid prefixes of length , with containing the empty prefix. Deleting the last choice maps to . Every prefix has exactly extensions, so the uniform-fiber rule gives . Repeating this identity proves the product. A zero factor correctly gives no complete sequence; if no prefixes reach a later stage, the assertion about their extensions is vacuous.
Proof X-ray
Where the uniform extension count is used
The proof is an induction along the prefix sets , and the hypothesis enters at exactly one point: every fiber of the truncation map must have elements. The choices themselves may change with the prefix; the fiber rule sees only their number. If one prefix had extensions and another a different number, could only be written as the sum of the extension counts over , which is the branching-tree count of the next paragraph and not a product.
Two degenerate cases close the argument without extra work. has one element, the empty prefix, which is why the empty product is . If some , then , every later fiber condition holds vacuously, and the formula correctly returns . The induction never uses that different choice sequences give different objects; that is a separate question, handled by the fiber rule in the next section.
When the number of continuations varies, sum over the prefixes instead. If is the number of completions after a first-stage choice , the number of two-stage sequences is . For a longer construction, the same idea gives a branching tree: add the numbers of completed sequences below each first branch. Multiplication is the special case in which the relevant fiber sizes are uniform.
Worked example 2.4.5
(A restriction changes the branch sizes)
Choose an ordered pair of distinct integers from with even. If is odd, must be the other odd number; if is even, must be the other even number. Each of the four choices for has exactly one continuation, so there are pairs: .
If instead must be odd and , the numbers of continuations for are respectively. Their sum is ; multiplying by a single branch count would need a uniformity that is absent.
Worked example 2.4.6
(An even three-digit integer with distinct digits)
How many three-digit integers have distinct digits and an even units digit? A leading zero is forbidden. Split by the units digit, because zero plays a different role from a nonzero digit.
If the units digit is , the hundreds digit has choices and the tens digit has remaining choices. This case contributes . If the units digit is one of , it has choices. The hundreds digit is nonzero and different from the units digit, so it has choices; the tens digit can be any of the remaining digits, including zero. This case contributes .
The cases are disjoint and exhaustive, so the total is . Within each case the branch counts are uniform, although they differ between the cases. Choosing the last digit first is useful, but multiplying by a single count for the remaining positions would overlook that distinction.
Common mistake
(Choosing the positions in the wrong order)
If the hundreds digit is chosen first (nine ways) and then the tens digit (nine ways), the number of even digits still available for the units place is five minus the number of even digits already used, which is , or depending on the earlier choices. No single factor can be written for the last stage, so the product rule does not apply in this order; either sum over the cases or, as above, choose the constrained position first.
From sequences to objects
Worked example 2.4.7
(Committees and ordered offices)
From six people, choose a three-person committee. First count ordered lists of three distinct people: there are . Forgetting the order maps a list to its committee. Each committee has exactly lists, since its members can be arranged in six orders. The fiber rule gives , hence committees. By contrast, if the three positions are chair, secretary and treasurer, changing the order changes the assignment, so all sequences are distinct answers and no division is warranted.
Counterexample mode
A quotient is not automatically uniform
Let two distinct people each choose one of three unlabeled boxes, with empty boxes allowed. There are two unlabeled distributions: the people are together or separated. If the boxes are labeled first, there are assignments. Forgetting labels gives three descriptions of the together distribution but six of the separated distribution. Dividing by would produce , not .
Take a particular object and count its actual descriptions. In the example, permuting labels on the two empty boxes in a together assignment does not change that assignment. For nonempty blocks, by contrast, each labeling of the distinct blocks produces a different assignment. Nonemptiness explains why division by a factorial is valid in the companion discussion of surjections.
Counting one incidence set from both sides
Earlier we counted sets by splitting them into fibers of known sizes. Here we look at a related situation: the same finite set of ordered pairs can be split in two different ways, once by its first coordinates and once by its second. Each split gives a correct count. Putting the two counts side by side gives an equation, and that equation can rule out configurations without searching through them.
Suppose a group of students signs up for workshop sessions. You can count sign-ups by asking every student how many sessions they attend and adding the answers. You can also ask every session how many students attend it and add those answers. Each method counts every sign-up exactly once, so the two totals must agree, even though the individual numbers in the two lists can be quite different.
Setting
Let be a finite set of students and a finite set of sessions. An incidence set is any subset . We read as "student attends session ". Each pair either belongs to or does not, so a student cannot be recorded as attending the same session twice. For and define
We call the left degree of and the right degree of . Either may be .
Proposition 2.4.8
(Double counting)
For finite , and any ,
Corollary 2.4.9
(Uniform degrees on both sides)
If for every , then . If, in addition, for every , then . When this gives . When the equation only says , and nothing may be divided by .
Proof
(Why both sums count the same set)
Let send to . The fiber over is . The map is a bijection from onto , because the first coordinate is fixed. So .
The fibers are pairwise disjoint, since a pair has only one first coordinate. Their union is , since every pair has some first coordinate in . The fiber rule therefore gives .
Applying the same argument to gives .
Edge cases need no separate treatment:
- If , then , so . Both sums equal : one is an empty sum, and the other is a sum of zeros (or empty if too).
- A student with no sessions contributes an empty fiber and adds .
For the corollary, a constant sum is . Equating the two expressions for gives .
Concept lensAlgebraic
Double counting as two ways to sum a matrix
Record as its incidence matrix , with rows indexed by , columns by , and entry exactly when . Then is the sum of all entries. The row sums are the left degrees, , and the column sums are the right degrees, . The proposition is the associativity : adding row totals or column totals gives the same grand total.
Common mistake
(The two sums are not two stages)
The two partitions are different ways of cutting up one set . They are not two independent stages of a choice, so the two sums must not be multiplied together. We are adding up the sizes of fibers, and those sizes may vary freely from fiber to fiber.
Worked example 2.4.10
(Four students, three sessions)
Let , , and
Left degrees.
- Ada attends and , so .
- Bo attends , so .
- Cy attends and , so .
- Di attends , so .
The sum is .
Right degrees.
- has Ada and Cy, so .
- has Ada and Bo, so .
- has Cy and Di, so .
The sum is , which agrees with .
Averages. The average right degree is , and here every session really does have degree . That is a fact we checked in the data; it does not follow from the average. The average left degree is , yet no student attends sessions. Each is an integer, and the actual values are and . An average describes the total divided evenly. It does not describe any particular vertex.
Counterexample mode
Multiplying where you should add
It is tempting to say "4 students, 3 sessions, so attendances". But counts every possible pair. One of those pairs is , and Bo does not attend . In fact six of the twelve pairs are absent. The product equals only when .
A second error goes the other way. Suppose a sign-up sheet lists Ada under twice. A count of the lines on the sheet then reports , but the incidence set still has elements, because is a single pair. Double counting is a statement about the set , not about a list that may contain repeated entries.
Exercises
Quick check
(Four students each attend exactly two sessions, and there are five sessions. Show that it is impossible for every session to have the same positive number of students. Then give an explicit assignment in which each student still attends two sessions.)
Solution · Answer
Counting by students gives . If every session had students, counting by sessions would give , so . Since , no positive integer works. So no such configuration exists.
Uneven session sizes are possible. Take students and sessions , with
- attending ,
- attending ,
- attending ,
- attending .
Every left degree is . The right degrees are , , , , . Their sum is , as the proposition requires.
Quick check
(Let , , and . Compute all degrees, verify both sums, and find the average degree on each side. Explain why neither of the two given coordinate-fiber partitions has uniform fiber size.)
Solution · Answer
The left degrees are , , , . The right degrees are , , . Both sums equal .
The left average is . Even so, attends two sessions and attends none.
The right average is , which is allowed only because . With there would be no right average at all, and writing would be meaningless.
Neither side is uniform. The left degrees take the values , and , and the right degrees take , and . No common is the degree of every session, so the uniform-fiber rule cannot be applied to this example; the average must not be used as if it were a degree.
Practice
Quick check
(How many three-digit decimal strings have distinct digits and an even final digit? Leading zero is allowed.)
Condition first on the final digit; check how many choices remain for each earlier position.
Solution · Answer
There are five choices for the final digit, then nine for the first and eight for the middle digit. Each string is determined once by this procedure, giving . Allowing a leading zero is essential to the nine-choice count; a three-digit integer has a different restriction.
Quick check
(A set has elements and a function from to a three-element set has fibers of sizes , and . Find . Can this function have a common fiber size?)
Use the fiber sum, not a product rule.
Solution · Answer
The fiber rule gives , so . The fibers already have different sizes, and a common fiber size is impossible; independently, is not divisible by .
Quick check
(Count the ordered pairs of integers with and . Explain why multiplying three first choices by three second choices is wrong.)
Count the possible values of separately for each .
Solution · Answer
For there are respectively possible values of . The sum is . The nine ordered pairs from a product would include pairs such as that violate ; the second-stage count is not uniformly three.
Quick check
(How many functions are there from the empty set to a three-element set? What are the sizes of the three fibers, and is the function onto?)
A function must assign a value to each input. Consider what this requires when there are no inputs.
Solution · Answer
There is exactly one function: the empty function, whose graph is the empty set. Each of its three fibers is empty, and the fiber sum is , the size of its domain. It is not onto the nonempty target. This one function corresponds to one empty sequence of choices; it should not be confused with an element of the empty domain.