Chapter 1 — Front Matter
Purpose and Overview
Every field of mathematics has a central question. Calculus asks how things change continuously. Algebra asks how symbolic relationships can be solved and transformed. Geometry asks about shape, space, and measurement. Combinatorics asks a deceptively simple question: In how many ways can something happen?
That question turns out to be deep. Answering it carefully requires precise language, structured reasoning, algebraic tools, and sometimes proof. This chapter introduces combinatorics as a discipline — not a collection of tricks, but a coherent way of thinking about arrangements, selections, patterns, and finite structures.
By the end of this chapter, you should be able to describe what combinatorics studies, distinguish arrangements from selections, use the vocabulary of sets and sample spaces, list outcomes systematically, build and read tree diagrams, organize cases into tables, and understand why proof matters. These habits of mind will carry you through every topic in this book.
Opening Question
Suppose you are designing a password system. Passwords must be exactly 8 characters long. Each character can be any of the 26 lowercase letters. How many different passwords are possible? Should you list them all? Even at one per millisecond, it would take more than 6,000 years. And yet the answer can be calculated exactly, in one line, by understanding the structure of the problem. That is combinatorics.
14Sections
10Objectives
16Key Terms
8+Worked Examples
Learning Objectives
- 1Describe combinatorics as the study of counting, arranging, selecting, and proving facts about finite or discrete structures.
- 2Distinguish between arrangements (order matters) and selections (order does not matter).
- 3Use the vocabulary of sets, elements, outcomes, and sample spaces in a combinatorial context.
- 4List all outcomes of a simple experiment systematically.
- 5Construct and read a tree diagram for a multi-step choice.
- 6Organize outcomes using a table or case list.
- 7Explain why combinatorics does not require calculus, limits, or infinite series analysis.
- 8Identify how combinatorics connects to probability, computing, cryptography, networks, scheduling, and design.
- 9Recognize and correct common early counting errors.
- 10Explain why a count must be justified by the structure of the problem, not just arrived at numerically.
Sections 1.1 – 1.5
The Discipline: What Combinatorics Studies and Why
The Field · Structured Reasoning · Arrangements vs Selections · Finite Sets · Sample Spaces
Section 1.1
What Combinatorics Studies
The word combinatorics comes from a Latin root meaning to combine. It describes a field of mathematics concerned with combinations, arrangements, groupings, and the counting of finite collections. Combinatorics is not one narrow technique. It is an entire mathematical discipline with its own questions, tools, proof methods, and applications.
At its core, combinatorics answers questions of this form:
| Type of Question | Example |
|---|
| Arrangement | How many ways can 5 books be ordered on a shelf? |
| Selection | How many ways can a committee of 3 be chosen from 10 people? |
| Distribution | How many ways can 12 identical candies be distributed among 4 children? |
| Existence | Must some two of these 13 people share a birth month? |
| Proof | Why is the formula for choosing k objects from n always an integer? |
Combinatorics is not calculus. This distinction matters and will be repeated throughout the book. Calculus studies continuous change: limits, derivatives, integrals, and infinite series. Combinatorics studies discrete, finite structures: sets, sequences, graphs, and codes. A student who has completed Algebra II has all the mathematical background needed to begin this book. No calculus is required.
The Tools of Combinatorics
Counting rules — principles that systematize how to count choices, arrangements, and selections.
Algebraic notation — expressions such as n!, P(n,k), and C(n,k) that encode counts compactly.
Set language — precise vocabulary for describing collections of objects.
Proof — logical justification for counting formulas and existence claims.
Recursion — definitions and arguments that build answers from smaller cases.
Generating functions — algebraic objects that encode sequences of counts.
Graph structures — finite diagrams of relationships between objects.
Section 1.2
Counting as Structured Reasoning
In ordinary conversation, counting means reciting numbers: one, two, three. In combinatorics, counting means determining the exact size of a set of possibilities without examining each one individually — and being able to justify that determination. This is structured reasoning about quantity.
The core process of combinatorial reasoning has six stages. This process will reappear throughout every chapter of this book.
The Combinatorial Reasoning Process
1Identify
2Represent
3Count
4Justify
5Check
6Explain
| Stage | What It Requires |
|---|
| Identify | Understand what one outcome is; what makes two outcomes the same or different; what constraints apply |
| Represent | Choose a representation: list, diagram, set, sequence, equation, graph, or recursion |
| Count | Apply a method that matches the structure of the problem exactly |
| Justify | Explain why the method is correct for this problem — not just for similar-looking problems |
| Check | Verify that no outcome was counted twice (overcounting) and none was missed (undercounting) |
| Explain | Connect the numerical answer back to the original situation in clear language |
Why Process Matters More Than Formula
Most errors in combinatorics come from skipping the Identify step and jumping straight to a formula that looks familiar. A formula is only correct when the structure of the problem matches what the formula assumes. The process protects against this error.
Section 1.3
Objects, Arrangements, and Selections
Two of the most important ideas in combinatorics are arrangements and selections. These words have precise technical meanings that differ from casual usage.
Arrangements — Order Matters
An arrangement is an ordered sequence of objects. Two arrangements are considered different if the same objects appear in a different order. Consider the three letters A, B, C arranged in a row:
ABC ACB BAC BCA CAB CBA
These are six different arrangements, even though they all use the same three letters. The order is what distinguishes them. In later chapters, arrangements will be studied formally under the name permutations.
Selections — Order Does Not Matter
A selection is an unordered collection of objects. Two selections are the same if they consist of the same objects, regardless of any ordering. Choosing two letters from A, B, C to form a group:
{A, B} {A, C} {B, C}
There are only three distinct selections, because {A, B} and {B, A} are the same group — the same two letters were chosen. In later chapters, selections will be studied formally under the name combinations.
The Most Important Early Question
Does order matter here? If changing the order of objects produces a different outcome, the problem involves arrangements. If reordering the same objects produces the same outcome, the problem involves selections. Many counting errors arise from confusing these two types. An arrangement formula applied to a selection problem will produce an answer that is too large.
Section 1.4
Finite Sets and Discrete Structures
Combinatorics operates in the world of finite sets and discrete structures. A set is a well-defined collection of distinct objects. The objects in a set are called its elements or members.
| Concept | Definition | Example |
|---|
| Set | A well-defined collection of distinct objects enclosed in braces | A = {1, 2, 3, 4, 5} |
| Element | A single object belonging to a set | 3 ∈ A |
| Cardinality | The number of elements in a set; written |A| | |A| = 5 |
| Finite set | A set with a specific, countable number of elements | {red, blue, green} |
| Discrete structure | A mathematical object whose elements are individually distinguishable and separate | A graph, a sequence, a code |
Combinatorics works almost exclusively with finite sets. When we count the number of arrangements or selections, we are computing the size of a finite set of outcomes. This is in contrast to calculus, which studies continuous objects — functions defined at every real number, areas under curves, and rates of change.
Combinatorics is part of discrete mathematics: the study of mathematical structures that are fundamentally countable and separate. The only foundation required is algebra and discrete reasoning.
Section 1.5
Outcomes and Sample Spaces
An outcome is a single result of a process, experiment, or choice procedure. The sample space is the complete collection of all possible outcomes, typically written as the set S.
| Experiment | Sample Space S | |S| |
|---|
| Flip a coin once | {Heads, Tails} | 2 |
| Roll a standard die | {1, 2, 3, 4, 5, 6} | 6 |
| Choose a letter from {A, B, C} | {A, B, C} | 3 |
| Choose 2 letters from {A, B, C} (ordered, no repeat) | {AB, AC, BA, BC, CA, CB} | 6 |
Combinatorics is often concerned with computing |S| — the size of the sample space — and with counting how many outcomes in S satisfy some given condition. For small sample spaces, direct inspection works. For large sample spaces, the counting tools developed in Chapters 2 through 14 are necessary.
Notice how carefully outcomes must be defined. In the last row of the table above, AB and BA are counted as different outcomes because the problem specifies ordered pairs. Had the problem asked for unordered pairs, AB and BA would be the same outcome and the sample space would have only 3 elements.
Sections 1.6 – 1.9
Listing, Diagrams, and Structural Counting
Systematic Lists · Tree Diagrams · Tables · Counting Without Enumeration
Section 1.6
Listing Systematically
Before any formulas are developed, every student of combinatorics should practice listing outcomes systematically for small problems. Systematic listing is the foundation of combinatorial reasoning. It makes the structure of a problem visible. A systematic list is a complete, non-repetitive enumeration of all outcomes — organized so that nothing is accidentally skipped or accidentally repeated.
The most reliable method: fix one feature and vary the rest, then move to the next value of the fixed feature and repeat.
Example 1.6.1
Two-letter sequences with repetition allowed
- ProblemList all two-letter sequences from {A, B, C} if letters can repeat.
- RepresentAn ordered pair (first letter, second letter). Repetition is allowed, so AA is valid.
- List
First letter A: AA, AB, AC
First letter B: BA, BB, BC
First letter C: CA, CB, CC
- Count3 groups of 3 = 9 outcomes.
- InterpretEach group exhausts all second-letter choices for one fixed first letter. No outcome is listed twice. No outcome is skipped.
Answer: 9 two-letter sequences (with repetition allowed).
Example 1.6.2
Two-letter sequences without repetition
- ProblemList all two-letter sequences from {A, B, C} if letters cannot repeat.
- RepresentAn ordered pair where both letters are different. Exclude any pair where both positions show the same letter.
- List
First letter A: AB, AC
First letter B: BA, BC
First letter C: CA, CB
- Count3 groups of 2 = 6 outcomes.
- CheckRemoving repetition reduces the count from 9 to 6. AA, BB, and CC are correctly excluded.
Answer: 6 two-letter sequences (without repetition).
Why Listing Is Not Enough
Systematic listing works for small problems. But for 8-character passwords from a 26-letter alphabet, the sample space has 268 = 208,827,064,576 entries. Listing is the starting point — it teaches you what the structure looks like. Formulas allow you to scale that reasoning to cases where listing is impossible.
Section 1.7
Tree Diagrams
A tree diagram is a branching visual structure that organizes multi-step choices. Each branch represents one possible choice at one step. Following a path from the root to a leaf traces one complete outcome. Tree diagrams are especially useful when different choices affect what options are available at later steps.
How to Build a Tree Diagram
| Step | Action |
|---|
| 1 | Start with a single point: the root. |
| 2 | Draw one branch for each possible first choice, labeled with that choice. |
| 3 | From each first-choice branch, draw one branch for each possible second choice. |
| 4 | Continue until the tree reaches the final choice level. |
| 5 | Each endpoint (leaf) represents one complete outcome. Count the leaves. |
Example 1.7.1
Two-course meal — building a tree
- ProblemA café offers 3 appetizers (Soup, Salad, Bread) and 2 main courses (Pasta, Fish). How many different two-course meals are possible?
- RepresentA meal is an ordered pair (appetizer, main). The tree has two levels. Level 1: three branches (Soup, Salad, Bread). Level 2: from each appetizer branch, two sub-branches (Pasta, Fish).
- List Leaves
Soup-Pasta, Soup-Fish
Salad-Pasta, Salad-Fish
Bread-Pasta, Bread-Fish
- Count6 leaves = 6 possible meals.
- Check3 appetizers × 2 main courses = 6. The multiplication reflects the branching structure of the tree.
- InterpretThe two choices are independent: no matter which appetizer is chosen, both main courses remain available.
Answer: 6 possible two-course meals.
Example 1.7.2
Selecting Chair then Secretary — a tree with constraints
- ProblemFrom four candidates — Alex, Blake, Cameron, Dana — a club selects a chair, then a secretary. The same person cannot hold both positions. List all outcomes.
- IdentifyThis is an arrangement problem. The chair role and secretary role are different, so order matters. No repetition: one person, one role.
- TreeLevel 1: four branches (Alex/chair, Blake/chair, Cameron/chair, Dana/chair). From each, three sub-branches (everyone except the chair).
- Count4 × 3 = 12 outcomes.
- CheckAlex-Blake and Blake-Alex are different outcomes — different role assignments. Order matters here.
Answer: 12 possible chair-secretary assignments.
Section 1.8
Tables and Case Organization
For problems involving two independent choices, a table is an efficient organizational tool. Label rows with the choices for one variable and columns with the choices for another. Each cell is one outcome.
Example 1.8.1
Rolling two dice — using a table
- ProblemA red die and a blue die are each rolled. How many outcomes are possible?
- RepresentA 6×6 table. Rows = red die (1–6), columns = blue die (1–6). Each cell = ordered pair (red result, blue result).
- Count6 × 6 = 36 cells = 36 outcomes.
- InterpretSince the dice are different colors, (red=3, blue=5) is a different outcome from (red=5, blue=3). Order within the pair matters.
Answer: 36 possible outcomes.
Casework
Casework is the strategy of dividing a counting problem into exhaustive, non-overlapping cases and adding the counts from each case. The cases must satisfy two conditions:
Two Requirements for Valid Casework
Exhaustive — Every possible outcome falls into at least one case. Nothing is left uncounted.
Non-overlapping (disjoint) — No outcome falls into more than one case. Nothing is counted twice.
When both conditions hold, the total count equals the sum of the case counts. This is a preview of the Sum Rule, formalized in Chapter 2.
Example 1.8.2
Counting sequences with exactly one vowel — casework
- ProblemHow many three-letter sequences from {A, B, C, D, E} contain exactly one vowel? (Vowels: A, E. Consonants: B, C, D.)
- IdentifyThe single vowel must occupy position 1, 2, or 3. These cases are exhaustive and non-overlapping.
- Case 1Vowel in position 1: choose the vowel (2 ways) × consonant for position 2 (3 ways) × consonant for position 3 (3 ways) = 2 × 3 × 3 = 18.
- Case 2Vowel in position 2: consonant (3) × vowel (2) × consonant (3) = 18.
- Case 3Vowel in position 3: consonant (3) × consonant (3) × vowel (2) = 18.
- Total18 + 18 + 18 = 54.
- CheckCases are non-overlapping (a sequence has its vowel in exactly one position) and exhaustive. Addition is valid.
Answer: 54 three-letter sequences with exactly one vowel.
Section 1.9
Counting Without Counting One by One
A central theme of combinatorics is determining exact counts without examining each outcome individually. This is both possible and necessary. Consider again the password problem from this chapter's opening: 8 positions, each with 26 choices, gives 268 ≈ 208 billion passwords. Listing every one would take more than 6,000 years.
Combinatorics works because many large collections of outcomes have a structured, repeating pattern that can be captured algebraically. Each structure corresponds to a formula:
| Structure | Formula | Example |
|---|
| Product structure — independent positions, repeated choices | nk | 268 passwords from 26 letters, length 8 |
| Factorial structure — arranging n distinct objects in order | n! | 5! = 120 ways to arrange 5 books |
| Binomial structure — choosing k from n, order ignored | C(n,k) | C(20,3) = 1140 ways to choose 3 from 20 |
Each of these formulas will be derived from first principles in later chapters. The point here is that formula-based counting replaces list-based counting when lists become too large. The formula is valid only when its structural assumptions match the actual problem. Applying a product formula to a problem with restrictions — or applying a combination formula to a problem where order matters — produces an incorrect count.
Sections 1.10 – 1.14
Notation, Proof, Applications, and Preparation
Algebraic Notation · Why Proof Matters · Connections · Common Errors · Readiness
Section 1.10
Algebraic Notation in Counting
Combinatorics uses several important algebraic notations. This section introduces them informally. Full definitions and derivations will follow in Chapters 3, 4, and 5.
Notation
Meaning
Example
n!
Factorial of n — product of all positive integers from 1 to n
5! = 120
P(n,k)
Number of ordered arrangements of k objects from n distinct objects
P(5,2) = 20
C(n,k)
Number of unordered selections of k objects from n distinct objects
C(5,2) = 10
The Three Essential Formulas
n! = n × (n−1) × (n−2) × ⋯ × 2 × 1
P(n,k) = n! / (n−k)!
C(n,k) = n! / (k! × (n−k)!)
By convention, 0! = 1. This will be justified when factorial formulas are derived. Note: C(n,k) is also written as the binomial coefficient notation with n on top and k on the bottom in parentheses.
Notation Requires Care
C(10,3) answers a specific question: in how many ways can you choose 3 objects from 10, ignoring order? Using this expression for a problem where order matters produces the wrong answer. Throughout this book, notation will always be connected to meaning. The formula is a shortcut — but only when the formula matches the structure.
- Compute 4!
- Compute 6!
- Compute 0! and explain the convention.
- Compute 7!/5!
- Evaluate P(6,2)
- Evaluate P(5,5)
- Evaluate C(6,2)
- Evaluate C(8,3)
- Why does P(n,k) ≥ C(n,k) for all valid n and k?
- When does P(n,k) = C(n,k)? Explain.
Section 1.11
Why Proof Matters in Combinatorics
Combinatorics is not only a computational subject. It is also a proof-based subject. Many of its most important results take the form of theorems: statements that must be established by logical argument, not just observed from examples.
A proof is a logically complete argument that a mathematical statement is true. In combinatorics, proofs are used to establish that a counting formula gives the correct count in all applicable cases, to prove that two different counting methods produce the same result, and to demonstrate that a certain combinatorial structure must exist — even without constructing it.
| Proof Type | What It Does | Where Used in This Book |
|---|
| Algebraic proof | Simplify or rearrange symbolic expressions | Chapters 4, 5, 9 |
| Combinatorial proof | Show two expressions count the same set in two different ways | Chapter 9 |
| Double counting | Count a set two different ways; set the results equal | Chapter 9 |
| Bijective proof | Show two sets are the same size by pairing their elements | Chapter 9 |
| Pigeonhole principle | Prove some outcome must exist under certain conditions | Chapter 8 |
Example 1.11.1
Why 3! = 6 — a first proof
- ClaimThere are exactly 6 ways to arrange three distinct objects A, B, C in a row.
- ArgumentChoose the first position: 3 options. Choose the second: 2 options remaining (the first choice is taken). Choose the third: 1 option remaining. By the structure of sequential independent choices, the total is 3 × 2 × 1 = 6.
- VerifyList all arrangements:
ABC, ACB, BAC, BCA, CAB, CBA
That is exactly 6. The list confirms the formula for this small case.
- InterpretThe formula comes from understanding the structure. The list confirms the formula. For n = 100, listing is impossible — but the argument still gives the exact answer: 100!.
Answer: 3! = 6. Proven by sequential choice argument; confirmed by enumeration.
Section 1.12
Combinatorics in Computing, Probability, and Design
Combinatorics appears as a foundational tool across many disciplines. Here is an overview of connections that will be developed throughout this book.
| Field | How Combinatorics Applies | Example |
|---|
| Probability | Computing probabilities requires counting outcomes in an event and in the full sample space | P(specific person on committee) = C(19,4) / C(20,5) |
| Computer Science | Algorithm analysis; data structure design; decision trees; recursive problem structures | Number of binary trees on n nodes; searching a sorted array |
| Cryptography | Security depends on astronomically large key spaces that make brute-force search infeasible | AES-256 has 2256 possible keys |
| Networks | Counting routes, schedules, and assignments in graphs and networks | Number of spanning trees; number of valid schedules |
| Experimental Design | Latin squares, block designs, and balanced experiments guarantee fair data collection | A 4×4 Latin square for 4 treatments and 4 subjects |
| Games and Codes | Counting hands, configurations, and error-correcting code words | Number of 5-card poker hands; number of Hamming code words |
Section 1.13
Common Early Counting Misunderstandings
Combinatorics has predictable pitfalls. Naming them early lets students watch for them from the start.
Misunderstanding 1 — Treating all problems as arrangements
"The committee {Alice, Bob, Carol} and {Carol, Alice, Bob} are different because the order differs."
Committees are unordered selections. Using an arrangement formula produces an answer that is too large — by a factor of k!, where k is the committee size.
Misunderstanding 2 — Treating all problems as selections
"First, second, and third prize from 10 candidates: C(10,3) = 120."
Prize rankings are ordered. Alice winning first prize is different from Alice winning third. This is an arrangement problem: P(10,3) = 720.
Misunderstanding 3 — Missing cases in casework
"To count sequences with at least one A, I counted only sequences with exactly one A."
Casework requires exhaustive cases. "At least one A" includes exactly 1, exactly 2, exactly 3, ... as many as the length allows. Check that all cases together cover every possible outcome.
Misunderstanding 4 — Counting the same outcome twice
"Case 1: sequences beginning with A. Case 2: sequences containing at least one A. I added both counts."
These cases overlap: every sequence beginning with A also contains at least one A. Overlapping cases cause double-counting. Cases must be non-overlapping for the Sum Rule to apply.
Misunderstanding 5 — Ignoring restrictions
"5 people, 5 chairs: 5! = 120 arrangements." (But the problem says two specific people cannot be adjacent.)
Restrictions change the structure of the problem and must be addressed before computing the count, not after. The restriction "X and Y not adjacent" requires a subtraction or complement approach.
Misunderstanding 6 — Confusing the count with the event
"There are 120 arrangements of 5 books, so each arrangement is equally likely to appear on the shelf."
Combinatorics gives the size of a set of possibilities. It does not by itself determine which possibility occurs or with what probability. Probability requires additional information about the process generating outcomes.
Misunderstanding 7 — Solving a simpler problem than the one given
"It says without repetition, so I used P(n,k). But the problem also requires one specific person to be included — I forgot that restriction."
Read the problem completely. Identify every constraint. Check that your method addresses the exact conditions given, not just the most obvious feature of the problem.
Section 1.14
Preparing for Basic Counting Principles
Chapter 1 has introduced the language, concepts, and habits of mind needed to begin combinatorics. Chapter 2 introduces the first formal tools: the Sum Rule and the Product Rule.
These two rules formalize what has already been observed informally in this chapter. When outcomes fall into non-overlapping cases, the total count is the sum of the case counts — this is the Sum Rule. When choices are made in sequence and each choice is independent, the total count is the product of the individual counts — this is the Product Rule.
Together with complement counting, casework, and the inclusion-exclusion principle, these two rules form the foundation of all later counting techniques. Everything in Chapters 3 through 14 rests on the reasoning introduced in Chapters 1 and 2.
Readiness Checklist for Chapter 2
□ I can describe what combinatorics studies and what tools it uses.
□ I can distinguish arrangements (order matters) from selections (order does not matter).
□ I can list outcomes systematically for small problems.
□ I can build and read a tree diagram for a two-step or three-step choice.
□ I can organize a counting problem into exhaustive, non-overlapping cases.
□ I know the notation n!, P(n,k), and C(n,k) at an introductory level.
□ I can name at least three common early counting errors and explain how to detect them.
- A coin is flipped and then a card is drawn from {1, 2, 3}. List all outcomes systematically. How many are there?
- A student chooses a first course from {Math, English} and a second course from {Science, History, Art}. Draw a tree diagram and count the outcomes. Does order matter within a single student's schedule?
- From five runners — Alex, Bea, Carl, Dana, Elena — list all possible gold-silver medal outcomes. Explain why this is an arrangement problem.
- A class is choosing a 2-person study team from Alex, Bea, Carl, Dana. List all possible teams. Explain why this is a selection problem.
- Compare your two lists from problems 3 and 4. Why does problem 3 have more outcomes than problem 4?
Chapter 1 — Back Matter
Chapter Summary
- Sec 1.1Combinatorics is the branch of mathematics that studies counting, arranging, selecting, and proving facts about finite or discrete structures. It is not calculus-based. Its tools are algebraic notation, set language, counting rules, casework, proof, and recursion.
- Sec 1.2The core process is: Identify → Represent → Count → Justify → Check → Explain. Every problem begins by identifying what is being counted and what makes two outcomes the same or different.
- Sec 1.3An arrangement is an ordered sequence; two arrangements are different if the same objects appear in different order. A selection is an unordered collection; two selections are the same if they consist of the same objects. The question "Does order matter?" is the first question to ask in any counting problem.
- Sec 1.4A set is a well-defined collection of distinct objects. Its cardinality |S| is the number of elements. Combinatorics works with finite sets and discrete structures. No calculus is required.
- Sec 1.5An outcome is a single result of a choice process. The sample space S is the complete set of all outcomes. Combinatorics computes |S| and sizes of subsets of S without listing every element.
- Sec 1.6Systematic listing uses the fix-and-vary method to produce complete, non-repetitive enumerations. For small cases, listing reveals structure. For large cases, formulas replace listing.
- Sec 1.7A tree diagram uses branches to organize multi-step choices. Each leaf is one complete outcome. The number of leaves counts the total outcomes. Branching reflects independence or dependence between steps.
- Sec 1.8Tables organize outcomes when two independent choices are made. Casework divides a problem into exhaustive, non-overlapping cases. If both conditions hold, the total count is the sum of the case counts.
- Sec 1.9Large sample spaces have product, factorial, or binomial structure that allows exact counting without enumeration. The formula is valid only when its structural assumptions match the actual problem.
- Sec 1.10Key notation: n! = n × (n−1) × ⋯ × 1. P(n,k) = n!/(n−k)!. C(n,k) = n!/(k!(n−k)!). Each notation encodes a specific counting question. Using the wrong notation gives a wrong count.
- Sec 1.11A proof is a logically complete argument. Combinatorial proofs include algebraic proofs, combinatorial proofs, double counting, bijective proofs, and the pigeonhole principle. Formulas must be proved, not just observed from examples.
- Sec 1.12Combinatorics connects to probability, computer science, cryptography, networks, scheduling, experimental design, and games. It is a foundational tool across quantitative fields.
- Sec 1.13Seven common early errors: treating all problems as arrangements; treating all as selections; missing cases; double-counting overlapping cases; ignoring restrictions; confusing count with probability; solving a simpler problem than given.
- Sec 1.14Chapter 2 formalizes the Sum Rule and Product Rule. All skills from Chapter 1 — systematic listing, casework, distinguishing arrangements from selections — carry forward directly.
Key Terms Review
combinatorics
The branch of mathematics that studies counting, arranging, selecting, and proving facts about finite or discrete structures.
arrangement
An ordered sequence of objects. Two arrangements are different if the same objects appear in a different order. Studied formally as permutations in Chapter 3.
selection
An unordered collection of objects. Two selections are the same if they consist of the same objects. Studied formally as combinations in Chapter 4.
set
A well-defined collection of distinct objects enclosed in braces. Sets have no inherent order and no repeated elements.
element
A single object belonging to a set. Written x ∈ S to indicate that x is an element of set S.
cardinality
The number of elements in a set. Written |S|. Combinatorics often asks for the cardinality of a sample space or subset.
finite set
A set with a specific, countable number of elements. Combinatorics works almost exclusively with finite sets.
discrete structure
A mathematical object whose elements are individually distinguishable and separate. Examples: sets, sequences, graphs, codes.
outcome
A single result of a choice process or experiment. Must be defined precisely before counting begins.
sample space
The complete set of all possible outcomes of an experiment, written S. Combinatorics computes |S|.
tree diagram
A branching diagram used to list and count outcomes of multi-step choice processes. Each leaf is one complete outcome.
casework
The strategy of dividing a counting problem into exhaustive, non-overlapping cases and summing the counts. Preview of the Sum Rule.
factorial (n!)
The product n × (n−1) × ⋯ × 2 × 1. Counts the arrangements of n distinct objects in order. By convention, 0! = 1.
P(n,k)
The number of ordered arrangements of k objects chosen from n distinct objects. Formally: n!/(n−k)!. Developed in Chapter 3.
C(n,k)
The number of unordered selections of k objects from n distinct objects. Formally: n!/(k!(n−k)!). Developed in Chapters 4–5.
proof
A logically complete argument establishing that a mathematical statement is true. Not the same as checking examples.
Concept Review Questions
- In your own words, what does combinatorics study? How does it differ from calculus?
- Explain the difference between an arrangement and a selection. Give one example of each.
- What is a sample space? How is computing |S| related to the general goal of combinatorics?
- What does it mean to list outcomes systematically? Why is a systematic list better than a random list?
- What is the purpose of a tree diagram? When does a table serve the same purpose more efficiently?
- State the two conditions that a set of cases must satisfy for casework-based counting to be valid.
- Why is it important to distinguish "with repetition" from "without repetition" when counting sequences?
- Give an example where order matters in a counting problem and one where it does not. Explain how you decide.
- What is a proof, and why does it matter in combinatorics rather than just checking formulas on examples?
- Name three common early counting errors. For each, give a brief example and explain how to detect it.
- List all two-letter sequences from {P, Q, R} with repetition allowed. How many are there?
- List all two-letter sequences from {P, Q, R} without repetition. How many are there?
- List all three-element subsets of {1, 2, 3, 4}. How many are there?
- List all ways to arrange the letters in the word DOG. How many arrangements are there?
- List all ways to choose a first-place and second-place finisher from three runners: Priya, Quinn, Rosa.
- List all outcomes when a coin is flipped three times in a row. How many are there?
- List all two-digit numbers that can be formed using {1, 2, 3} with repetition allowed. How many are there?
- List all two-person teams from {Amir, Brianna, Carlos, Diana}. How many are there?
Answers may be placed in the answer key.
- Draw a tree diagram showing all outcomes when a coin is flipped and then a die with faces {1, 2, 3} is rolled. How many outcomes are there?
- A sandwich shop offers 2 breads (white, wheat), 3 fillings (turkey, tuna, veggie), and 2 condiments (mustard, mayo). Draw a tree and count all possible sandwiches.
- A student can travel from A to B by car, bus, or train. From B to C by bus or train. Draw a tree showing all routes from A to C.
- A lock has a three-digit code. Each digit is from {0, 1, 2}. Draw a tree diagram. How many codes are there?
- A player rolls a three-face die {1, 2, 3} and then draws a card {Red, Blue}. Draw a tree and count all outcomes.
Answers may be placed in the answer key.
- Three-letter sequences from {A, B, C, D, E} (A and E are vowels, B, C, D are consonants). Count sequences with exactly two vowels using casework on the vowel positions.
- A four-character password uses only {1, 2, 3}. Count passwords containing at least one 3 by using the complement approach.
- From five friends Aisha, Ben, Carmen, David, Elena, list all two-person teams that include either Aisha or Ben or both. How many such teams are there?
- How many integers from 1 to 100 are divisible by 2 or by 5? Use casework and handle the overlap carefully.
- A committee of 3 is chosen from 4 men and 3 women. Using casework on the number of women, count the total possible committees. You may use C(n,k) notation.
Answers may be placed in the answer key.
For each problem: identify what is being counted, state whether order matters, state whether repetition is allowed, then compute the count.
- Passwords: A 4-digit PIN uses digits 0–9, repetition allowed. How many PINs are possible? Explain your reasoning without simply stating a formula.
- Menu Planning: A restaurant has 4 appetizers, 6 main courses, and 3 desserts. A complete dinner = one from each category. How many complete dinners are possible? Draw a partial tree for the first two categories.
- Color Coding: A label uses three color bands, each chosen from {red, blue, green, yellow}. Repetition allowed: how many labels? No repeated colors: how many?
- Scheduling: 4 class periods, 3 subjects (Math, Science, English), one subject per period, each subject used once. How many schedules are possible? Does order matter?
- Team Selection: 2 people chosen from 8 volunteers. Does order matter? How many teams are possible?
- Seating: 5 people sit in a row of 5 chairs. How many arrangements are possible? Why does order matter in this context?
Answers may be placed in the answer key.
Error Analysis
Each problem shows a counting error. Identify the error and explain how to correct it.
Problem 1
"How many ways can 3 books be chosen from 7 for a reading list if order matters? Answer: C(7,3) = 35."
Identify the error. What type of counting object is being counted here? What should the correct approach be?
Problem 2
"Three-digit numbers from {1,2,3,4,5}: there are 5³ = 125 total, and 4³ = 64 contain no 3, so the answer is 61."
Check whether this complement reasoning is valid. Is there any logical error?
Problem 3
"Alice and Bob are on the team. Choose 2 more from Carmen, David, Elena, Farouk: I list 6 teams, then double to 12 because listing Bob first is different from listing Alice first."
Identify the conceptual error. What type of object is a team? How should the count be performed?
Problem 4
"A committee of 3 from 5 Group A + 5 Group B, exactly 1 from A and 2 from B: answer = 5 + C(5,2) = 5 + 10 = 15."
Identify the error. What operation should be used between the Group A count and the Group B count?
Chapter 1 Checkpoint
Chapter 1 Checkpoint
Complete without assistance — assesses all key concepts and skills from Chapter 1
Part A — Vocabulary
- Define arrangement and selection in your own words. Give one real-world example of each.
- What is the difference between an outcome and a sample space? Give an example of each.
- What does systematic listing mean, and why is it preferable to an unsystematic list?
Part B — Listing and Diagrams
- List all possible outcomes when a fair coin is flipped twice. Represent your list as a set.
- A student chooses a main color (Red, Blue, Green) and an accent color (Yellow, White), with no color repeated. Draw a tree diagram and list all outcomes.
- From {A, B, C, D}, list all selections of exactly 2 elements, then all arrangements of exactly 2 elements. How many of each?
Part C — Casework
- How many integers from 1 to 50 are divisible by 3 or by 7? Use casework and handle the overlap.
- A three-character code is formed from {X, Y, Z}. Count codes containing the letter Z at least once, using casework.
Part D — Reasoning and Explanation
- A student claims: "Since the committee {Alice, Bob, Carol} and {Carol, Alice, Bob} are different orderings, I should count them separately." Do you agree? Explain your reasoning by defining what type of object a committee is.
- Describe in words how you would approach this problem before computing anything: "A café has 5 sandwich types, 4 drink types, and 3 desserts. A customer chooses one of each. How many different complete orders are possible?" Identify what is being counted, whether order matters, and what structure the problem has.
Part E — Notation
- Compute 5!, 3!, and 0!.
- Evaluate P(5,3) and C(5,3). Explain why P(5,3) > C(5,3).
- Write in words what C(10,4) counts. Give a real-world context that matches this count.
Part F — Reflection
- What is the most important idea you learned in Chapter 1? Write 2–4 sentences explaining why it matters.
- Name one question Chapter 1 raised that you expect later chapters to answer.
Looking Ahead
Chapter 2: Basic Counting Principles
Chapter 1 introduced the vocabulary and reasoning habits of combinatorics. Chapter 2 formalizes the first rules: the Sum Rule, the Product Rule, complement counting, casework with multiple subcases, and inclusion-exclusion for two and three overlapping sets. These principles are the operational backbone of the entire subject. As you move forward, continue to ask: What am I counting? Does order matter? Is repetition allowed? Are my cases complete and non-overlapping? These questions — and the habits of precision and justification they require — are what distinguish rigorous combinatorial reasoning from lucky guessing.
MGU Library Connection
- Discrete Mathematics: Sets and Set Operations — foundational set language used throughout this textbook
- Discrete Mathematics: Logic and Proof — formal proof techniques previewed in Section 1.11
- Probability and Statistics: Sample Spaces and Events — the vocabulary of outcomes and sample spaces connects directly
- Computer Science: Decision Trees and Recursive Structures — tree diagrams and casework reappear in algorithmic contexts
- Cryptography: Key Space Analysis — counting arguments underpin the security of modern cryptographic systems
- MGU Dictionary entries: arrangement, selection, sample space, tree diagram, casework, factorial, permutation, combination