Counting Techniques: Sum Rule, Product Rule, Permutations, and Combinations

Welcome to the first lesson of our second module, "Core Counting Principles and Bijections." In the previous module, we built a robust toolkit of proof techniques—induction, contradiction, and the Extremal Principle. Those methods helped us answer questions about possibility and structure, like "Is it possible...?" or "What properties must exist?". Now, we pivot to a different, though related, question: "How many...?"

This is the heart of enumerative combinatorics. Your goal of mastering Olympiad-level problems requires absolute fluency in the fundamental principles of counting. While you may have encountered these ideas before, our purpose here is to formalize them. We will build them from the ground up, starting with the two pillars of counting—the Sum and Product Rules—and then using them to construct the concepts of permutations and combinations. Mastering this formalization is the key to systematically breaking down complex problems instead of relying on intuition alone.

The Two Pillars: Addition and Multiplication

At its core, almost every counting problem can be broken down into two fundamental operations: adding or multiplying. The challenge is knowing when to do which. The Sum Rule applies when you have a choice between several disjoint options (an "OR" situation). The Product Rule applies when a task consists of a sequence of independent steps (an "AND" situation).

Discrete Math II - 6.1.1 The Rules of Sum and Product

This video provides a clear, formal introduction to the Sum and Product Rules, grounding them in set theory. The lecturer, Kimberly Brehm, explains the underlying logic with simple examples.

Please watch the following two segments: The Rule of Sum: Watch this part for the formal definition. Notice how it's linked to the cardinality of the union of disjoint sets. The idea that the options cannot overlap is crucial. The Rule of Product: Now watch this segment. Pay attention to how a procedure is broken down into a sequence of tasks. The concept is formalized using the Cartesian product of sets.

The tree diagram shown in the video for the Rule of Product is a great way to visualize why we multiply. Each stage in the sequence branches out from the previous one, and the total number of outcomes is the number of leaves at the end of the tree.

This tree diagram illustrates the Product Rule. Two choices for the first step (A1, A2) followed by three choices for the second step (B1, B2, B3) result in 2 × 3 = 6 total possible sequences.

Let's solidify these ideas and see a wider array of applications with a reading.

[PDF] Contents 4 Counting Principles - Evan Dummit

This document by Evan Dummit presents the same principles with several concise examples that show their versatility.

Please read the section on "Addition and Multiplication Principles". Start at the beginning of the document and read through all the examples down to the one about the telephone numbers. As you read, focus on these points: Subsets: Notice how counting the subsets of a set becomes a sequence of binary choices (in or out), a classic application of the product rule. Functions: See how the number of functions from a set A to a set B is determined by a sequence of choices for where to map each element of A. Divisors: Given your background in number theory, pay close attention to the example of counting divisors. The prime factorization n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} allows you to count divisors by choosing the exponent for each prime factor independently. This is a powerful application of the Product Rule.

Permutations: Counting Ordered Arrangements

Now that we have the sum and product rules, we can build more specialized counting tools. The first is for situations where order matters. A permutation is an arrangement of objects in a specific order.

For example, how many ways can we arrange the letters A, B, C?
Using the product rule, we have:

3 choices for the first position.
2 choices for the second position (since one letter is used).
1 choice for the final position.
Total arrangements: $3 \times 2 \times 1 = 6$ . These are ABC, ACB, BAC, BCA, CAB, CBA.

This product of descending integers is so common it gets its own notation: the factorial. We define $n! = n \times (n - 1) \times \dots \times 2 \times 1$ , with the special case $0! = 1$ .

What if we only want to arrange some of the objects? For example, how many ways can we choose and arrange 2 letters from the set {A, B, C, D}?

4 choices for the first position.
3 choices for the second position.
Total arrangements: $4 \times 3 = 12$ .

This is a permutation of 4 items taken 2 at a time, denoted $P (4, 2)$ or $^{4} P_{2}$ . The general formula is derived directly from the product rule.

[PDF] Contents 4 Counting Principles - Evan Dummit

Let's return to Evan Dummit's notes for a formal definition.

In the same document, read the first part of the section on "Permutations and Combinations". Please focus on the material related to permutations, from the start of the section down to the example about playoff teams. Pay close attention to the derivation of the formula P(n,k) = \frac{n!}{(n-k)!} from the product rule.

Combinations: Counting Unordered Selections

What happens if order does not matter? If we are just selecting a group of items, and the arrangement within the group is irrelevant, we are dealing with combinations.

Think about picking a 2-person committee from {Alice, Bob, Charles}.

If we use the permutation formula $P (3, 2)$ , we get $3 \times 2 = 6$ ordered pairs: (A, B), (B, A), (A, C), (C, A), (B, C), (C, B).
But for a committee, {Alice, Bob} is the same as {Bob, Alice}. We have counted every committee twice! The actual committees are just {A, B}, {A, C}, {B, C}. There are only 3.

To get the number of combinations, we can start with the number of permutations and then divide by the number of ways to order the chosen items. This corrects for the overcounting.

