MGU Mathematics Series — Combinatorics

Part V: Graphs, Designs, and Capstone Applications

Synthesis · Modeling · Strategy · Proof · Application

Chapter 14 of 14

MGU Mathematics Series · Combinatorics · Library Textbook Edition

Chapter 14:
Combinatorics Capstone
and Applications

Bringing together every major method — modeling, ordering, selecting, distributing, overlap, existence, recurrence, generating functions, and graph structures — into a unified framework for combinatorial reasoning

■ Math Level: Combinatorics ■

■ 15 Sections • Part V of 5 ■

Closing Chapter · Synthesizes Chapters 1–13 · Prepares students for Probability, Algorithms, Cryptography, and Graph Theory

Chapter 14 — Front Matter

Purpose and Overview

This chapter is the closing chapter of the textbook. Its purpose is not to introduce new counting formulas, but to bring together every major idea from the preceding thirteen chapters and show how they work together as a unified toolkit for combinatorial reasoning.

Throughout this book, you have studied the sum rule and the product rule, permutations and combinations, binomial coefficients and Pascal's Triangle, stars and bars, inclusion-exclusion, the pigeonhole principle, combinatorial identities and proof, recurrence relations, generating functions, graph counting, Latin squares, block designs, and symmetry arguments. Each of those chapters asked you to master one set of ideas thoroughly before moving forward.

This chapter asks a different question: given a problem you have never seen before, how do you decide what to do? That question is harder than it sounds. Real combinatorial problems do not announce their type. They do not come labeled "use inclusion-exclusion here" or "this is a recurrence relation problem." You have to read the situation, identify the structure, choose a model, justify the approach, carry out the count, and explain the result. This chapter is designed to teach exactly that process.

By the end of this chapter, you should be able to approach a combinatorial problem from any direction, recognize which tools apply, combine methods when necessary, and communicate your reasoning clearly and completely. Combinatorics is not a bag of tricks. It is a way of thinking.

Opening Question

A small software company needs to assign project roles for a new development cycle. They have 12 engineers. Three will be assigned to security, four to user interface, and five to back-end infrastructure. No engineer can be assigned to more than one team. The security team needs a lead, and the infrastructure team needs both a lead and a deputy lead. In how many ways can these assignments be made?

Before you read further, think about this problem. What is being counted? Does order matter in some parts and not others? Are there stages to the assignment? Are there restrictions? Could you solve this problem with just one method, or would you need to combine several? You will return to it in Section 14.13.

15Sections

8Objectives

9Worked Examples

4Capstone Problems

Learning Objectives

1Apply the combinatorial modeling process to unfamiliar problems using the Identify → Represent → Count → Justify → Check → Explain framework.
2Identify the objects being counted and the structure of any counting situation.
3Recognize when a problem requires an ordering model, selection model, distribution model, overlap correction, existence argument, recurrence, generating function, or graph structure.
4Combine multiple counting methods within a single problem.
5Check counts for overcounting and undercounting.
6Construct and communicate complete combinatorial arguments.
7Recognize and correct common combinatorial modeling errors.
8Identify how combinatorial reasoning appears in probability, algorithms, cryptography, and data science.

Chapter 14 — Contents

Sections at a Glance

14.1The Combinatorial Modeling ProcessSix stages: Identify, Represent, Count, Justify, Check, Explain; what makes a good model; order, repetition, restrictions, overlap, existence, recursion
14.2Identifying the Objects Being CountedThree problems about choosing three people; taxonomy of combinatorial objects; sequences, subsets, multisets, distributions, graphs, symmetry classes
14.3Choosing an Ordering ModelWhen order matters; permutation methods; restrictions, gap method, block method; Example 14.1
14.4Choosing a Selection ModelWhen order does not matter; combination methods; fixing required elements, complement, casework; Example 14.2
14.5Handling Repetition and RestrictionsFour-cell table of repetition vs. no repetition; common restriction types; most-constrained-first strategy; Example 14.3
14.6Handling OverlapInclusion-exclusion for two and three sets; when casework beats inclusion-exclusion; Example 14.4
14.7Using Existence ArgumentsPigeonhole principle; generalized form; four-step application; beyond simple pigeonhole; Example 14.5
14.8Using RecurrencesRecursive structure; first-order, second-order, Fibonacci-type; recognizing recursive patterns; Example 14.6
14.9Using Generating FunctionsFormal power series review; factors for restrictions; multiplying and extracting coefficients; Example 14.7
14.10Using Graph StructuresHandshaking lemma; complete and bipartite graphs; trees; Cayley's formula preview; Example 14.8
14.11Comparing Counting StrategiesWhen to use each method: direct, complement, casework, inclusion-exclusion, stars and bars, recurrence, generating functions, pigeonhole, combinatorial proof
14.12Communicating Combinatorial ReasoningWhat a complete explanation looks like; incomplete vs. complete examples; writing a combinatorial proof; Example 14.9
14.13Capstone Counting ProjectsFour extended problems: engineering teams, integer divisibility, tiling recurrence, pigeonhole bound
14.14Common Combinatorial Modeling MistakesTen conceptual errors; wrong order model, repetition confusion, missing restrictions, double-counting, incomplete existence arguments, treating generating functions analytically
14.15Readiness for Advanced StudyWhat you now know; probability, algorithms, cryptography, graph theory, coding theory, operations research, and advanced combinatorics

Section 14.1

The Combinatorial Modeling Process

Every counting problem begins with a situation described in words. Before any formula is applied, that situation must be translated into a mathematical structure. This translation is called the combinatorial modeling process. The process has six stages, which this book has used since Chapter 1.

The Six Stages

