06 Fundamental Counting Principles

Choosing the right counting principle

Counting begins by identifying how an outcome is constructed. Ask whether the outcome comes from one alternative or from several stages, and determine whether different cases can overlap.

The addition principle applies when exactly one of several mutually exclusive cases occurs. If one dessert can be chosen from 4 cakes or 3 pies, the total is

because no dessert belongs to both categories.

The multiplication principle applies when an outcome is built through successive stages. If the stages have $a_1,a_2,\ldots,a_k$ choices, the total is

For a code consisting of two letters followed by three digits, with repetition allowed, the count is

If the number of choices changes at each stage, multiply the stage-specific counts. For example, choosing a president and a vice president from 8 people gives $8\cdot7=56$, because the first choice leaves 7 people.

Takeaway: use addition for mutually exclusive alternatives and multiplication for sequential choices.

Factorials and arrangements

A factorial is defined for every nonnegative integer by

with the special definition

The factorial $n!$ counts the ways to arrange $n$ distinct objects in a line. Thus, 5 distinct books can be arranged in

ways.

Factorials simplify products of consecutive integers. For example,

This expression explains why ordered selections lead naturally to permutation formulas: the first position has $n$ choices, the next has $n-1$, and so on.

Takeaway: factorials count complete arrangements and provide compact notation for consecutive products.

Permutations and repeated objects

A permutation is an arrangement in which order matters. Selecting a president, secretary, and treasurer from 10 members is ordered because assigning the same three people to different offices produces a different outcome.

The number of ordered selections of $r$ objects from $n$ distinct objects is

For the officer example,

When objects repeat and identical objects cannot be distinguished, divide by the factorial of each repetition count. If there are $n$ total objects with repetition counts $r_1,r_2,\ldots,r_k$, the number of distinct arrangements is

For BANANA, there are 6 letters, with 3 A's, 2 N's, and 1 B, so the number of distinct arrangements is

Takeaway: use permutations for ordered selections, and correct for indistinguishable repetitions by dividing by their factorials.

Combinations and binomial coefficients

A combination is a selection in which order does not matter. A committee containing the same people is unchanged by rearranging the order in which its members are listed.

The number of combinations of $r$ objects chosen from $n$ distinct objects is

For example, the number of 4-person committees from 12 people is

Test the distinction by asking whether swapping two selected objects changes the outcome. If it does, use $P(n,r)$; if it does not, use $\binom{n}{r}$. Their relationship is

because each unordered group of $r$ objects can be placed in $r!$ orders.

Binomial coefficients are the values $\binom{n}{r}$. They obey the symmetry rule

and Pascal's identity

The symmetry rule reflects the equivalence between choosing what to include and choosing what to exclude.

Takeaway: decide whether order matters before selecting a permutation or combination formula.

Guaranteeing repetition

The pigeonhole principle proves that some repetition must occur when there are more objects than available categories. If more than $m$ objects are distributed among $m$ boxes, at least one box contains at least two objects.

For instance, 13 people assigned to 12 birth-month categories guarantee that two people share a birth month.

The generalized form states that if $n$ objects are distributed among $m$ boxes, some box contains at least

objects, where the ceiling gives the least integer greater than or equal to the input. Thus, assigning 25 students to 6 groups forces some group to contain at least

students.

To guarantee that some box contains at least $k$ objects, it is enough to show

If every box contained at most $k-1$ objects, there could be at most $m(k-1)$ objects altogether.

Takeaway: compare the number of objects with the number of categories to prove that a repeated value or shared property is unavoidable.

Handling restrictions without double-counting

Restrictions should be identified before choosing a formula. Common methods include reducing choices directly, counting a complement, grouping required objects into blocks, separating mutually exclusive cases, and using the inclusion–exclusion principle for overlapping conditions.

Direct restriction: For a 5-digit code using digits from 0 through 9, with no repetition and a first digit that cannot be 0, the successive counts are $9,9,8,7,6$. Therefore, the total is

Complement: If two particular people cannot both be on a 4-person committee from 10 people, subtract committees containing both from all committees:

Blocks: If A and B must be adjacent in an arrangement of A, B, C, D, and E, treat AB as one block. The four objects can be arranged in $4!$ ways, and the block can be ordered in $2!$ ways, giving

Cases: A 3-person committee from 5 engineers and 4 designers must contain at least one designer. The complement is shorter:

For overlapping restrictions, use

The intersection is subtracted because it was counted in both individual cases.

Takeaway: make restrictions explicit and choose the method that prevents omissions and double-counting.

A systematic workflow

A reliable solution can be organized as a short decision process:

1. Define exactly what counts as one outcome.

2. Decide whether order matters.

3. Determine whether repetition is allowed and whether repeated objects are distinguishable.

4. Separate the possibilities into mutually exclusive and exhaustive cases when needed.

5. Use addition for alternatives and multiplication for stages.

6. Apply factorials, permutations, or combinations only after modeling the outcome.

7. Handle restrictions with direct choice reduction, complements, blocks, cases, or inclusion–exclusion.

8. Check that every outcome was counted once and only once.

A final reasonableness check is useful. If order is ignored, the answer should not exceed the corresponding ordered count; indeed,

If a restriction is added, the restricted count should not exceed the unrestricted count.

The central habit is to describe the structure of an outcome before calculating. Once the structure is clear, the appropriate counting principle usually follows.