6.1 Sum, Product, and Bijection Principles

Chapter 5 counted how many times an algorithm performs an operation. Some loops were easy to count because their iteration space formed a line, rectangle, or triangle. Chapter 6 develops rules for counting more general sets of possibilities without listing every possibility one by one.

The central question is:

> How many objects satisfy a given description?

Before applying a formula, we must identify exactly what counts as one object and whether two construction paths can produce the same object.

Counting sets and outcomes

For a finite set $S$, its number of elements is written

If

then $|S|=3$.

A collection of possible results is often called an outcome space. Counting an outcome space means constructing a finite set of distinct outcomes and finding its cardinality.

For example, if a café offers tea, coffee, or juice, the set of drink choices is

so $|D|=3$.

The sum principle counts disjoint alternatives

Suppose an outcome can be produced in one of several mutually exclusive cases. If case 1 has $m$ possibilities and case 2 has $n$ possibilities, then the total is

This is the sum principle.

In set notation, if finite sets $A$ and $B$ are disjoint,

then

Example: choosing one workshop

A student may attend exactly one workshop:

• one of $4$ mathematics workshops; or

• one of $3$ design workshops.

No workshop belongs to both categories. Therefore

choices are available.

The words exactly one and or signal alternatives. But “or” alone does not guarantee that the cases are disjoint.

Why overlap causes double-counting

Suppose $20$ students study mathematics and $15$ study computer science, while $6$ study both. Adding $20+15$ counts the $6$ students twice.

The correct number studying at least one subject is

Section 6.4 will develop this correction systematically as inclusion–exclusion. For now, apply the simple sum principle only after checking that the cases cannot overlap.

The product principle counts sequential choices

Suppose an outcome is constructed in two stages:

1. stage 1 has $m$ possible choices;

2. after each stage-1 choice, stage 2 has $n$ possible choices.

Then the number of complete outcomes is

This is the product principle.

Example: building an outfit

Choose one of $3$ shirts and one of $2$ pairs of trousers. Each shirt can be paired with either pair of trousers, so

outfits exist.

The outcomes are ordered choice pairs:

This is the Cartesian product from Chapter 1:

More than two stages

If a password contains:

• one of $4$ symbols in the first position;

• one of $4$ symbols in the second position;

• one of $4$ symbols in the third position;

and repetition is allowed, then

passwords exist.

More generally, $k$ independent positions with $n$ choices each produce

strings.

The word “independent” here means that every listed choice remains available after earlier choices. It does not refer to probabilistic independence, which appears later in the course.

Decision trees reveal whether to add or multiply

A decision tree represents a sequence of choices:

• each branch is one available choice;

• each root-to-leaf path is one complete outcome;

• branches at one stage multiply across stages;

• separate terminal cases add.

Suppose a meal is either:

• a soup-only meal, with $3$ soup choices; or

• a main-and-dessert meal, with $4$ mains and $2$ desserts.

The soup case contributes $3$, while the two-stage case contributes

Since the two meal types are disjoint, the total is

Parentheses can make the structure explicit:

Counting is therefore not a hunt for keywords. It is a model of how a complete outcome is constructed.

Build a branching festival plan by deciding which gates represent alternatives and which represent sequential choices. The foundry expands every complete path, detects duplicate leaves, and turns the tree structure into a sum-of-products expression.

The bijection principle counts by reversible translation

Sometimes a set is difficult to count directly but has the same structure as a set we already know how to count.

A bijection between finite sets $A$ and $B$ is a function

that is both injective and surjective. Section 4.1 showed that this means every element of $B$ corresponds to exactly one element of $A$.

Therefore:

This is the bijection principle.

The method has three steps:

1. define a forward encoding from every object in $A$ to an object in $B$;

2. define how to reverse the encoding;

3. conclude that neither collisions nor missing targets occur.

Binary strings and subsets

Let

Every subset $S\subseteq U$ can be encoded by a binary string of length $n$:

• write $1$ in position $i$ if $u_i\in S$;

• write $0$ in position $i$ if $u_i\notin S$.

For $U=\{a,b,c,d\}$, the subset

corresponds to

The encoding is reversible: read the positions containing $1$ to recover the subset.

Each of the $n$ positions has $2$ choices, so the product principle gives

binary strings. By the bijection principle,

This proves the power-set count introduced in Chapter 1.

Why reversibility matters

An encoding that maps several source objects to the same code cannot transfer a count directly, because it is not injective.

An encoding that leaves some codes unused cannot establish equality of sizes, because it is not surjective.

For a valid counting bijection, every source object must receive exactly one code, and every permitted code must decode to exactly one source object.

Example: subsets of fixed size and binary strings

Subsets of $U$ containing exactly $k$ elements correspond to length-$n$ binary strings containing exactly $k$ ones.

The forward map marks membership with $1$. The reverse map reads the $1$ positions. Therefore these two sets have equal size.

Section 6.2 will give that common number a standard notation:

For now, the important idea is structural: a reversible representation can turn a difficult-looking collection into a familiar one.

Toggle elements of a live set and watch its binary passport update, then edit the passport to reconstruct the set. Challenge rounds include invalid-length codes and fixed-weight codes, making injectivity, surjectivity, and reversibility visible rather than assumed.

Section bridge

The product principle counts strings when each position keeps the same choices. What changes when an earlier choice removes an item from later availability, or when order should not matter? Section 6.2 develops permutations and combinations to answer those two questions.