Identify. What objects are being counted? Arrangements, selections, sequences, distributions, graphs, paths, designs? Name the objects before anything else.
Represent. How can the situation be described precisely? Use sets, ordered lists, trees, tables, equations, diagrams, recurrences, or graphs as appropriate.
Count. Apply the appropriate method or combination of methods. Show the computation step by step.
Justify. Explain why the method is correct. Why does it count exactly the right objects? Why does it avoid counting the same object twice?
Check. Verify by testing small cases, using complementary arguments, or comparing to a known result. Confirm the number is plausible in context.
Explain. Interpret the answer in the language of the original problem. A count is not complete until it is connected back to the situation it describes.

What Makes a Good Combinatorial Model?

A combinatorial model is correct when it captures exactly the structure of the situation being counted. This requires precision across several dimensions that must each be addressed before a formula is chosen.

Dimension	Key Question	Impact on the Count
Order	Does swapping two elements produce a different outcome?	Yes → permutation model. No → combination model.
Repetition	Can the same object appear more than once?	Changes formulas for both sequences and selections.
Restrictions	Are any outcomes forbidden or required?	Must be represented before the formula is chosen.
Overlap	Can the same outcome belong to two different cases?	Requires inclusion-exclusion or careful casework.
Existence vs. Exact Count	Does the problem ask how many, or whether something must exist?	Existence → pigeonhole or extremal argument.
Recursion vs. Closed Form	Is the count most naturally defined in terms of smaller cases?	Yes → recurrence relation or generating function.

Section 14.2

Identifying the Objects Being Counted

The most important question in any combinatorial problem is: what exactly is being counted? This question is harder than it appears because the same words can describe different objects depending on how the situation is read. Consider three different problems about choosing three people from a group of eight.

In the first problem, three people are chosen to receive the same prize. The objects being counted are three-element subsets of an eight-element set. Order does not matter. The count is C(8,3) = 56.

In the second problem, three people are chosen for three different roles: president, secretary, and treasurer. The objects are ordered triples drawn without repetition. Order matters. The count is P(8,3) = 8 · 7 · 6 = 336.

In the third problem, three identical items are distributed among eight people, where each person may receive any number. This is a stars-and-bars problem. The count is C(8+3−1, 3) = C(10,3) = 120.

Three problems. Three completely different counts. The only difference is what is being counted. Getting that right is the whole game.

A Taxonomy of Common Combinatorial Objects

Object Type	Conditions	Formula
Sequences, no repetition	Ordered, distinct objects	P(n,k) = n! / (n−k)!
Sequences with repetition	Ordered, any element reusable	n^k
Sequences with repeated symbols	Arrange a fixed multiset	n! / (n₁! · n₂! · … · nᵣ!)
Subsets, no repetition	Unordered, each element used at most once	C(n,k) = n! / (k!(n−k)!)
Multisets with repetition	Unordered, repetition allowed	C(n+k−1, k)
Circular arrangements	Rotations are equivalent	(n−1)!
Distributions, identical objects	n identical into k distinct bins	C(n+k−1, k)
Distributions, distinct objects	Each of n objects chooses a bin	kⁿ
Overlapping categories	Union of sets with intersections	Inclusion-exclusion
Existence under constraints	Must something exist?	Pigeonhole principle
Counts built from smaller cases	Recursive structure	Recurrence relations
Arrangements under symmetry	Rotations or reflections equivalent	Burnside's Lemma (preview)

Section 14.3

Choosing an Ordering Model

Order matters when position, sequence, rank, role, or label is part of what distinguishes one outcome from another. The first digit of a PIN is not the same as the second. The president of a committee is not the same as the treasurer.

Order does not matter when two outcomes are considered the same as long as they contain the same elements. A committee of three named Alice, Ben, and Carla is the same committee regardless of the order they are listed.

The test is simple: swap two elements in an outcome. If the result is a different outcome, order matters. If the result is the same outcome, order does not matter.

Restriction Strategy

Handle the most constrained part of the problem first. Fix required elements. Remove forbidden elements. Establish togetherness using the block method (treat required-together objects as one unit). Establish separation using the gap method (arrange unrestricted objects, then count valid positions for separated objects). Only after representing all restrictions should you apply the permutation formula.

Example 14.1

Choosing an ordering model — prize rankings

ProblemA professor has 10 students and wants to rank the top 4 for a prize competition. How many different rankings are possible?
IdentifyA ranking assigns positions 1st, 2nd, 3rd, and 4th to four different students. These positions are distinct. Swapping two students produces a different ranking. Order matters.
RepresentCount ordered arrangements of 4 students chosen from 10, without repetition.
Count P(10,4) = 10! / (10−4)! = 10 · 9 · 8 · 7 = 5,040
CheckThe first position has 10 choices, the second has 9, the third has 8, the fourth has 7. The product 10 · 9 · 8 · 7 = 5,040 matches. ✓
InterpretThere are 5,040 possible rankings of the top 4 students.

Answer: P(10,4) = 5,040 rankings

Section 14.4

Choosing a Selection Model

When order does not matter, the count must eliminate repeated arrangements of the same group. This is done by dividing by the number of ways the selected group could be arranged among itself. The result is the combination formula:

Combination Formula

C(n,k) = n! / (k!(n−k)!)

This counts the number of ways to choose k objects from n distinct objects when order does not matter. Every combination of k objects corresponds to exactly k! different permutations of the same objects; dividing by k! corrects the overcounting.

Example 14.2

Choosing a selection model — committee with a required member

ProblemA research lab has 15 scientists. A steering committee of 5 must be chosen. Dr. Vásquez must be on the committee. How many possible committees are there?
IdentifyA committee is a group; order does not matter. Dr. Vásquez is a required element.
RepresentFix Dr. Vásquez in place. Choose 4 more from the remaining 14 scientists.
Count C(14,4) = 14! / (4! · 10!) = (14 · 13 · 12 · 11) / (4 · 3 · 2 · 1) = 24,024 / 24 = 1,001
CheckWithout the restriction, C(15,5) = 3,003 total committees. The fraction including Dr. Vásquez is 5/15 = 1/3 of the total: 3,003 · (1/3) = 1,001. ✓
InterpretThere are 1,001 possible committees that include Dr. Vásquez.

