Sum and product counting rules

Three patterns and two stamps make how many cards?

A card maker has three paper patterns P1, P2 and P3, and two stamp styles S1 and S2. A finished card uses exactly one pattern and one stamp. Every pattern permits either stamp. Two cards count as different exactly when their pattern or stamp differs; making another copy of the same design does not create a new design.

P1 can be paired with S1 or S2. The same two choices remain for P2 and P3. The complete grid therefore has six cells: three rows with two cells in each. The count is 3 × 2 = 6 distinct pattern–stamp pairs, not 3 + 2 = 5 separate supplies.

Changing the question changes the count. If instead you choose one card from three printed designs P1, P2, P3 or two folded designs F1, F2, and no design belongs to both families, there are 3 + 2 = 5 choices. The words “and” and “or” are clues; the exact outcomes and their relationships decide the rule.

Read the objects before the formula

The lesson Counting, zero and natural numbers explains counting each distinct object once. Multiplication and division develops equal groups, which become grid rows and equal representation groups here. Examples, explanations and counterexamples helps separate a small successful check from a reason that covers every allowed case.

First read through disjoint alternatives, staged choices and variable branches. The binary-word section uses a nonnegative integer power such as 2³. If that notation is unfamiliar, review Powers, roots and the real number line, then return there. No probability, factorial or binomial-coefficient formula is needed for this lesson.

The sets and mappings lessons develop the language of unions, products and bijections further. Here a set means a collection of distinct outcomes, a map assigns one output to each input, and every new counting term is explained before it is used.

A finished object is not always its construction record

Let Ω be the finite set of outcomes being counted. Its cardinality |Ω| is the number of distinct members. A proposed list is a correct count only if it includes every allowed outcome and lists no outcome twice. State whether order, labels, repeated use and any restrictions matter.

For a pattern–stamp card, use the ordered pair (pattern, stamp). These positions have different roles: (P1, S2) identifies one card, while a list of the five available supplies identifies no finished card. Changing the order in which you picked the same pattern and stamp does not produce another card under our definition.

A construction history or record may contain more information than the final object. If two records represent the same object, counting records counts that object more than once. Later we will group records by their final objects and check whether division can remove the overcount.

Counting alone supplies no probabilities. Outcomes need not be equally likely, and a grid with equal-sized cells does not assert that they are. This lesson concerns exact finite possibilities.

Add cases that share no outcome

Two finite sets A and B are disjoint when no outcome belongs to both: A ∩ B = ∅. Their union A ∪ B contains outcomes in either set, including any shared outcome if one exists. For disjoint sets, the sum rule is |A ∪ B| = |A| + |B|.

The reason is that each outcome of the union belongs to exactly one of the two cases. Listing A, then B, includes everything without a duplicate. In the two card families, {P1,P2,P3} and {F1,F2} are disjoint, so the list contains five distinct designs.

More generally, add the sizes of finitely many pairwise disjoint cases. Pairwise disjoint means every pair of different cases has empty intersection. A case of size zero contributes zero; two empty cases still have an empty union, not two outcomes.

If the same design is offered by both catalogues, the catalogues are not disjoint merely because their names differ. You must decide whether you count designs or catalogue–design records. Adding an explicit catalogue label makes different records, but it changes the question.

Subtract one extra count of the overlap

For arbitrary finite A and B, |A ∪ B| = |A| + |B| − |A ∩ B|. An A-only outcome is counted once in the sum, a B-only outcome once, and a shared outcome twice. Subtracting the shared count once leaves every union member counted exactly once.

A precise decomposition gives the same proof. The three sets A ∖ B, A ∩ B and B ∖ A are pairwise disjoint and cover the union. Both |A| and |B| include the shared part, so adding them counts that middle part twice instead of once.

With A = {1,2,5,6} and B = {2,3,6}, the shared outcomes are {2,6}. The corrected count is 4 + 3 − 2 = 5, with union {1,2,3,5,6}. Removing the overlap twice would wrongly discard shared outcomes from the union.

