Counting by Cases

The Central Idea

Suppose a finite set of outcomes \(S\) is divided into cases

such that every outcome belongs to exactly one case.

Then

and the cases are pairwise disjoint.

Therefore,

Cases Are a Partition

A good case split has two properties.

1. Exhaustive: every valid outcome belongs to some case.
2. Disjoint: no valid outcome belongs to more than one case.

When both properties hold, the cases form a partition of the outcome set.

A First Example

Count the integers from \(1\) through \(20\) that are either even or odd.

Every integer belongs to exactly one of the two cases:

• even;
• odd.

There are \(10\) even integers and \(10\) odd integers.

Therefore,

Why Cases Help

A complicated counting rule may behave differently under different circumstances.

Splitting into cases lets us replace one irregular problem with several regular problems.

Within each case, the product principle, complementary counting, or another counting tool may become easy to apply.

Example: Two Code Formats

A code has one of two formats:

• one letter followed by two digits;
• two letters followed by one digit.

Repetition is allowed.

Case 1:

Case 2:

Since the formats are distinct,

Case Labels Should Reflect Structure

Useful cases are usually based on a feature that changes the number of later choices.

Common case labels include:

• first symbol;
• last symbol;
• number of special elements;
• parity;
• which category is chosen;
• whether a distinguished object is included;
• which restriction becomes active.

Casework and the Sum Principle

Counting by cases is an organized use of the sum principle.

The difference is that the cases are often constructed by the solver rather than given explicitly in the problem.

The sum principle then combines the case totals.

Casework and the Product Principle

Within a case, sequential choices are often counted by multiplication.

A common pattern is

Example: Restricted Two-Digit Numbers

Count two-digit positive integers whose digits have different parity.

Split into two cases:

• odd tens digit and even ones digit;
• even tens digit and odd ones digit.

Case 1: Odd Tens, Even Ones

The tens digit has \(5\) odd choices:

The ones digit has \(5\) even choices:

Therefore,

Case 2: Even Tens, Odd Ones

The tens digit must be nonzero and even:

So there are \(4\) choices for the tens digit and \(5\) odd choices for the ones digit.

Adding the two disjoint cases gives

Cases Should Not Overlap

If two cases can contain the same outcome, simple addition overcounts.

In the parity example, a number cannot simultaneously have an odd tens digit and an even tens digit.

The cases are therefore disjoint.

Cases Must Cover Everything

A case split can also fail by omitting valid outcomes.

Before counting, ask:

Can every valid outcome be placed into one of my cases?

If the answer is no, the case list is incomplete.

Example: Strings by First Symbol

Suppose a three-character string is formed from the symbols

but strings beginning with \(A\) may use only \(B\) or \(C\) in the second position, while strings beginning with \(B,C,\) or \(D\) may use any symbol in later positions.

The first symbol changes the available continuations, so it is natural to split by the first symbol.

Case 1: First Symbol \(A\)

The first position is fixed as \(A\).

The second position has \(2\) allowed choices, and the third has \(4\) choices.

Case 2: First Symbol Not \(A\)

The first position has \(3\) choices:

Each remaining position has \(4\) choices.

Therefore,

Split Where the Rule Changes

The previous example illustrates a major strategy:

Split into cases at the point where the counting rule changes.

This often converts an irregular branch structure into a short list of regular products.

Counting by Number of Special Objects

Another common strategy is to classify outcomes by how many times a particular type of object appears.

For example, a string might contain:

• zero vowels;
• one vowel;
• two vowels;
• three vowels.

These cases are naturally disjoint because a string cannot contain two different numbers of vowels at once.

Example: Three-Letter Strings with at Most One Vowel

Use \(5\) vowels and \(21\) consonants, with repetition allowed.

The condition “at most one vowel” suggests two cases:

• no vowels;
• exactly one vowel.

Case 1: No Vowels

Every position contains a consonant:

Case 2: Exactly One Vowel

Choose the position of the vowel:

Choose the vowel:

Choose consonants for the remaining two positions:

Therefore,

The total is

Exactly, At Most, and At Least

Casework is especially natural when a condition is expressed using:

• exactly \(r\);
• at most \(r\);
• at least \(r\).

These conditions can often be decomposed into disjoint exact-count cases.

Example: At Least Two Successes

Suppose a five-stage binary process records success \(S\) or failure \(F\).