Answer: C(14,4) = 1,001 committees

Section 14.5

Handling Repetition and Restrictions

Situation	Repetition Allowed	No Repetition
Ordered sequences of length k from n objects	`n^k`	`P(n,k) = n! / (n−k)!`
Unordered selections of size k from n objects	`C(n+k−1, k)`	`C(n,k) = n! / (k!(n−k)!)`

Most Common Error

Choosing the wrong column in the table above is the single most frequent mistake in combinatorics. Before applying any formula, ask: is the same object allowed to appear more than once? If yes, use the repetition column. If no, use the no-repetition column.

Example 14.3

Repetition and restriction combined — passwords with at least one digit

ProblemA 6-character password uses lowercase letters (26) and digits (10), for an alphabet of 36 characters. Repetition is allowed. How many passwords contain at least one digit?
ThinkCounting passwords with at least one digit directly involves many cases. Use complement counting: subtract those with no digits from the total.
Count Total (any character): 36⁶ = 2,176,782,336 No digits (letters only): 26⁶ = 308,915,776 At least one digit: 36⁶ − 26⁶ = 1,867,866,560
CheckThe complement (all-letter passwords) is about 14% of the total. About 86% contain at least one digit — plausible for a 6-character password with 10 of 36 characters being digits. ✓
InterpretThere are 1,867,866,560 valid passwords containing at least one digit.

Answer: 36⁶ − 26⁶ = 1,867,866,560 passwords

Section 14.6

Handling Overlap

When a counting problem involves categories that overlap — when some outcomes belong to more than one category — adding the category sizes will overcount the outcomes in the intersection. Inclusion-exclusion corrects this by alternately adding and subtracting intersection sizes.

Inclusion-Exclusion

For two overlapping sets A and B:

|A ∪ B| = |A| + |B| − |A ∩ B|

For three overlapping sets A, B, and C:

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

The pattern alternates: add individual sets, subtract pairwise intersections, add triple intersections, and so on.

Example 14.4

Inclusion-exclusion with overlapping survey categories

ProblemA class of 40 students is surveyed. 22 play chess, 18 play Go, and 7 play both. How many students play at least one of these games?
IdentifyThe two groups overlap. Adding 22 and 18 counts the 7 students in both groups twice.
Count |C ∪ G| = 22 + 18 − 7 = 33
Check33 play at least one game. The remaining 40 − 33 = 7 students play neither. Consistent and plausible. ✓
Interpret33 students play at least one of chess or Go.

Answer: 33 students

Casework vs. Inclusion-Exclusion

Use inclusion-exclusion when overlapping categories are defined by independent conditions and intersections can be computed efficiently. Use casework when the number of cases is small, the cases are naturally disjoint, and restrictions make certain cases very easy to count. Casework requires that all cases together cover every valid outcome exactly once.

Section 14.7

Using Existence Arguments

Some combinatorial problems do not ask for an exact count. They ask whether a particular outcome must exist under given conditions. The central tool is the pigeonhole principle: if more than n objects are distributed among n containers, then at least one container must hold more than one object. The generalized form: if more than n · k objects are distributed among n containers, then at least one container must hold more than k objects.

Applying the Pigeonhole Principle

Identify the pigeons (the objects being distributed).
Identify the boxes (the categories or containers).
Determine the threshold: how many pigeons per box guarantee the conclusion?
State the conclusion precisely. The conclusion holds regardless of how the distribution is made.

Example 14.5

Pigeonhole — guaranteed matching pair

ProblemA drawer contains socks in four colors: red, blue, green, and black. What is the minimum number of socks you must draw (without looking) to guarantee a matching pair?
IdentifyPigeons: socks drawn. Boxes: four colors. With 4 boxes, drawing 5 socks guarantees at least 2 socks in one box.
Count Minimum socks needed = 4 + 1 = 5
CheckWith 4 socks, you could have exactly one of each color — no guarantee. With 5 socks, the pigeonhole principle guarantees at least one color has 2 or more socks. ✓
InterpretYou must draw at least 5 socks to guarantee a matching pair.

Answer: 5 socks

Section 14.8

Using Recurrences

Some combinatorial quantities are most naturally defined in terms of smaller versions of themselves. When the count of an n-element structure can be expressed in terms of counts for smaller structures, a recurrence relation describes the count precisely. A recurrence requires initial conditions to determine the sequence uniquely.

Look for recursive structure when: a choice at position n depends on choices at earlier positions; a structure of size n can be built by extending a structure of size n−1; or removing one element leaves a smaller problem of the same type.

Example 14.6

Recognizing recursive structure — staircase climbing

ProblemA staircase has n steps. You can climb 1 or 2 steps at a time. Let aₙ be the number of ways to climb an n-step staircase. Find a recurrence for aₙ and compute a₅.
ThinkConsider the last move. Either you arrived by taking 1 step from step n−1 (giving aₙ₋₁ ways to get there) or by taking 2 steps from step n−2 (giving aₙ₋₂ ways to get there).
Represent aₙ = aₙ₋₁ + aₙ₋₂ Initial conditions: a₁ = 1 (one way: one step) a₂ = 2 (two ways: 1+1 or 2)
Count a₃ = 2 + 1 = 3 a₄ = 3 + 2 = 5 a₅ = 5 + 3 = 8
CheckFor n = 3 the ways are: 1+1+1, 1+2, 2+1. That is 3 ways. ✓
InterpretThere are 8 ways to climb a 5-step staircase using 1- or 2-step moves. This follows the Fibonacci sequence.

Answer: a₅ = 8

Section 14.9

Using Generating Functions