The formula includes the boundary cases. For disjoint inputs the subtraction is zero. If A = B, it gives |A| + |A| − |A| = |A|. If A ⊆ B, the overlap is A, so the answer is |B|. Corrections for three or more overlapping cases require more bookkeeping; that is a later lesson.

Multiply when every partial choice has the stated continuations

Suppose there are m first choices and exactly n legal second choices after every first choice. If every legal two-stage path identifies one distinct outcome and every outcome has exactly one such path, the count is m × n. Group the paths by their first choice: there are m disjoint groups, each of size n.

The set of all ordered pairs from finite choice sets A and B is their Cartesian product A × B. Every member of A may be paired with every member of B, so |A × B| = |A| × |B|. The pattern–stamp grid is this complete product. A missing legal pairing would remove a cell and invalidate that full-grid count.

The same idea extends to k stages. If the number of available choices at stage i is nᵢ after every legal prefix of the earlier stages, and complete paths correspond exactly to outcomes, the count is n₁ × n₂ × ⋯ × nₖ. The identities of the choices may depend on the prefix; the required condition is that their number is the stated constant at that stage.

This condition is about legal continuations, not probabilistic independence. Two different-colour lamps allow two final brightness settings each, even if the actual setting labels differ. Four legal colour–setting paths result when each colour has exactly two settings and a path uniquely identifies a lamp configuration.

Unequal branches require a sum of leaf counts

A first-stage choice A has two legal continuations, B has one, and C has four. The tree has 2 + 1 + 4 = 7 leaves. Each path remembers its first choice, so the three path families are disjoint. Multiplying three first choices by two would give six and omit a legal outcome.

For a finite first-choice set A, let r(a) be the number of legal continuations after choice a. Then the number of two-stage paths is the sum of r(a) over a ∈ A. When every r(a) equals n, this sum becomes |A| × n. A variable tree and a constant product are the same disjoint-group reasoning under different conditions.

At more stages, count the leaves below each allowed prefix, then add disjoint branches. A branch with no legal continuation contributes zero completed paths. Do not count its unfinished node as a finished outcome unless the question explicitly permits stopping there.

A tree counts paths. If two different leaves represent the same finished object, the leaf total is still the number of histories, and a further correspondence or multiplicity argument is needed to count objects.

A reversible correspondence preserves the count

A bijection pairs every object of one finite set with exactly one object of another, with every object on the second side used exactly once. Equivalently, the mapping is one-to-one and onto. One-to-one prevents merging different inputs; onto prevents missing an output.

To justify a bijection, explain both the encoding and how to recover the original object. Reversing each three-letter word over {a,b} is a bijection on those words: reversing twice returns the original word. It preserves the eight-word count. Simply sorting a word’s letters is not one-to-one: aab and aba both become aab.

A grid-cell correspondence sends a finished card to its unique (pattern, stamp) pair. Reading the pair reconstructs the card’s design. This supplies the connection between six construction choices and six designs; equal numerical counts without a correspondence would not explain why a proposed encoding works.

A bijection may relate very different objects. You need not find the count first: proving a reversible correspondence means that either side can be counted once the other side is understood.

Subtract the unwanted outcomes from a stated universe

Let Ω be a specified finite universe and W ⊆ Ω the unwanted outcomes. The wanted outcomes Ω ∖ W and W are disjoint and cover Ω. The sum rule gives |Ω ∖ W| = |Ω| − |W|. Both counts must refer to the same universe.

For three positions, each holding 0 or 1, Ω contains all 2³ = 8 binary words. A word has at least one 1 exactly when it is not 000. There is one all-zero word, so the wanted count is 8 − 1 = 7. The complete display keeps 000 visible as the excluded word rather than pretending it never belonged to Ω.

“At least one 1” and “exactly one 1” are different conditions. In this universe, exactly one 1 gives only 001, 010 and 100, a count of three. Complement subtraction removes only the outcomes actually forbidden by the stated condition.

For length zero, the universe contains one empty word. It has no 1, so the count with at least one 1 is 2⁰ − 1 = 0. A restriction eliminating every universe member gives zero wanted outcomes; an empty unwanted set leaves the full universe count.

