Combinatorics Counting Rules

The sum rule and the product rule

The sum rule handles a choice between separate options. If one task can be done in a ways and a second, mutually exclusive task can be done in b ways, then the number of ways to do one task or the other is a plus b. The word or, together with the requirement that the options do not overlap, is the signal for addition.

The product rule handles a sequence of independent decisions. If a procedure consists of a first step with a outcomes followed by a second step with b outcomes, and the count for the second step does not depend on which outcome the first produced, then the whole procedure has a times b outcomes. The word and, joining stages that must all happen, is the signal for multiplication. For example, choosing a 3-character code from 26 letters with repetition allowed is 26 times 26 times 26, because each position is an independent decision with 26 outcomes.

• Sum rule: mutually exclusive alternatives, count with addition.
• Product rule: independent successive stages, count with multiplication.
• The words or and and are strong hints for which rule applies.

Permutations: when order matters

A permutation counts arrangements in which the order of the chosen items is part of the answer. If you are lining up people, ranking finishers, or filling distinct positions, swapping two items produces a genuinely different outcome, so order matters. The number of ways to arrange all n distinct items in a row is n factorial, written n exclamation, which means n times n minus 1 times n minus 2, down to 1.

When you arrange only r of the n items in order, the count is the falling product n times n minus 1, continuing for r factors. Equivalently it is n factorial divided by the quantity n minus r factorial, usually written P of n and r. For instance, awarding gold, silver, and bronze among 8 runners is 8 times 7 times 6, which is 336, because the three medals are distinct positions and order clearly matters.

Combinations: when order does not matter

A combination counts selections in which order is irrelevant. Choosing a committee, dealing a hand of cards, or picking a subset are all situations where rearranging the chosen items gives the same result. The number of ways to choose r items from n, written C of n and r or n choose r, equals n factorial divided by the product of r factorial and n minus r factorial.

The relationship to permutations makes the formula memorable. Every unordered selection of r items can be ordered in r factorial ways, so combinations are just permutations with that overcounting divided out: C of n and r equals P of n and r divided by r factorial. Choosing a 3-person committee from 8 people is 8 choose 3, which is 8 times 7 times 6 divided by 3 factorial, giving 56, exactly one sixth of the 336 ordered arrangements because the 6 orderings of each committee collapse into one.

• Ask first: does swapping two chosen items change the outcome?
• If yes, order matters, use a permutation.
• If no, order is irrelevant, use a combination.
• Combinations equal permutations divided by r factorial.

A worked comparison

Suppose a club of 10 members must select officers. If the roles are president, secretary, and treasurer, order matters because the positions are distinct, so the count is P of 10 and 3, which is 10 times 9 times 8, equal to 720. If instead the club simply forms a 3-person planning group with no titles, order does not matter, so the count is 10 choose 3, which is 720 divided by 6, equal to 120.

The two questions use the same numbers 10 and 3 yet differ by a factor of 6, precisely the 3 factorial orderings of three chosen people. When in doubt, describe two outcomes that use the same items in different orders and decide whether your problem counts them as the same or as different.

The pigeonhole principle

The pigeonhole principle states that if you place more than n items into n containers, then at least one container holds two or more items. Put another way, if there are more pigeons than pigeonholes, some hole has at least two pigeons. It sounds almost too obvious to be useful, yet it proves the existence of collisions that would be hard to demonstrate by direct construction.

A clean example: among any 13 people, at least two share a birth month, because there are only 12 months to distribute 13 people among. A generalized version says that distributing m items into n containers forces some container to hold at least the ceiling of m divided by n items. This principle is central to arguments about hashing, where more keys than buckets guarantee at least one collision, and it appears throughout discrete mathematics whenever you need to prove something must repeat.

Choosing the right tool under pressure

When a counting problem appears, run through a short diagnostic. First, break the process into stages and ask whether you are making a single choice among alternatives, which points to the sum rule, or a sequence of decisions, which points to the product rule. Second, wherever you select items, decide whether order matters to choose between permutations and combinations. Third, if the question asks whether a repeat or collision is unavoidable, think pigeonhole.

Most exam-level problems combine these moves rather than applying a single rule once. A committee with a designated chair mixes a combination for the members with a separate choice for the chair. Break the problem into stages, apply the right rule to each stage, and multiply the stage counts together.