A generating function encodes a sequence as the coefficients of a formal power series: G(x) = a₀ + a₁x + a₂x² + a₃x³ + ⋯ = Σ aₙxⁿ. In this book, x is a formal placeholder — not a real number with a value. We do not ask whether the series converges. We extract coefficients algebraically.

Each object type in the count contributes a factor. If an object can be chosen 0, 1, 2, … times without restriction, its factor is 1 + x + x² + ⋯. If it can be chosen exactly 0 or 1 times, its factor is 1 + x. If it must be chosen at least once, its factor starts at x. The coefficient of xⁿ in the product of all factors counts the ways to make selections totaling n.

Example 14.7

Generating functions for a restricted selection count

ProblemHow many ways can you choose 6 items from three types if you must choose at least 1 of type A, at most 2 of type B, and any number of type C?
Represent Type A (at least 1): x + x² + x³ + ⋯ Type B (at most 2): 1 + x + x² Type C (any amount): 1 + x + x² + x³ + ⋯ G(x) = (x + x² + ⋯)(1 + x + x²)(1 + x + x² + ⋯)
CountFactor x from the type-A series. We need [x⁶] in G(x), which equals [x⁵] in (1 + x + x² + ⋯)²(1 + x + x²). The product of the two infinite factors has [xᵏ] = k+1. So we need [x⁵] in Σ(k+1)xᵏ · (1 + x + x²): [x⁵] = (5+1)·1 + (4+1)·1 + (3+1)·1 = 6 + 5 + 4 = 15
CheckAlternative: substitute a′ = a−1, giving a′+b+c = 5 with a′ ≥ 0, 0 ≤ b ≤ 2, c ≥ 0. Unconstrained count C(7,2) = 21; subtract cases b ≥ 3 (substitute b′ = b−3, a′+b′+c = 2: C(4,2) = 6 cases). Answer = 21 − 6 = 15. ✓
InterpretThere are 15 ways to select 6 items from the three types under the given restrictions.

Answer: 15 ways

Section 14.10

Using Graph Structures

Some combinatorial problems involve relationships between objects, not just the objects themselves. A graph G consists of a set of vertices V and a set of edges E. Graph counting problems ask how many vertices, edges, paths, cycles, trees, colorings, or matchings exist in a graph or satisfy some condition.

Key Graph Counting Formulas

Handshaking Lemma: The sum of all vertex degrees equals twice the number of edges: Σ deg(v) = 2|E|.

Complete graph K_n: Has C(n,2) = n(n−1)/2 edges.

Complete bipartite graph K_m,n: Has mn edges.

Trees: A tree on n vertices has exactly n−1 edges. Cayley's formula states the number of labeled trees on n vertices is nⁿ⁻².

Example 14.8

Graph counting — collaboration network

ProblemA university department has 9 faculty members. A collaboration graph connects pairs who have coauthored a paper. Every faculty member has exactly 4 collaborators. How many collaboration pairs are there?
RepresentThe graph has 9 vertices, each with degree 4. Apply the Handshaking Lemma.
Count Σ deg(v) = 9 · 4 = 36 = 2|E| |E| = 36 / 2 = 18
CheckThe maximum for 9 vertices is C(9,2) = 36 edges. Having 18 means exactly half of all possible collaborations exist. Plausible. ✓
InterpretThere are 18 collaboration pairs among the 9 faculty members.

Answer: 18 collaboration pairs

Section 14.11

Comparing Counting Strategies

One of the most important skills in combinatorics is recognizing when multiple methods could solve the same problem and choosing the most efficient one. The following reference compares the major approaches and their appropriate conditions.

Direct Counting Structure is clear, cases are few, no overlap. Apply the appropriate formula directly. Watch for missing restrictions and wrong repetition assumptions.
Complement Counting Counting desired outcomes directly is harder than subtracting undesired from the total. Total − undesired = desired. Ensure total and undesired use the same rules for order and repetition.
Casework Problem naturally splits into a small number of disjoint cases covering all possibilities. Count each case, verify cases are disjoint and exhaustive, add. Watch for missing or overlapping cases.
Inclusion-Exclusion Categories overlap in a structured way and overlaps can be computed. Add sizes, subtract pairwise overlaps, add triple overlaps, and so on. Watch for missing intersection terms.
Stars and Bars Distributing identical objects into distinct bins, or counting nonneg. integer solutions to x₁ + x₂ + ⋯ + xₖ = n. Formula: C(n+k−1, k−1). Only for identical objects.
Recurrence Relations Count at step n depends on earlier counts and the recursive structure is clear. Write recurrence, establish initial conditions, compute forward or solve for closed form.
Generating Functions Multiple interacting restrictions make direct counting complicated. Assign factors per object type, multiply, extract coefficients algebraically. Do not treat x as a real number.
Pigeonhole / Existence The problem asks whether something must exist, not how many exist. Name pigeons, boxes, and threshold. State the guaranteed conclusion precisely.
Combinatorial Proof Two expressions appear equal; prove it by describing a finite set and counting it two ways. Each side of the identity counts the same set from a different perspective.

Section 14.12

Communicating Combinatorial Reasoning

A count is only as good as its explanation. In mathematics, a number without justification is not a complete answer. Good combinatorial communication follows a consistent pattern: name the objects, state the model, show the computation, justify the method, and interpret the result.

Incomplete Example

"There are C(10,3) = 120 ways."

This is incomplete. It does not explain why C(10,3) is correct. Are the objects distinct? Does order matter? Are there restrictions? Why is division by 3! appropriate?

Complete Example

A committee of 3 is an unordered selection of 3 distinct people from 10. Since the committee has no assigned roles and the same 3 people form one committee regardless of listing order, combinations apply. The count is C(10,3) = 10! / (3! · 7!) = 120.

Example 14.9

A combinatorial proof — symmetry of binomial coefficients