“At least two successes” can be split into:

• exactly \(2\) successes;
• exactly \(3\) successes;
• exactly \(4\) successes;
• exactly \(5\) successes.

This is valid casework because the number of successes uniquely determines the case.

Direct Casework versus Complementary Counting

The previous example can be counted by cases, but the complement may be shorter:

has complement

A good solver compares the case structure in both directions and chooses the simpler route.

Example: Committees with a Distinguished Person

A \(4\)-person committee is chosen from \(10\) people, one of whom is Alex.

Split the committees into two cases:

• Alex is on the committee;
• Alex is not on the committee.

Committee Case Counts

If Alex is included, choose the other \(3\) members from the remaining \(9\):

If Alex is excluded, choose all \(4\) members from the remaining \(9\):

Therefore,

This is Pascal's identity interpreted as counting by cases.

Casework Can Prove Identities

When one finite set is partitioned into disjoint cases, the resulting count can produce a combinatorial identity.

The identity is true because both sides count the same objects, but one side counts them all at once while the other counts them case by case.

Example: Largest Element of a Subset

Count the \(k\)-element subsets of

by their largest element.

If the largest element is \(j\), then the remaining \(k-1\) elements must be selected from

Therefore, that case contains

subsets.

A Case-Sum Identity

The possible largest elements are

Adding the case counts gives

This is sometimes called the hockey-stick identity in Pascal's triangle.

Cases Can Be Nested

A complicated case may itself be divided into smaller subcases.

The structure can be hierarchical:

while

Decision trees provide a visual representation of this nested case structure.

Example: Codes by First Character Type

A four-character code may begin with a letter or a digit.

If it begins with a letter, the remaining positions follow one rule.

If it begins with a digit, the remaining positions follow another.

The first-character type is therefore a natural top-level case split.

Cases by Parity

Parity often creates useful disjoint cases.

An integer is exactly one of:

Likewise, a sum may be classified according to whether its components have even or odd parity.

Example: Pairs with Even Sum

Choose an ordered pair

from

Count pairs for which \(a+b\) is even.

An even sum occurs in exactly two cases:

• both entries are even;
• both entries are odd.

Counting the Even-Sum Cases

There are \(5\) even numbers and \(5\) odd numbers in

Even-even pairs:

Odd-odd pairs:

Therefore,

Cases by Remainder Class

Congruence classes also create natural partitions.

Every integer has exactly one remainder modulo \(m\):

Therefore, a counting problem involving modular conditions can often be split by remainder.

Cases by a Distinguished Position

Strings and arrangements can often be classified by:

• the first position;
• the last position;
• the position of a special symbol;
• the first occurrence of a property.

The best position is the one that makes the remaining choices easiest to count.

Cases by a Distinguished Element

In subset and committee problems, ask whether a particular element is included.

This produces the disjoint split

This pattern appears repeatedly in recursive identities.

Casework and Recursive Counting

Some recurrence relations arise by splitting objects according to their first or last structural choice.

Each case reduces to a smaller version of the original problem.

The next lessons on recursive counting will develop this idea systematically.

Casework and Inclusion–Exclusion

Counting by cases works best when the cases are disjoint.

If natural categories overlap, either refine them into nonoverlapping cases or use inclusion–exclusion.

The choice depends on which representation is cleaner.

Refining Overlapping Cases

Suppose outcomes may satisfy properties \(A\) and \(B\).

The overlapping categories

can be refined into the disjoint cases

These three regions do not overlap.

Choosing the Right Number of Cases

Too few cases may leave complicated rules inside each case.

Too many cases may create unnecessary bookkeeping.

Good casework uses the smallest number of cases that makes each case easy to count.

Symmetric Cases

Sometimes several cases have identical counts because of symmetry.

Instead of computing each one separately, count one representative case and multiply by the number of symmetric cases.

This combines casework with the product principle.

Example: Exactly One Special Position

A four-character string contains exactly one occurrence of \(X\), and each non-\(X\) position has \(5\) choices.

There are \(4\) symmetric cases according to the position of \(X\).

Each case has

strings.

Therefore,

Common Error: Overlapping Cases

Suppose one case is

and another is

A string containing both belongs to both cases.

Adding the case totals directly would overcount.

Common Error: Missing a Case

If a problem is divided into:

• exactly one special symbol;
• exactly two special symbols;