Divide only after proving the same multiplicity everywhere

Let R be a finite set of records and T a finite set of finished objects. A map f sends each record to the object it represents. The fibre over an object t is the group of records mapped to t. These fibres are disjoint: one record cannot have two assigned outputs.

Suppose every object in T has exactly k representing records, where k is a fixed positive integer. Then the fibres cover all R and form |T| groups of size k. Thus |R| = k × |T| and |T| = |R| ÷ k. The condition includes every object of T; a missing object would have a fibre of size zero and break the positive k condition.

Three designs A, B and C each have two distinct catalogue records, A1,A2; B1,B2; C1,C2. Forgetting the record suffix maps six records to three designs. Every design has exactly two records, so dividing six by two correctly counts three designs.

Division is justified by the equal fibres, not by the fact that the quotient happens to be a whole number. State the records, the objects, their mapping and the positive common multiplicity before dividing.

A plausible divisor can still give the wrong answer

Now four designs A, B, C and D have records A1; B1; C1,C2; D1,D2. There are six records and four designs. The fibre sizes are 1, 1, 2 and 2, so there is no common multiplicity two. Dividing six by two gives three, which is an integer but is the wrong design count.

The exact identity is |R| = the sum of the individual fibre sizes. Here it is 6 = 1 + 1 + 2 + 2. Equal-size division is the special case in which every term has the same value. Without that evidence, a duplicate seen somewhere does not give a divisor valid everywhere.

You can instead list the distinct outputs, partition the objects into cases with known equal multiplicities, or establish a genuine bijection. Choosing a convenient divisor after seeing the record total supplies none of these reasons.

Each subset has one inclusion word

Fix a finite set S = {s₁, …, sₙ} of n distinct elements in a chosen order. Encode a subset by n bits: bit i is 1 when sᵢ is included and 0 when it is excluded. Each bit has two choices, so there are 2ⁿ words. The order labels positions; it does not give an order to the subset itself.

This encoding is a bijection. Given a subset, every bit is determined by membership. Given a word, include exactly the elements in its 1 positions. These two operations undo each other, proving that every subset appears exactly once and that different subsets have different words. Therefore an n-element set has 2ⁿ subsets, for every nonnegative integer n.

For S = {1,2,3}, the word 101 encodes {1,3}. The word 000 encodes ∅ and 111 encodes S. All eight words appear in the table. Selecting {3,1} rather than {1,3} does not create a new subset: the fixed position encoding gives 101 in either listing order.

For n = 0, there is exactly one subset, ∅, and exactly one length-zero word, the empty word. Thus 2⁰ = 1 has an outcome interpretation. It differs from making a required choice from an empty menu, which allows no completed outcome. Counting subsets of a fixed size uses a further rule developed in the next lesson.

Check zero, one and what a path represents

If a required stage has zero legal choices, no path can finish, so the product count is zero. With zero required stages, there is one empty choice tuple: do nothing. The product with no factors is defined as one to preserve this interpretation. Neither statement changes the meaning of a required choice from an empty set.

For two disjoint alternatives, addition is still valid when one or both are empty. For complement counting, the unwanted outcomes must lie in the stated finite universe. For division, the common fibre size must be positive and apply to every target object, even if all displayed objects look similar.

A reliable counting plan names the outcome, describes allowed choices, and checks whether cases overlap, branch counts vary, or histories merge. Then choose a rule, give its reason, and test a small or boundary case. A correct small count checks the explanation; it does not establish an unrestricted rule by itself.

Use the explorer to compare these small structures. Predict the count before revealing the complete table, then identify the precise condition that makes the rule valid. The nonuniform record case is a useful check that a whole-number quotient alone can still be wrong.

Worked examples

Try it yourself

1. You may choose one of four distinct postcards or one of three distinct bookmarks, with no object in both families. Alternatively, a gift pack contains one postcard and one bookmark, with every pairing allowed. Count each question.

   Show the answer and reasoning

   A single-item choice has 4 + 3 = 7 outcomes. A gift pack has 4 × 3 = 12 outcomes.

   The first question selects one member of a disjoint union. The second requires a typed pair, and every postcard has all three bookmark continuations. These are different outcome sets.