ProblemProve that C(n,k) = C(n, n−k).
State the setLet S be the collection of all k-element subsets of an n-element set.
Left sideC(n,k) counts the number of k-element subsets of S directly.
Right sideFor every k-element subset A, there is a corresponding (n−k)-element subset — the complement S ∖ A. This correspondence is a bijection between k-element subsets and (n−k)-element subsets. Therefore the number of k-element subsets equals the number of (n−k)-element subsets, which is C(n, n−k).
ConcludeBoth sides count the same collection of k-element subsets. Therefore C(n,k) = C(n, n−k). ∎

Proved by bijection between k-element subsets and their complements.

Section 14.13

Capstone Counting Projects

The four problems below each require combining multiple counting methods. Work through each one fully using the Identify → Represent → Count → Justify → Check → Explain framework.

Capstone Problem 1

Return to the Opening Question — Engineering Team Assignments

Problem12 engineers are assigned to security (3 members, 1 lead), user interface (4 members, no roles), and infrastructure (5 members, 1 lead and 1 deputy lead). How many assignments are possible?
ThinkThis is a multi-stage problem. Form the teams first, then assign roles within teams. Use the product rule to connect all stages.
Count Stage 1 — Choose 3 from 12 for security: C(12,3) = 220 Stage 2 — Choose lead from those 3: 3 choices Stage 3 — Choose 4 from remaining 9 for UI: C(9,4) = 126 Stage 4 — Remaining 5 go to infrastructure: 1 way Stage 5 — Choose lead (5) then deputy (4) from infrastructure: 5 · 4 = 20 Total = 220 · 3 · 126 · 1 · 20 = 1,663,200
CheckChoosing security team and lead alternatively: choose lead first (12 ways), then 2 others from remaining 11 (C(11,2) = 55 ways) → 12 · 55 = 660 = 220 · 3. ✓

Answer: 1,663,200 possible assignments

Capstone Problem 2

Inclusion-Exclusion with Integer Divisibility

ProblemHow many integers from 1 to 1000 are divisible by 3, 5, or 7?
RepresentLet A = divisible by 3, B = divisible by 5, C = divisible by 7. Use inclusion-exclusion.
Count |A| = ⌊1000/3⌋ = 333 |B| = ⌊1000/5⌋ = 200 |C| = ⌊1000/7⌋ = 142 |A ∩ B| = ⌊1000/15⌋ = 66 |A ∩ C| = ⌊1000/21⌋ = 47 |B ∩ C| = ⌊1000/35⌋ = 28 |A ∩ B ∩ C| = ⌊1000/105⌋ = 9 |A ∪ B ∪ C| = 333 + 200 + 142 − 66 − 47 − 28 + 9 = 543
CheckThe complement — integers not divisible by any of 3, 5, or 7 — is 1000 − 543 = 457. Plausible: slightly under half of all integers avoid all three divisors. ✓

Answer: 543 integers

Capstone Problem 3

Recurrence for a Tiling Problem

ProblemA 1×n board is tiled using 1×1 squares (red or blue) and 1×2 dominoes (one color). Let aₙ be the number of tilings. Find a recurrence and compute a₁ through a₅.
ThinkThe first position can be covered by a red tile (leaving a 1×(n−1) board), a blue tile (leaving a 1×(n−1) board), or the left half of a domino (leaving a 1×(n−2) board).
Represent aₙ = 2aₙ₋₁ + aₙ₋₂ Initial conditions: a₁ = 2 (red tile or blue tile) a₂ = 5 (RR, RB, BR, BB, or one domino)
Count a₃ = 2(5) + 2 = 12 a₄ = 2(12) + 5 = 29 a₅ = 2(29) + 12 = 70
CheckFor n = 3: eight ways using only single tiles (2³) plus four ways with one domino (2 domino positions × 2 tile colors) = 12. ✓

Answer: a₅ = 70 tilings

Capstone Problem 4

Pigeonhole with a Combinatorial Bound

ProblemA class of 25 students each selected a favorite number from 1 to 8. Prove that at least 4 students selected the same number.
RepresentPigeons: 25 students. Boxes: 8 possible favorite numbers. If each box contained at most 3 students, the maximum total would be 8 · 3 = 24. But there are 25 students.
ConcludeSince 25 > 24 = 8 · 3, at least one box must contain at least 4 students. That is, at least 4 students chose the same favorite number. ∎

Proved by the generalized pigeonhole principle.

Section 14.14

Common Combinatorial Modeling Mistakes

The errors below are not arithmetic mistakes. They are conceptual errors — misidentifying the structure of the problem before any calculation begins. Recognizing them is the first step toward avoiding them.

Mistake 1 — Choosing the wrong model for order

Applying P(n,k) when C(n,k) is needed (or vice versa)

This produces an answer off by a factor of k!. Test: swap two elements in one outcome. If the result is different, order matters and permutations apply. If the result is the same, order does not matter and combinations apply.

Mistake 2 — Wrong repetition assumption

Using nᵏ when the same object cannot repeat, or P(n,k) when repetition is allowed

Check explicitly: can the same element appear more than once in a valid outcome? Repetition and no-repetition formulas are different. Confusing them is one of the most common errors across all counting problems.

Mistake 3 — Applying a formula before representing the restriction

Choosing a method, then "adjusting" for a restriction after the fact

Restrictions must be built into the model before any formula is chosen. Adjust-after approaches almost always lead to double-counting or missing cases. Represent the structure first; the formula follows.

Mistake 4 — Double-counting without correction

Adding two overlapping case sizes without subtracting the intersection

Whenever two cases can share outcomes, adding them without subtracting the intersection counts the shared outcomes twice. Use inclusion-exclusion or verify cases are truly disjoint before adding.

Mistake 5 — Missing cases in casework

Cases that do not cover every valid outcome