but the original condition allows zero or three special symbols, the case split is incomplete.

Common Error: Counting the Same Case Two Different Ways and Adding

Two formulas may be alternative methods for counting the same case.

They should not be added unless they represent disjoint collections.

Always ask whether the formulas count different outcomes or merely describe the same outcomes differently.

Common Error: Using Case Labels That Do Not Determine the Rule

A useful case split should simplify the remaining choices.

If the same complicated restriction still behaves differently inside a case, the case may need further refinement.

Common Error: Forgetting the Sum at the End

Counting each case separately is only part of the solution.

If the cases form a partition, the final step is to add:

A Reliable Procedure

1. Define the complete set of valid outcomes.
2. Identify a feature that naturally separates the outcomes.
3. Create cases that cover every valid outcome.
4. Check that no outcome belongs to more than one case.
5. Count each case using the simplest available method.
6. Exploit symmetry when several cases have the same size.
7. Add the case totals.
8. Check whether a complement or inclusion–exclusion would have been simpler.

Example: Full Casework Workflow

Count three-digit positive integers whose first and last digits have the same parity.

Split into two disjoint cases:

• first and last digits both odd;
• first and last digits both even.

Case 1: odd first digit and odd last digit.

Case 2: even nonzero first digit and even last digit.

Therefore,

Practice 1: Two Formats

A code is either one letter followed by one digit or two digits followed by one letter. Repetition is allowed. How many codes are possible?

Practice 2: Same Parity

How many ordered pairs

have \(a\) and \(b\) with the same parity?

Practice 3: Different Parity

How many two-digit positive integers have digits of different parity?

Practice 4: Distinguished Committee Member

A \(5\)-person committee is chosen from \(12\) people, including Jordan. Express the total number of committees as the sum of the cases “Jordan is included” and “Jordan is excluded.”

Practice 5: At Most One Vowel

How many two-letter strings contain at most one vowel, assuming \(5\) vowels, \(21\) consonants, and repetition allowed?

Practice 6: Exactly One \(X\)

A four-character string is formed from \(\{X,A,B,C\}\). How many strings contain exactly one \(X\)?

Practice 7: Even Sum

How many ordered pairs from

have an even sum?

Practice 8: Split by First Digit

Count three-digit positive integers whose first digit is either \(1\) or greater than \(1\). Verify that the case totals sum to \(900\).

Practice 9: Largest Element

How many \(3\)-element subsets of

have largest element \(5\)?

Practice 10: Identify the Error

A student counts strings containing \(A\) or \(B\) by adding the case “contains \(A\)” to the case “contains \(B\).” What problem can occur?

Practice Answers

Practice 1

Case 1:

Case 2:

Therefore,

Practice 2

There are \(4\) even numbers and \(4\) odd numbers.

Even-even:

Odd-odd:

Therefore,

Practice 3

Odd tens and even ones:

Even nonzero tens and odd ones:

Therefore,

Practice 4

Jordan included:

Jordan excluded:

Therefore,

Practice 5

No vowels:

Exactly one vowel:

Therefore,

Practice 6

Choose the position of \(X\):

Each remaining position has \(3\) non-\(X\) choices:

Practice 7

There are \(6\) even and \(6\) odd numbers.

Therefore,

Practice 8

First digit \(1\):

First digit greater than \(1\):

Therefore,

Practice 9

If \(5\) is the largest element, choose the other two elements from

Thus,

Practice 10

The cases can overlap. A string containing both \(A\) and \(B\) belongs to both cases and would be counted twice.

The cases must be refined into disjoint cases or the overlap must be corrected using inclusion–exclusion.

What to Remember

Counting by cases partitions one outcome set into disjoint pieces:

• Cases must be exhaustive.
• Cases must be mutually exclusive.
• Split where the counting rule changes.
• Use multiplication within a case when choices occur in stages.
• Exploit symmetry when several cases have equal size.
• Refine overlapping categories or use inclusion–exclusion.
• Compare casework with complementary counting before choosing a method.

The central habit is to design cases that make the remaining counting simple.

Where We Go Next

Counting by cases simplifies a problem by separating different structural situations. Many problems add another difficulty: some potential outcomes are forbidden, constrained, or conditionally available.

The next lesson, Counting with Restrictions, develops systematic methods for incorporating those constraints into counting arguments.