This image illustrates the difference. To form permutations of 2 balls from 3, we arrange them, yielding 6 distinct outcomes. To form combinations, we just select them, so the pairs {a, b}, {a, c}, and {b, c} are the only 3 outcomes, regardless of the order they were picked.

The number of ways to choose $k$ items from a set of $n$ without regard to order is denoted $(k n)$ (read "n choose k") or $C (n, k)$ . It's calculated by taking the number of permutations and dividing by $k!$ , the number of ways to arrange the $k$ chosen items.

(k n) = \frac{P ( n , k )}{k !} = \frac{n !}{k ! ( n - k )!}

AMC 10 Preparation - Class #1: Counting and Probability

This video, aimed at AMC 10 preparation, provides a very clear, intuitive explanation of this overcounting correction.

Watch the segment from this explanation. The speaker walks through a problem of picking 3 balls from 5, first calculating the permutations (5x4x3 = 60), and then reasoning about why this needs to be divided by 3! = 6 to correct for the fact that the order of the three chosen balls doesn't matter. This idea of "strategic overcounting and correction" is a vital problem-solving technique.

Putting It All Together

Let's review the framework for approaching a basic counting problem:

Identify the Task: What constitutes a single successful outcome?
Break It Down: Can the task be broken into a sequence of steps (Product Rule) or a set of mutually exclusive cases (Sum Rule)?
Check for Order: In each step or case, does the order in which you select items matter?
- Yes: Use Permutations ( $P (n, k)$ ).
- No: Use Combinations ( $(k n)$ ).
Calculate: Combine the results using the appropriate rules.

This systematic approach is your primary weapon. Let's see it applied to a problem that combines these ideas.

AMC 10 Preparation - Class #1: Counting and Probability

Let's return to the AMC 10 video and see a more complex problem solved from scratch.

Watch the walkthrough of the problem about building towers from colored cubes, starting at the beginning of the problem. The problem asks for the number of different towers of height 8 that can be built with specific sets of colored cubes. The initial approach shown uses casework (Sum Rule): Case 1: Leave out a red cube. Case 2: Leave out a blue cube. Case 3: Leave out a green cube. Within each case, the problem becomes one of arranging items where some are identical (e.g., arrange 1 Red, 3 Blue, 4 Green). This is a classic combination-style problem. The number of arrangements of n objects where there are n_1 of type 1, n_2 of type 2, etc., is \frac{n!}{n_1! n_2! \dots n_k!}. This is a direct extension of the logic for \binom{n}{k}. This formula is derived by choosing the positions for each type of item sequentially. For example, to arrange RBBBG, you have \binom{5}{1} ways to place the R, then \binom{4}{3} ways to place the Bs, and \binom{1}{1} way to place the G. This gives \frac{5!}{1!4!} \times \frac{4!}{3!1!} \times \frac{1!}{1!0!} = \frac{5!}{1!3!1!}. (As an interesting aside, you can watch the rest of the clip, from 22:16 to the end, to see a more elegant, non-casework solution. This is the kind of clever thinking you'll develop with practice!)

Practice Problems

Here are a few problems to practice these fundamental concepts. For each one, consciously apply the framework: Sum Rule, Product Rule, Permutation, or Combination?

Committee Selection: A club has 10 men and 12 women.
a. How many ways can a committee of 5 people be chosen?
b. How many ways can a committee of 5 be chosen if it must consist of 2 men and 3 women?
c. How many ways can a President, Vice-President, and Treasurer be chosen from the 22 members?
License Plates: A state issues license plates consisting of 3 letters followed by 4 digits.

a. How many different license plates can be made if repetitions are allowed?
b. How many can be made if repetitions are *not* allowed?
c. How many can be made if repetitions are allowed, but the plate cannot contain the letter 'O' and the first digit cannot be '0'?

3. Word Arrangements: How many distinct arrangements of the letters in the word "ENGINEERING" are there?
Hint: This is similar to the cube tower problem. Count the total letters and the frequencies of each repeated letter.

Card Hands: From a standard 52-card deck, how many 5-card hands contain at least one Ace?
Hint: It's difficult to count the cases "exactly one Ace," "exactly two Aces," etc. and add them up. Consider using complementary counting: find the total number of 5-card hands and subtract the number of hands that have zero Aces.

Conclusion

Today, we've formalized the foundational tools of combinatorics. You've seen how the simple ideas of the Sum and Product Rules can be used to construct the more specialized, but powerful, formulas for permutations and combinations.

Key Takeaways:

Sum Rule: Use for disjoint cases (OR). The total is the sum of the possibilities for each case.
Product Rule: Use for sequences of tasks (AND). The total is the product of the possibilities for each step.
Permutations $P (n, k)$ : Use when order matters. It counts ordered arrangements.
Combinations $(k n)$ : Use when order does not matter. It counts unordered subsets. Derived by correcting the permutation formula for overcounting.
Problem-Solving Framework: Always start by identifying if you need to add cases or multiply steps, and whether order is important.

In our next lesson, we will explore a powerful application of these principles called the "Stars and Bars" method. It provides a clever, systematic way to solve a very common class of problems: distributing identical items into distinct bins.

Recommended resources