Casework is only valid when every valid outcome falls into exactly one case. Before adding case totals, verify that the cases together are exhaustive (nothing missing) and disjoint (nothing counted twice).

Mistake 6 — Treating identical objects as distinct

Labeling and tracking identical objects individually

Stars and bars is for identical objects distributed into distinct bins. The product rule is for distinct objects. Mixing these produces wrong answers. Ask: are the objects distinguishable, or would swapping two of them leave the outcome unchanged?

Mistake 7 — Incomplete existence arguments

"There are more pigeons than boxes, so something must repeat."

A pigeonhole argument must name the pigeons, name the boxes, state the exact numbers, and state the guaranteed conclusion. Vague arguments do not constitute a proof. State the threshold and what it guarantees.

Mistake 8 — Confusing recurrence with closed form

Substituting a recurrence directly where a closed-form expression is needed

A recurrence defines the nth value in terms of earlier values and requires computing forward from initial conditions. A closed form expresses the nth value directly. They are different objects; using one where the other is expected produces errors.

Mistake 9 — Treating generating functions analytically

Substituting numerical values for x in a generating function to "evaluate" it

In this textbook, generating functions are formal power series. The variable x is a placeholder. Do not substitute values for x or ask about convergence. Work algebraically: multiply factors, then extract the coefficient of xⁿ.

Mistake 10 — Stopping at the number

"The answer is 720."

A count without explanation is not a complete combinatorial answer. State what is being counted, why the method is appropriate, and what the number means in context. Every count should be followed by an interpretation connecting the number to the original situation.

Section 14.15

Readiness for Advanced Combinatorics, Probability, and Computer Science

You have reached the end of this textbook. The ideas you have mastered are the foundation for a wide range of advanced subjects. Here is a brief map of where they lead.

What You Now Know

FoundationsSum rule, product rule, complement counting, casework, inclusion-exclusion — applied accurately to a wide range of counting problems.
ArrangementsOrdered arrangements with and without repetition, circular arrangements, arrangements with repeated symbols, restricted arrangements using gap and block methods.
SelectionsUnordered selections with and without repetition, committee problems, restricted selections, distribution problems via stars and bars.
Binomial CoefficientsPascal's Triangle, Pascal's identity, the Binomial Theorem, coefficient extraction, combinatorial interpretations of algebraic expansion.
Inclusion-ExclusionTwo- and three-set formulas, derangement problems, forbidden position problems, probability applications.
PigeonholeBasic and generalized pigeonhole principle, existence arguments distinguishing "how many" from "must something exist."
Combinatorial ProofDouble counting, bijective proof, combinatorial interpretation — proving identities by describing what each side counts.
RecurrencesFirst-order and second-order recurrences, Fibonacci-type sequences, initial conditions, closed forms via characteristic equations.
Generating FunctionsFormal power series, factor construction for restricted selections, product and extraction of coefficients.
Graph CountingHandshaking lemma, complete and bipartite graph edge counts, tree properties, combinatorial reasoning inside network structures.
Designs and SymmetryLatin squares, block designs, tournament schedules, circular equivalences, Burnside's Lemma as a preview.

Where You Are Going

Advanced Pathways from Combinatorics

Probability and Statistics

Combinatorics is the mathematical engine of probability. Permutations, combinations, binomial coefficients, and inclusion-exclusion appear directly in probability calculations. The Binomial distribution, the hypergeometric distribution, and classical probability all depend on the ideas in this book.

Algorithms and Computer Science

Recurrence relations describe the time complexity of recursive algorithms. Graph counting connects to data structures, network algorithms, search problems, and scheduling. Combinatorial search and optimization are major areas of theoretical computer science.

Cryptography

Password security, key space analysis, block cipher design, and coding theory all depend on combinatorial counting. The counting arguments you practiced — especially large counts with restrictions — appear throughout modern cryptography.

Graph Theory

Chapter 12 introduced graph counting as combinatorics applied to relational structures. A full graph theory course extends this into Eulerian paths, Hamiltonian cycles, planarity, chromatic polynomials, matchings, network flows, and Ramsey theory.

Operations Research

Scheduling, assignment, routing, and resource allocation are combinatorial optimization problems. Integer programming and network flow theory build directly on the counting ideas in this book.

Advanced Combinatorics

A graduate course will introduce analytic combinatorics (using generating functions and complex analysis), extremal combinatorics (maximum or minimum structures under constraints), probabilistic combinatorics (using probability to prove combinatorial results), and algebraic combinatorics (group theory, representation theory). Each builds directly on these foundations.

MGU Library Connection

Probability and Statistics — MGU Mathematics Series (direct continuation)
Discrete Mathematics — MGU Mathematics Series (companion or prerequisite)
Introduction to Graph Theory — MGU Library Reference
Algorithms — MGU Computer Science Series
Cryptography — MGU Computer Science Series
Data Science Foundations — MGU Mathematics Series
Operations Research — MGU Mathematics Series
Combinatorics Formula Sheet, Proof Guide, and Counting Method Reference — MGU Library Appendices

Chapter 14 — Back Matter

Chapter Summary