2. Finite A and B each have five elements and A = B. What is |A ∪ B|? Explain why adding the two sizes alone fails.

   Show the answer and reasoning

   |A ∪ B| = 5 + 5 − 5 = 5.

   The overlap is the whole common set. Adding alone counts each member twice; subtracting one common-set count leaves each member once. Equality is a boundary case of the same two-set rule.

3. First choices X,Y,Z have zero, two and three legal continuations. Only completed two-stage paths count. How many outcomes occur?

   Show the answer and reasoning

   There are 0 + 2 + 3 = 5 completed paths.

   The X node has no completed leaf and contributes zero. The first-choice labels make the remaining path families disjoint. Counting X itself as an outcome would change the stopping rule.

4. A red lamp allows brightness settings low and high; a blue lamp allows settings standard and extra. Each colour–setting pair is a distinct configuration. May the product rule count them?

   Show the answer and reasoning

   Yes. There are 2 × 2 = 4 configurations.

   The setting identities depend on colour, but each legal first choice has exactly two continuations. A product count requires this constant number, not identical setting names or probabilistic independence.

5. For four-bit words, count those with at least one 1. Is this also the count with exactly one 1?

   Show the answer and reasoning

   At least one 1 gives 2⁴ − 1 = 15 words. Exactly one 1 gives four words: 1000,0100,0010,0001.

   Only 0000 is excluded by the at-least condition. Words with two, three or four ones remain. For exactly one, its unique position determines the word, giving four outcomes without a fixed-size-subset formula.

6. T is a finite set of objects, and every object has exactly three distinct records. Every record represents one object of T. If there are twenty-one records, how many objects are there?

   Show the answer and reasoning

   There are 21 ÷ 3 = 7 objects.

   The fibres are disjoint, cover all records and each have size three. Hence 21 = 3 × |T|. The positive equal multiplicity justifies division and ensures that no object of T is missing.

7. Objects A,B,C,D have respectively one, one, two and two records. Someone divides six records by two and reports three objects. What failed?

   Show the answer and reasoning

   There are four objects. The fibre sizes are not uniformly two.

   The six records are partitioned as 1 + 1 + 2 + 2. The proposed divisor fits only C and D. The whole-number quotient three is insufficient evidence; A and B each have only one representation.

8. With positions ordered 1,2,3,4, which subset does 0101 encode? What word encodes {1,3,4}?

   Show the answer and reasoning

   0101 encodes {2,4}; {1,3,4} is encoded by 1011.

   Bit i records inclusion of element i. Recovering the bits from the subset reverses the encoding, so neither ordering a subset’s listing nor choosing it in a different sequence creates another subset.

9. Compare choosing one item from an empty menu with making a tuple of choices from zero required stages. How many outcomes are there in each case?

   Show the answer and reasoning

   The required choice from an empty menu has zero outcomes. Zero required stages have one outcome, the empty tuple.

   The first task cannot be completed. The second task is already complete without a choice. This gives the empty product its value one and is consistent with the single empty binary word and single subset of ∅.

10. Does sorting every three-letter word over {a,b} into alphabetical order give a bijection on all eight such words?

    Show the answer and reasoning

    No. Different words can have the same sorted output.

    For example aab and aba both map to aab, so the map is not one-to-one. Outputs such as aba never occur after sorting, so it is not onto the full eight-word set either. Reversing words, by contrast, has reversing again as its inverse.

What to carry forward

• Define one distinct outcome before counting histories, records or finished objects.
• Add disjoint cases; for two overlapping finite sets subtract the overlap once.
• Multiply complete stage counts only when every legal prefix has the stated continuation number and paths identify outcomes uniquely.
• Variable branches are counted by adding their completed leaf counts; a dead end contributes zero.
• Bijections preserve counts, complements require a finite stated universe, and division requires a positive equal multiplicity for every object.
• A fixed-order inclusion word encodes each subset exactly once, giving 2ⁿ subsets and one empty outcome when n = 0.