Sec 14.1The combinatorial modeling process — Identify, Represent, Count, Justify, Check, Explain — is the unifying framework. A model is correct when it captures order, repetition, restrictions, overlap, existence vs. count, and recursion accurately.
Sec 14.2The most important question in any problem is what exactly is being counted. The same words can describe sequences, subsets, multisets, or distributions depending on the situation. A taxonomy of combinatorial objects guides the initial identification.
Sec 14.3An ordering model applies when swapping two elements produces a different outcome. Permutation formulas, the gap method for separation, and the block method for togetherness are the primary tools. Handle the most constrained part first.
Sec 14.4A selection model applies when order does not matter. Combination formulas correct overcounting by dividing out the k! ways the selected group could be arranged. Required elements are fixed first; forbidden elements are removed before counting.
Sec 14.5Repetition changes the formulas for both ordered and unordered counting. A four-cell table maps repetition vs. no-repetition onto ordered vs. unordered. Restrictions must be represented before any formula is chosen.
Sec 14.6When categories overlap, inclusion-exclusion corrects the overcounting caused by intersection. Casework is preferred when cases are few and naturally disjoint. Both require care to ensure all outcomes are covered exactly once.
Sec 14.7Existence arguments use the pigeonhole principle: name the pigeons, name the boxes, state the threshold, and conclude precisely. Existence arguments prove something must occur; they do not count how many ways it occurs.
Sec 14.8Recurrence relations describe counts with recursive structure. Write the recurrence, establish initial conditions, and compute forward. The closed form, if needed, comes from solving the characteristic equation.
Sec 14.9Generating functions encode sequences algebraically. Each object contributes a formal factor; the product is the generating function; the coefficient of xⁿ gives the count. Treat the variable x as a formal placeholder, not a number.
Sec 14.10Graph counting uses the Handshaking Lemma, complete graph edge formulas, tree properties, and degree arguments to count structural features of relational networks.
Sec 14.11Each counting strategy has specific conditions under which it is most appropriate. The choice of method follows from the model; the model follows from what is being counted. Comparing strategies is itself a mathematical skill.
Sec 14.12A complete combinatorial argument names the objects, states the model, shows the computation, justifies the method, and interprets the result. A combinatorial proof describes a set and counts it two ways to explain why an identity holds.
Sec 14.13The four capstone problems — engineering assignments, integer divisibility, tiling recurrence, and a pigeonhole bound — demonstrate that real problems combine multiple methods and require all six stages of the modeling process.
Sec 14.14Ten common modeling errors: wrong order model, wrong repetition assumption, formula before restriction, double-counting, missing cases, treating identical objects as distinct, incomplete existence arguments, recurrence vs. closed form confusion, analytic treatment of generating functions, and stopping at the number without interpretation.
Sec 14.15The ideas in this textbook lead directly to probability, algorithms, cryptography, graph theory, coding theory, operations research, and advanced combinatorics. Mastery of the modeling process — not memorization of formulas — is the foundation that carries forward.

Key Terms Review

combinatorial modeling process

The six-stage framework: Identify → Represent → Count → Justify → Check → Explain. Applied before any formula is chosen.

ordering model

A counting model in which position or sequence distinguishes outcomes. Uses permutations. Applied when swapping elements produces a different outcome.

selection model

A counting model in which groups are counted without regard to order. Uses combinations. Applied when swapping elements produces the same outcome.

distribution model

A model for assigning objects to bins. Stars and bars for identical objects; product rule for distinct objects. The choice depends on distinguishability.

complement counting

Computing a count by subtracting undesired outcomes from the total: desired = total − undesired. Especially useful when "at least one" conditions are present.

casework

Dividing a counting problem into disjoint and exhaustive cases, counting each separately, and adding. Valid only when cases are both exhaustive and disjoint.

inclusion-exclusion

A correction formula for overlapping categories: |A ∪ B| = |A| + |B| − |A ∩ B|. Alternately adds and subtracts intersection sizes to correct overcounting.

existence argument

A proof that a certain outcome must exist without finding it explicitly. The pigeonhole principle is the central tool. Proves what must happen, not how many ways.

recurrence relation

An equation expressing a sequence value in terms of earlier values, together with initial conditions that uniquely determine the sequence.

generating function

A formal power series G(x) = Σ aₙxⁿ that encodes a sequence as coefficients. The variable x is a formal placeholder; do not substitute numerical values.

combinatorial proof

A proof of an identity by describing a finite set and counting it two ways: one computation gives the left side, the other gives the right side.

closed form

An expression for the nth term of a sequence that does not refer to earlier terms. Contrasts with a recurrence relation, which requires earlier values.

bijection

A one-to-one correspondence between two sets. Used in bijective proofs to show two sets have the same size without counting either directly.

capstone problem

A multi-method problem requiring the full modeling process. Does not announce its type; requires recognizing structure, selecting methods, and combining them.

Counting Strategy Quick Reference

Situation	Method	Formula
Order matters, no repetition	Permutations	P(n,k) = n! / (n−k)!
Order matters, repetition allowed	Repeated sequences	nᵏ
Order matters, repeated symbols	Multinomial	n! / (n₁! · n₂! · … · nᵣ!)
Order does not matter, no repetition	Combinations	C(n,k) = n! / (k!(n−k)!)
Order does not matter, repetition allowed	Stars and bars	C(n+k−1, k)
Circular arrangements	Circular permutations	(n−1)!
Overcounting from a restriction	Complement or casework	Total − undesired
Overlapping categories	Inclusion-exclusion	\|A ∪ B\| = \|A\| + \|B\| − \|A ∩ B\|
Something must exist	Pigeonhole principle	More than n · k pigeons in n boxes → one box has more than k
Count built from smaller cases	Recurrence relation	aₙ = f(aₙ₋₁, aₙ₋₂, …) with initial conditions
Selections with multiple restrictions	Generating functions	[xⁿ] of product of factor series
Relationship structures	Graph counting	Handshaking lemma, C(n,2) for Kₙ, etc.
Arrangements under symmetry	Burnside's Lemma	(preview — see Chapter 13)

Mixed Counting Practice

These problems do not announce their type. Identify the structure, choose the method, and justify your answer.

Part AConcept Check

A problem asks you to count the number of ways to assign three prizes (first, second, third) to ten contestants. Does order matter? Which formula applies? Why?
A problem asks you to count the number of three-person committees from ten people. Does order matter? Which formula applies? Why?
A problem asks how many ways you can distribute 8 identical cookies among 5 students (each student may receive zero cookies). Name the model and the formula.
A problem asks you to show that among any 13 people in a room, at least 2 must share a birth month. Name the method. Identify the pigeons and boxes.
Explain in one sentence why complement counting is useful. Give an example of a situation where counting desired outcomes directly would be harder than using the complement.

Part BSkill Practice

A school has 8 different clubs. A student must join exactly 2. How many choices?
A license plate: 3 uppercase letters then 3 digits, repetition allowed. How many plates?
A pizza has between 2 and 4 toppings from 10. How many topping combinations?
5-digit strings from digits 1–9 (repetition allowed) with at least one 5. How many?
12 identical books into 4 shelves, each shelf at least 1 book. How many distributions?
From 15 students (6 left-handed), a team of 4 with exactly 2 left-handed. How many?
10 people at a round table. How many distinct seatings?
4 distinct letters then 3 distinct digits (0–9). How many codes?
How many arrangements of the letters in MISSISSIPPI?
From 10 men and 8 women, a committee of 6 with at least 2 women. How many?

Part CProof and Reasoning

Prove combinatorially that C(n,1) + C(n,2) + ⋯ + C(n,n) = 2ⁿ − 1.
Give a combinatorial proof that C(n,k) · k = n · C(n−1, k−1).
Let aₙ be the number of binary strings of length n with no two consecutive 1s. Write a recurrence with initial conditions, and compute a₆.
Use the pigeonhole principle to prove that among any 10 integers, at least two have the same remainder when divided by 9.
Prove that Σₖ₌₀ⁿ C(n,k)² = C(2n,n) by giving a combinatorial argument. (Hint: count n-element subsets of a 2n-element set by splitting the set into two halves of size n.)

Part DApplications

A hospital has 14 nurses for 3 wards: A needs 4, B needs 5, C needs 5. How many assignments?
Keys of length 5 from a 62-character alphabet (A–Z, a–z, 0–9), repetition allowed. (a) How many total keys? (b) How many contain at least one digit?
A tournament with 8 teams, each pair plays exactly once. How many games total?
5 different tasks assigned to 3 employees (each may receive any number). How many assignments?
30 students into 4 project groups of 7, 7, 8, 8 (groups are distinguishable). How many ways?

Error Analysis

Each problem contains an error. Identify it and write the correct solution.

Problem 1

"The number of ways to assign 5 different tasks to 3 employees (each gets at least 1 task) is 3⁵ = 243."

What is wrong? (Hint: what does 3⁵ count? Does it enforce the "at least 1" condition?)

Problem 2

"There are P(7,3) = 210 ways to choose a committee of 3 from 7 people."

Identify the error. Which formula is correct, and why?

Problem 3

"The number of 4-digit PINs (digits 0–9, repetition allowed) with at least one repeated digit is 10⁴ − 10 · 9 · 8 · 7."

Is this correct? Explain what each part counts and confirm or correct the claim.

Problem 4

"The number of ways to distribute 10 identical cookies to 4 children (no restriction) is 4¹⁰."

Identify the error. Which method applies for identical objects, and what is the correct count?

Problem 5

"By inclusion-exclusion: the number of integers from 1 to 100 divisible by 4 or 6 is 25 + 16 = 41."

What is missing? Apply inclusion-exclusion correctly.

Problem 6

"There are (8−1)! = 5040 ways to seat 8 people in a row."

Identify the error. When does (n−1)! apply, and what formula is correct for a row?

Chapter 14 Checkpoint

Complete without assistance — assesses the full scope of Chapter 14 and synthesizes Chapters 1–13

Part A — Identification

For each problem, state which counting method or model is most appropriate. Do not compute; only identify and explain.

Count the number of 7-letter strings (with repetition) from the 26-letter alphabet that begin and end with a vowel.
Count committees of 5 from 12 people where two specific people refuse to serve together.
Prove that among any 25 people, at least 3 share the same birth month.
Find the number of ways to put 9 identical red balls into 4 distinct boxes with each box holding at least 1 ball.
Prove that C(2n,2) = 2·C(n,2) + n² using a combinatorial argument.

Part B — Computation

A database entry: 3-letter code (uppercase letters, no repetition) followed by a 4-digit number (digits 0–9, repetition allowed). How many distinct entries are possible?
A 9-player baseball batting order arranged from a roster of 15. How many orderings?
A bookshelf holds 6 books: 2 identical copies of A, 2 of B, 2 of C. How many distinct arrangements?
How many integers from 1 to 500 are divisible by 2, 3, or 5?
From 20 people (8 from team X, 12 from team Y), how many 6-person committees include at least 2 from team X?

Part C — Explanation and Proof

A student uses P(10,4) = 5,040 to answer: "How many 4-person committees from 10 people?" Explain the error. Provide the correct answer with full justification.
State and prove using any valid combinatorial method: C(n+1, k) = C(n,k) + C(n, k−1).
Write a complete solution using the Identify → Represent → Count → Justify → Check → Explain framework for the following: A choir of 14 singers must be divided into a lead quartet (4 singers in specific roles: soprano lead, alto lead, tenor lead, bass lead) and a backing ensemble of 5 (no assigned roles). How many such divisions are possible?

Answers to the Chapter 14 Checkpoint and practice problems may be placed in the answer key.

End of Textbook

Combinatorics — MGU Mathematics Series, Library Textbook Edition

You have completed the fourteen chapters of this textbook. You have learned to count arrangements and selections, prove counting formulas, recognize finite structures, use recurrence and algebraic methods, count graph structures, and model discrete problems across probability, computing, cryptography, scheduling, design, and operations research.

More than any specific formula, you have practiced a way of thinking: identify the objects, represent the structure, count carefully, justify the method, check the result, and explain what it means. That discipline — not any individual technique — is what makes a combinatorialist. Carry it forward into every quantitative subject you encounter.

Chapter 14:Combinatorics Capstoneand Applications