Chapter 4 — Front Matter
Purpose and Overview
This chapter develops the mathematics of unordered selection. In Chapter 3, you studied arrangements — situations where the order of objects matters and different orderings count as different outcomes. This chapter focuses on the opposite situation: choosing a group of objects where the order of selection is irrelevant, and only the composition of the group matters.
This distinction — order matters versus order does not matter — is one of the most important in all of combinatorics. Confusing it is also one of the most common sources of counting errors. The goal of this chapter is to build the concept of a combination from the ground up, connect it clearly to permutations, develop the binomial coefficient as a central piece of mathematical notation, and apply combinatorial selection to committee problems, restricted choices, probability, and data analysis.
By the end of this chapter, you should be able to recognize when a problem involves an unordered selection, apply the combination formula correctly, handle restrictions and required or forbidden elements, use complementary counting, and interpret your results in context.
Opening Question
A university committee on curriculum must be formed from a department of twelve faculty members. The committee will have five members. No one has been assigned a special role — every committee member has the same status.
How many different committees are possible? Before reading further, consider: does it matter which order the five faculty members were chosen? If Professor Adesanya is chosen first and Professor Nakamura is chosen fifth, is that a different committee from one in which Professor Nakamura is chosen first? The answer is no. A committee is a group, not a sequence. This is the defining feature of a combination.
14Sections
9Objectives
11Key Terms
15+Worked Examples
Why This Chapter Matters
Permutations count arrangements. Combinations count groups. Each has its domain, and both are essential. Committees, teams, data subsets, sample selections in probability, card hands in game theory, encryption key components in cryptography, feature selections in machine learning, subgraphs in graph theory — all of these are modeled by combinations.
The combination formula also produces the binomial coefficients, which appear in Pascal's Triangle, polynomial algebra, probability theory, the Binomial Theorem, and countless other mathematical structures. Understanding combinations opens a major thread running through the rest of this textbook and into higher mathematics.
Learning Objectives
- 1Explain what a combination is and how it differs from a permutation.
- 2Use the combination formula C(n,k) = n! / (k!(n−k)!) to count unordered selections.
- 3Read and interpret binomial coefficient notation C(n,k) or "n choose k."
- 4Solve group-selection problems including committee formation and team selection.
- 5Apply restrictions, required elements, and forbidden elements to combination problems.
- 6Use complementary counting with combinations.
- 7Recognize when a problem calls for a combination versus a permutation.
- 8Apply combinations to basic probability and data-selection contexts.
- 9Identify and avoid the most common combination errors.
Sections 4.1 – 4.3
What a Selection Is and Why Order Does Not Matter
Selections vs. Arrangements · The Overcounting Argument · The Combination Formula
Section 4.1
What a Selection Is
A selection is a choice of objects from a set. The essential feature of a selection is that you are identifying which objects are chosen — not specifying any order among them. Compare these two situations carefully.
| Feature |
Situation A — Arrangement |
Situation B — Selection |
| Scenario |
Three students photographed in labeled positions: left, center, right |
Three students chosen to represent the class at a conference |
| Does order matter? |
Yes — swapping positions produces a different photograph |
No — the group of three representatives is the same group regardless of selection order |
| What is counted? |
Arrangements — sequences of objects in positions |
Groups — subsets of objects with no internal ordering |
| Mathematical structure |
Permutation |
Combination |
The mathematical structure of Situation B — choosing a group where the order of selection does not affect the identity of the group — is what this chapter develops. A selection of k objects from a set of n distinct objects, where order does not matter, is called a combination.
The Subset Connection
A combination of k objects from a set S of n distinct objects is exactly a subset of size k drawn from S. If S = {A, B, C, D} and you are selecting groups of 2, the distinct groups are:
{A, B}
{A, C}
{A, D}
{B, C}
{B, D}
{C, D}
There are six such subsets. Notice that {A, B} and {B, A} are the same subset — they contain the same two elements. Combinations count distinct subsets, not distinct ordered pairs. This is the conceptual foundation of everything that follows.
- In your own words, explain the difference between a combination and a permutation. Give one example of each from everyday life.
- A pizza shop offers 8 toppings. A customer orders a pizza with 3 toppings, and the shop makes the pizza the same way regardless of what order the toppings were requested. Is the number of possible pizzas a combination or a permutation problem? Explain.
- A coach will assign players to three distinct positions: point guard, shooting guard, and center. Is this a combination or permutation? Explain the difference from selecting a 3-person committee.
Section 4.2
Why Order Does Not Matter
When order does not matter, multiple arrangements collapse into a single selection. Understanding this collapse is the key to deriving the combination formula correctly.
Suppose you are choosing a group of 3 people from 5: call them A, B, C, D, E. If you were counting ordered arrangements of 3 from 5, you would count P(5,3) = 5 × 4 × 3 = 60 ordered triples. But many of these triples represent the same group. For example, all six of the following ordered triples correspond to the same unordered group {A, B, C}:
(A, B, C)
(A, C, B)
(B, A, C)
(B, C, A)
(C, A, B)
(C, B, A)
These six ordered arrangements all correspond to the same unordered group {A, B, C}. There are exactly 3! = 6 arrangements of any fixed 3-element group. So the 60 ordered arrangements are organized into groups of 6, each group corresponding to one unordered selection.
The Overcounting Argument
Step 1. Count ordered arrangements of k from n: P(n,k) = n! / (n−k)!
Step 2. Each unordered selection has been counted k! times — once for each ordering of the selected group.
Step 3. Divide: P(n,k) / k! = n! / (k! · (n−k)!)
This quotient is the combination formula. Division by k! is the correction factor that removes the overcounting caused by treating the same group in different orders as different outcomes.
Checking with a Small Case
For choosing 3 from 5: P(5,3) = 60. Each group of 3 is counted 3! = 6 times. Number of groups: 60 / 6 = 10. You can verify this by listing all groups of 3 from {A, B, C, D, E} — there are exactly 10.
- Choosing 2 from {P, Q, R, S}: list all ordered pairs, then list all unordered groups. How many ordered pairs are there? How many unordered groups? What is the ratio?
- Explain why dividing by k! is the correct correction when moving from P(n,k) to C(n,k). Why k! specifically?
- If you choose 4 objects from a set of 7 with order, you get P(7,4) ordered arrangements. How many of these correspond to each single unordered group? How many unordered groups are there?
Section 4.3
Combinations
Definition — Combination
The number of ways to choose k objects from a set of n distinct objects, without regard to order, is denoted C(n,k) and equals:
Boundary Cases
Choosing 0 objects: C(n,0) = n! / (0! · n!) = 1/1 = 1. There is exactly one way to choose nothing — the empty selection.
Choosing all n objects: C(n,n) = n! / (n! · 0!) = 1. There is exactly one way to choose every object.
Choosing 1 object: C(n,1) = n! / (1!(n−1)!) = n. Each of the n objects can be the sole chosen element.
Quick Verification Check
After computing a combination, check the boundary behavior: C(n,0) should equal 1, C(n,n) should equal 1, and C(n,1) should equal n. If any of these fail for your formula, something has gone wrong.
Example 4.1
Choosing a Curriculum Committee
- ProblemA department has 12 faculty members. A 5-person curriculum committee will be formed. All members have equal status. How many different committees are possible?
- ThinkNo positions are assigned. The committee is a group, not a ranked list. Order does not matter. This is a combination problem: choosing 5 from 12 without regard to order.
- RepresentLet the 12 faculty members be the objects. Select a subset of size 5. The number of such subsets is C(12,5).
- Count
C(12,5) = 12! / (5! · 7!)
= (12 × 11 × 10 × 9 × 8) / (5 × 4 × 3 × 2 × 1)
= 95040 / 120
= 792
- CheckThe answer should be at most C(12,6) = 924 (the maximum is achieved near the middle selection size). The answer 792 is slightly less, which is reasonable for k = 5 from n = 12.
- InterpretThere are 792 different possible curriculum committees.
Answer: C(12,5) = 792 committees.
Example 4.2
A Small Case Verified by Listing
- ProblemFour students — Ana, Bo, Cal, Dani — are being considered for a 2-person study pair. No roles are assigned. How many study pairs are possible?
- ThinkOrder does not matter. {Ana, Bo} and {Bo, Ana} are the same pair.
- Count
C(4,2) = 4! / (2! · 2!) = 24/4 = 6
- VerifyThe six pairs: {A,B}, {A,C}, {A,D}, {B,C}, {B,D}, {C,D}. Count by listing: 6 pairs.
- InterpretThe formula and the listing agree. There are 6 possible study pairs.
Answer: C(4,2) = 6 study pairs. Verified by complete listing.
- C(5,2)
- C(7,3)
- C(10,4)
- C(6,6)
- C(8,1)
- C(9,0)
- C(12,3)
- C(15,2)
For C(4,3) and C(5,3), also verify your answers by listing all groups.
Sections 4.4 – 4.6
Binomial Coefficients and Group Selection
Notation · Reading C(n,k) · Symmetry · Group-Selection Problems
Section 4.4
Binomial Coefficients
The expression C(n,k) is so important that it has its own notation and its own name: the binomial coefficient. It is written with n on top and k on the bottom inside large parentheses, read as "n choose k." The term "binomial coefficient" comes from the fact that these numbers appear as the coefficients when a binomial expression (x + y)ⁿ is expanded — a connection developed fully in Chapter 5.
Why "Binomial"?
A binomial is an expression with two terms, like (x + y). When you expand (x + y)ⁿ by multiplying the binomial by itself n times, each term in the result has a coefficient. Those coefficients are exactly the binomial coefficients C(n,0), C(n,1), …, C(n,n). Chapter 5 will show why this is true — and it is a combination argument.
Section 4.5
Reading C(n,k)
When you encounter C(n,k), read it as a question: "In how many ways can I choose k things from n things, if order does not matter?" The top number, n, is the size of the set you are selecting from. The bottom number, k, is the size of the group you are selecting. The restriction 0 ≤ k ≤ n must hold. If k < 0 or k > n, the binomial coefficient is defined to be 0.
| Expression | Reading | Value |
|---|
C(8,3) | Choose 3 from 8 | 56 |
C(10,0) | Choose 0 from 10 | 1 |
C(7,7) | Choose all 7 from 7 | 1 |
C(6,1) | Choose 1 from 6 | 6 |
C(5,2) | Choose 2 from 5 | 10 |
C(5,3) | Choose 3 from 5 | 10 — same as C(5,2)! |
The Symmetry Property
Notice that C(5,2) = C(5,3) = 10. This is not a coincidence. In general: C(n,k) = C(n, n−k).
Why. Choosing k objects to include is the same as choosing the remaining n − k objects to exclude. Every selection of k objects corresponds to exactly one exclusion of n − k objects from the same set. The two counts must be equal.
This symmetry is also useful computationally: if k is large, it may be easier to compute C(n, n−k) instead.
Example 4.3
Using the Symmetry Property
- ProblemCompute C(20,17).
- ThinkC(20,17) = C(20, 20−17) = C(20,3). Computing C(20,3) is far easier than expanding 20! / (17! · 3!) directly with large factorials.
- Count
C(20,3) = (20 × 19 × 18) / (3 × 2 × 1) = 6840 / 6 = 1140
- InterpretC(20,17) = 1140. There are 1,140 ways to choose 17 objects from 20 — the same as choosing which 3 to leave out.
Answer: C(20,17) = C(20,3) = 1,140.
Student Warning — Symmetry Works Within n
The symmetry property is C(n,k) = C(n, n−k). The n stays fixed; only the bottom index changes. Do not confuse this with writing C(k,n), which is undefined when k < n. C(10,7) = C(10,3) = 120, not C(7,10).
Section 4.6
Choosing Groups from a Set
Many real selection problems involve choosing a group from a population where everyone is equally eligible and no role distinctions exist. These are combination problems in their most natural form.
Example 4.4
Choosing a Hand of Cards
- ProblemA standard deck has 52 cards. A hand of 5 cards is dealt. How many distinct hands are possible?
- ThinkA hand is a set of 5 cards. The order in which cards are dealt does not change the hand. This is a combination.
- Count
C(52,5) = (52 × 51 × 50 × 49 × 48) / (5 × 4 × 3 × 2 × 1)
= 311,875,200 / 120
= 2,598,960
- InterpretThere are 2,598,960 distinct 5-card hands in a standard deck. This large number is why card games have so much variety.
Answer: C(52,5) = 2,598,960 distinct hands.
Example 4.5
Choosing Projects to Fund
- ProblemA grant committee must choose 4 projects to fund from a pool of 10 submitted proposals. Each funded project receives the same amount. How many ways can the committee choose?
- ThinkAll funded projects are treated equally — no ranking is applied. This is a combination.
- Count
C(10,4) = (10 × 9 × 8 × 7) / (4 × 3 × 2 × 1) = 5040/24 = 210
- InterpretThere are 210 ways to choose 4 projects from 10 for equal funding.
Answer: C(10,4) = 210.
- Compute C(9,6) using the symmetry property.
- Compute C(100,1).
- Compute C(6,2) × C(8,3).
- C(10,4) + C(10,6) — what do you notice?
- A lottery requires choosing 6 numbers from 1 to 49, order irrelevant. How many tickets?
- A jury of 12 is selected from 50 candidates. How many juries are possible?
- A complete graph on 9 vertices has an edge between every pair. How many edges?
- C(n,2) = 45. Find n. (Hint: write out the formula and solve.)
Sections 4.7 – 4.11
Restrictions, Required Elements, and Forbidden Elements
Composition Requirements · Complementary Counting · Committee Problems · Required and Forbidden
Section 4.7
Combinations with Restrictions
Restrictions change the structure of a selection problem. A restriction is a condition that must be satisfied by every valid selection. Before choosing a formula, you must represent the restriction explicitly.
There are two general strategies for handling restrictions: direct counting (reorganize the problem to count only valid selections) and complementary counting (count all selections, then subtract the invalid ones). This section introduces direct counting through composition requirements.
Strategy — Composition Restrictions
When a selection must contain exactly a certain number from each subgroup (for example, exactly 2 from Group A and 3 from Group B), count each subgroup independently and multiply using the product rule. The two subgroups are chosen in independent steps.
Count from Group A × Count from Group B
Example 4.6
Restriction on Group Composition
- ProblemA library has 8 novels and 6 nonfiction books. A reading group will select 4 books: exactly 2 novels and 2 nonfiction. How many selections are possible?
- ThinkThe selection must satisfy a composition requirement. The novels and nonfiction are chosen independently in separate groups. Use the product rule: count the novel choices, count the nonfiction choices, then multiply.
- RepresentChoose 2 novels from 8: C(8,2). Choose 2 nonfiction from 6: C(6,2). The two choices are independent steps.
- Count
C(8,2) × C(6,2) = 28 × 15 = 420
- CheckThe total unrestricted selections of 4 from 14 is C(14,4) = 1001. The restricted count of 420 is less than 1001. Reasonable.
- InterpretThere are 420 ways to select exactly 2 novels and 2 nonfiction books.
Answer: C(8,2) × C(6,2) = 28 × 15 = 420.
Student Warning — Add vs. Multiply
Use multiplication when combining independent choices at separate steps. Use addition when counting mutually exclusive cases. Choosing 2 novels AND 2 nonfiction is a two-step independent process: multiply. Choosing either all novels OR all nonfiction are two exclusive alternatives: add. Getting this wrong is one of the most common errors in restricted combination problems.
Example 4.7
Restriction Using Complementary Counting
- ProblemA committee of 4 is formed from a group of 5 men and 7 women. The committee must include at least 1 man. How many such committees are possible?
- Think"At least 1 man" is most efficiently handled by complementary counting: subtract the committees with no men from the total. The only excluded case is all-women committees, which is easy to count.
- Count — total (no restriction)
C(12,4) = 495
- Count — excluded (all women)
C(7,4) = 35
- Count — valid
495 − 35 = 460
- CheckThe 35 all-women committees plus the 460 valid committees should total 495. Indeed 460 + 35 = 495. Correct.
- InterpretThere are 460 committees containing at least one man.
Answer: 495 − 35 = 460 valid committees.
Section 4.8
Complementary Selection Problems
Complementary counting is one of the most efficient strategies in combinatorics. The core idea is simple:
Example 4.8
At Least Two of a Type
- ProblemA team of 5 is chosen from 6 engineers and 4 scientists. How many teams contain at least 2 scientists?
- Think"At least 2 scientists" means 2, 3, or 4 scientists. The complement is "at most 1 scientist" — meaning 0 or 1 scientists. The complement is simpler to count.
- Count — total
C(10,5) = 252
- Count — 0 scientists
C(6,5) × C(4,0) = 6 × 1 = 6
- Count — 1 scientist
C(6,4) × C(4,1) = 15 × 4 = 60
- Count — at most 1
6 + 60 = 66
- Count — at least 2
252 − 66 = 186
- Check — direct count
2 scientists: C(4,2)·C(6,3) = 6·20 = 120
3 scientists: C(4,3)·C(6,2) = 4·15 = 60
4 scientists: C(4,4)·C(6,1) = 1·6 = 6
Total: 186 ✓
- InterpretThere are 186 valid teams containing at least 2 scientists.
Answer: 186 teams.
When to Use the Complement
Use complementary counting when the excluded cases are simpler than the valid cases. "At least 1" excludes only "0," which is usually one term. "At least 2" excludes "0 or 1," which is two terms but still often simpler than listing many valid compositions. When both direct and complementary counting seem equally complex, try both and choose the shorter path.
Section 4.9
Committee Problems
Committee problems are a central application of combinations. A committee is a group, not a ranked list. Every committee member is equal unless the problem specifies otherwise. When a problem assigns roles within a committee (chair, secretary, treasurer), the roles add a permutation layer on top of the combination selection.
Example 4.9
Committee with One Designated Role
- ProblemA company has 10 employees. A committee of 5 will be formed, and then one member will be designated as chair. How many outcomes are possible?
- ThinkThis is a two-step process: first choose the group of 5, then designate one as chair. The two steps are connected — the chair must come from the committee.
- Count — Method 1
C(10,5) × 5 = 252 × 5 = 1260
(Choose the group, then choose the chair from within it.)
- Count — Method 2
10 × C(9,4) = 10 × 126 = 1260
(Choose the chair first from all 10, then fill the remaining 4 spots from the other 9.)
- CheckBoth methods give 1260. Agreement confirms the calculation.
- InterpretThere are 1,260 ways to form a 5-person committee with one designated chair.
Answer: 1,260 committee-with-chair outcomes.
Example 4.10
Committee Restriction — Two People Who Refuse to Serve Together
- ProblemFrom a group of 8 people including two rivals — P and Q — who refuse to serve together, how many 3-person committees are possible?
- ThinkUse complementary counting: total committees minus committees containing both P and Q.
- Count — total
C(8,3) = 56
- Count — both P and Q includedIf both P and Q are in the committee, the third member can be any of the remaining 6:
C(6,1) = 6
- Count — valid
56 − 6 = 50
- InterpretThere are 50 valid committees in which P and Q do not both serve.
Answer: 56 − 6 = 50 valid committees.
Section 4.10
Selection with Required Elements
A required element is an object that must appear in every valid selection. When some objects are required, they are effectively pre-selected. The remaining choices are made from what is left.
Strategy — Required Elements
If a selection of k objects from n must include r specific required objects, those r objects are already chosen. Fill the remaining k − r positions from the n − r non-required objects.
Number of valid selections: C(n − r, k − r)
Example 4.11
Required Club Members
- ProblemA hiking club has 15 members. A trail team of 5 must include both the club president and the safety officer. How many trail teams are possible?
- ThinkTwo members are required. They occupy 2 of the 5 spots automatically. The remaining 3 spots are filled from the other 13 members.
- Count
C(15 − 2, 5 − 2) = C(13,3) = (13 × 12 × 11) / 6 = 286
- InterpretThere are 286 possible trail teams that include both required members.
Answer: C(13,3) = 286 trail teams.
Section 4.11
Selection with Forbidden Elements
A forbidden element is an object that cannot appear in any valid selection. When some objects are forbidden, exclude them entirely from the pool before counting.
Strategy — Forbidden Elements
If f objects are forbidden, treat them as if they do not exist. Count selections from the remaining n − f objects only.
Number of valid selections of k from n with f forbidden: C(n − f, k)
Example 4.12
Forbidden Team Members
- ProblemA robotics team has 12 members. Two members are disqualified. A team of 4 must be chosen from eligible members only. How many teams are possible?
- ThinkTwo members are forbidden. Remove them. Count from the remaining 10.
- Count
C(10,4) = 210
- InterpretThere are 210 valid teams.
Answer: C(10,4) = 210.
Example 4.13
Mixed Required and Forbidden
- ProblemFrom 9 candidates, 1 person is required (the project lead must be on the team) and 2 are forbidden (scheduling conflicts). A team of 4 must be formed. How many teams are possible?
- ThinkRemove the 2 forbidden members. The required member is already placed. From the 6 remaining eligible candidates (9 total − 1 required − 2 forbidden = 6 others), choose the final 3 spots.
- Count
C(6,3) = 20
- InterpretThere are 20 valid teams satisfying both constraints.
Answer: C(6,3) = 20.
- A shelf has 10 novels and 8 biographies. A reader selects 5 books: exactly 3 novels and 2 biographies. How many selections are possible?
- A committee of 6 is chosen from 8 scientists and 5 engineers. The committee must include exactly 4 scientists. How many committees are possible?
- From 12 candidates, 3 are disqualified. A team of 5 must be chosen from eligible candidates only. How many teams are possible?
- A selection of 4 items is made from 7 blue items and 5 red items. How many selections contain at least 1 red item?
- A committee of 5 is formed from 9 people. Two specific people — X and Y — cannot both serve. How many valid committees are there?
- A class of 20 students will form a study group of 4. The student council president must be included. How many study groups are possible?
- From 11 applicants (including 4 with prior experience), a selection of 3 must include at least 2 applicants with prior experience. How many selections are valid?
- A panel of 6 is chosen from 10 experts. One specific expert must be included and another must be excluded. How many valid panels are possible?
Sections 4.12 – 4.14
Applications, Common Mistakes, and the Road Ahead
Combinations in Probability · Common Mistakes · Preparing for Binomial Patterns
Section 4.12
Combinations in Probability and Data Problems
Combinations are fundamental to probability. When a sample is drawn uniformly at random from a population, the probability of any particular event is:
Example 4.14
Probability of Exactly 3 Hearts
- ProblemA hand of 5 cards is dealt from a standard 52-card deck. What is the probability that the hand contains exactly 3 hearts?
- ThinkThe sample space is all 5-card hands. The event is "exactly 3 hearts." Count favorable outcomes using combinations: 3 hearts from the 13 in the deck, and 2 non-hearts from the remaining 39.
- Total outcomes
C(52,5) = 2,598,960
- Favorable outcomes
C(13,3) × C(39,2) = 286 × 741 = 211,926
- Probability
P = 211,926 / 2,598,960 ≈ 0.0815
- InterpretThere is approximately an 8.15% probability that a random 5-card hand contains exactly 3 hearts.
Answer: P ≈ 0.0815 (about 8.15%).
Example 4.15
Selecting a Data Sample by Region
- ProblemA database contains 20 customer records: 8 from Eastern, 7 from Western, 5 from Central regions. An analyst randomly selects 3 records for review. What is the probability that all 3 are from the same region?
- ThinkCount all-Eastern, all-Western, and all-Central selections. These cases are mutually exclusive, so add them.
- Total
C(20,3) = 1140
- Favorable
C(8,3) + C(7,3) + C(5,3) = 56 + 35 + 10 = 101
- Probability
P = 101 / 1140 ≈ 0.0886
- InterpretThere is approximately an 8.86% probability that all three reviewed records come from the same region.
Answer: P ≈ 0.0886 (about 8.86%).
MGU Library Connection — Combinations in Computing and Data Science
- In data analysis and machine learning, combinations appear when selecting features or variable subsets. If a dataset has n features and a model tests all subsets of k, there are C(n,k) such subsets — growing very rapidly for large n.
- This explosive growth explains why exhaustive feature search is computationally prohibitive and motivates smarter selection algorithms.
- The role of combinatorics in feature selection and algorithmic search is developed in the MGU Data Science Foundations and Machine Learning Mathematics chapters.
- Cryptography students will find combinations in key-space analysis and error-correcting code design — see MGU Cryptography and Coding Theory chapters.
Section 4.13
Common Combination Mistakes
The following mistakes appear frequently in student work. Each one involves a genuine conceptual misunderstanding, not merely a computation slip. Recognizing and understanding them now will prevent wasted effort on every selection problem you encounter.
Mistake 1 — Using a Permutation When a Combination Is Correct
C(10,3) asked. Student computes P(10,3) = 720.
Why it happens: the student multiplied correctly but failed to recognize that committees are unordered groups. Ask: does the order of selection change the outcome? If no, use C(n,k). A committee of Alice, Bo, and Cal is the same regardless of who was chosen first.
Mistake 2 — Using a Combination When a Permutation Is Correct
3 prizes (1st, 2nd, 3rd) from 10 contestants. Student computes C(10,3) = 120 instead of P(10,3) = 720.
Why it happens: student recognized "choose 3 from 10" but ignored that the prizes are ranked. Ask: does the assignment of roles matter? If yes, the positions are distinct — use a permutation.
Mistake 3 — Adding Instead of Multiplying Independent Choices
2 novels from 8 AND 2 nonfiction from 6. Student writes C(8,2) + C(6,2) = 43.
Why it happens: student treated two simultaneous independent steps as alternatives. Independent choices at separate steps multiply. Use addition only for mutually exclusive alternatives (Case A or Case B, not Case A and Case B).
Mistake 4 — Skipping the Restriction Entirely
Problem requires at least 1 from each group. Student counts all selections without applying the restriction.
Why it happens: the restriction was read but not modeled. Before computing, write out what the restriction requires. For "at least 1 from each group," plan your strategy — direct casework or complementary counting — before reaching for a formula.
Mistake 5 — Double-Counting Across Cases
Casework counts Case A and Case B, but the same outcome belongs to both.
Why it happens: cases were not defined carefully. Verify that cases are mutually exclusive (no outcome belongs to two cases) and exhaustive (every outcome belongs to at least one case). Use the sum rule only for mutually exclusive cases.
Mistake 6 — Forgetting Required or Forbidden Elements
Student counts all selections without pre-selecting required members or excluding forbidden ones.
Why it happens: the constraint was stated but not built into the count. Before applying any formula, identify the effective pool size after removing forbidden elements and accounting for required ones.
Mistake 7 — Misreading the Symmetry Property
Student writes C(10,7) = C(7,10), claiming the answer is 0 or undefined.
Why it happens: the symmetry flips the bottom index within the same n. The correct symmetry is C(10,7) = C(10, 10−7) = C(10,3) = 120. The n stays fixed; only the bottom index changes.
Section 4.14
Preparing for Binomial Patterns
This chapter introduced the combination formula C(n,k) as a count of unordered selections. Chapter 5 will show that these same numbers appear as coefficients when a binomial expression (x + y)ⁿ is expanded.
The connection is not accidental. When you expand (x + y)ⁿ by multiplying the binomial by itself n times, the coefficient of the term x^(n−k) · y^k is C(n,k) — because expanding the product involves choosing which k of the n factors contribute a y rather than an x. That choice is a combination.
This means that every skill developed in this chapter — computing C(n,k), using the symmetry property, interpreting the formula as a count — directly supports the work of Chapter 5. Pascal's Triangle, the Binomial Theorem, combinatorial identities, and many important algebraic properties all build from what you have learned here.
Looking Ahead — Chapter 5: Binomial Coefficients and Pascal's Triangle
Chapter 5 will organize the values of C(n,k) into Pascal's Triangle and reveal a remarkable pattern: each entry equals the sum of the two entries above it. This is Pascal's Identity — C(n,k) = C(n−1,k−1) + C(n−1,k) — and it has a beautiful combinatorial proof using the ideas of this chapter. The Binomial Theorem will then show how these numbers arise in algebraic expansion. Every combination skill you have built here carries directly into that material.
- A bag contains 6 red and 4 green marbles. Three are drawn without replacement. What is the probability that all 3 are red?
- A dataset has 15 variables. A researcher will test all possible pairs of variables for correlation. How many pairs must be tested?
- A conference has 9 speakers. Organizers choose 4 for a panel (no roles). If one specific speaker must be included, how many panels are possible?
- Identify the mistake: "From a group of 10, a team of 3 is chosen. The count is P(10,3) = 720." What is the correct count?
- Identify the mistake: "A shelf has 6 science and 4 history books. Choosing 2 science and 2 history books: C(6,2) + C(4,2) = 21." What is the correct count?
- Identify the mistake: "How many 5-person committees can be chosen from 12 people, given that person A must be excluded? Answer: C(12,5) = 792." What is the correct count?
Chapter 4 — Back Matter
Chapter Summary
- Sec 4.1A combination is a selection of k objects from n distinct objects where order does not matter. A combination is equivalent to a subset of size k. Contrast with permutations, where position or order matters.
- Sec 4.2The combination formula arises from dividing the permutation count P(n,k) by k!, the number of orderings of any fixed group of k objects. Division by k! removes the overcounting caused by treating the same group in different orders as distinct.
- Sec 4.3C(n,k) = n! / (k!(n−k)!). Boundary cases: C(n,0) = C(n,n) = 1, and C(n,1) = n. Always verify boundary cases when working with new combination problems.
- Sec 4.4The binomial coefficient C(n,k), read "n choose k," is the standard notation for combinations. The name "binomial" reflects the appearance of these numbers as coefficients in the expansion of (x+y)ⁿ.
- Sec 4.5The symmetry property: C(n,k) = C(n, n−k). Choosing k objects is equivalent to choosing which n−k objects to exclude. Use symmetry to simplify computation when k is close to n.
- Sec 4.6Group-selection problems — card hands, project choices, juries, representative panels — are the natural domain of combinations. When all selected objects are equal, use C(n,k).
- Sec 4.7Composition restrictions require choosing independently from each subgroup and multiplying. Independent choices multiply; mutually exclusive alternatives add. Misidentifying this relationship is one of the most common errors.
- Sec 4.8Complementary counting: valid = total − invalid. Most efficient when the complement is simpler. "At least 1" phrases almost always signal this approach. Always verify by checking that valid + invalid = total.
- Sec 4.9Committee problems are pure combination problems unless roles are assigned. When roles are added, a permutation layer multiplies the combination count. Two-method verification (select group then role; select role then group) provides a useful check.
- Sec 4.10Required elements are pre-selected; reduce both the pool and the selection size: choose k − r from n − r remaining objects. Formula: C(n−r, k−r).
- Sec 4.11Forbidden elements are removed entirely from the pool before counting. Formula: C(n−f, k). For mixed required-and-forbidden problems, apply both adjustments: remove forbidden, place required, count from the remainder.
- Sec 4.12Combinations appear in probability whenever outcomes are unordered samples. P(event) = (favorable combinations) / (total combinations). This structure governs card probabilities, data sampling, and feature selection in computing.
- Sec 4.13Seven common mistakes: permutation used instead of combination; combination used instead of permutation; addition where multiplication is needed; restriction skipped; cases double-counted; required or forbidden elements ignored; symmetry misread.
- Sec 4.14The binomial coefficients C(n,k) will reappear in Chapter 5 as the entries of Pascal's Triangle and as the coefficients of the Binomial Theorem. The counting argument for why they appear in algebraic expansion is a direct application of the ideas of this chapter.
Key Terms Review
combination
A selection of k objects from a set of n distinct objects in which order does not matter. Equivalent to choosing a subset of size k.
binomial coefficient
The number C(n,k), read "n choose k," counting unordered selections of k from n. Named for its role as coefficients in binomial expansion.
selection
A choice of a subset of objects from a larger set, with no ordering imposed on the chosen objects.
symmetry property
C(n,k) = C(n, n−k). Choosing k objects is equivalent to choosing which n−k objects to exclude. The n stays fixed.
required element
An object that must appear in every valid selection. Pre-select it and reduce the remaining pool and selection size accordingly.
forbidden element
An object that cannot appear in any valid selection. Remove it from the pool entirely before counting.
complementary counting
Valid = Total − Invalid. A strategy used when the excluded cases are simpler to count than the valid cases. "At least one" problems are a frequent application.
restriction
A condition that must be satisfied by every valid selection. Must be modeled explicitly before any counting formula is applied.
committee problem
A selection problem in which a group of people is chosen from a larger pool with no role distinctions among members — the natural application of combinations.
overcounting
Including the same outcome more than once in a count. The combination formula corrects the overcounting in P(n,k) by dividing by k!.
correction factor
A divisor applied to remove overcounting. In combinations, the correction factor is k!, the number of orderings of any group of k selected objects.
Concept Review Questions
- What is the difference between a combination and a permutation? Give one example of each from everyday life.
- Explain in your own words why the combination formula divides the permutation count P(n,k) by k!.
- Why does C(n,0) = 1? What does it mean to choose zero objects from a set?
- State the symmetry property of binomial coefficients. Explain it in terms of choosing versus excluding objects.
- What does it mean for an element to be required in a selection problem? How does this change the computation?
- When is complementary counting a better strategy than direct counting? Give an example of a "signal phrase" that often indicates complementary counting should be used.
- A student says: "I used P(7,3) = 210 to count the number of ways to choose a 3-person team from 7." What mistake was made?
- In a probability problem involving unordered samples, how do combinations appear in the numerator and the denominator of the probability fraction?
- C(6,2)
- C(9,3)
- C(12,4)
- C(15,5)
- C(20,17) — use symmetry
- C(7,0)
- C(8,8)
- C(100,1)
- C(10,4) + C(10,6)
- C(6,2) × C(8,3)
For each scenario: identify whether a permutation or combination is required. Explain your reasoning. Set up (but do not necessarily compute) the appropriate count.
- Eight runners compete in a race. How many ways can the gold, silver, and bronze medals be awarded?
- A book club of 15 members selects 4 to attend an author event. No special roles are assigned.
- A password consists of 4 distinct letters chosen from the 26-letter alphabet, where order matters.
- A jury of 12 is selected from a pool of 50 candidates, all serving as equal jurors.
- From 10 paintings, a museum chooses 3 to display in positions labeled A, B, and C.
- From the same 10 paintings, the museum displays 3 in an unranked exhibit.
- A teacher selects 5 students from 30 for a study group. No leader is assigned.
- A director casts 3 actors from 20 into the roles of King, Queen, and Jester.
- A committee of 4 is chosen from 7 juniors and 5 seniors. The committee must include at least 2 seniors. How many valid committees are there?
- A panel of 7 is chosen from 10 residents of City A and 9 residents of City B. The panel must have at least 3 from each city. How many panels are possible?
- A selection of 6 is made from 14 people including 2 rivals who refuse to serve together. How many valid selections are there?
- A team of 5 is selected from 8 programmers and 6 designers. The team must include at least 2 designers and at least 2 programmers. How many valid teams are there?
- From 9 applicants (including 3 with advanced certification), a group of 4 must include exactly 2 with advanced certification. How many groups are possible?
- How many 4-person committees can be formed from a group of 14 people?
- A committee of 5 is formed from 12 people, and then a chair is chosen from the committee. How many outcomes are possible?
- From 15 faculty members, a search committee of 6 must include both the department chair and the graduate director. How many such committees can be formed?
- A 7-person advisory council is formed from 10 residents of City A and 9 residents of City B. The council must have at least 3 from each city. How many councils are possible?
- Lottery. A lottery requires choosing 6 numbers from 1 through 49, with no repetition and no order. How many distinct tickets are possible?
- Graph theory preview. A complete graph on 8 vertices has an edge between every pair of vertices. How many edges does it have?
- Probability. A bag contains 6 red and 4 green marbles. Three marbles are drawn without replacement. What is the probability that all 3 are red?
- Data analysis. A dataset has 15 variables. A researcher wants to test all possible pairs for correlation. How many pairs must be tested?
- Scheduling. A conference has 9 speakers. Organizers must choose 4 for a panel (no roles). One specific speaker must be included. How many panels are possible?
- Team building. A company has 10 employees in Team A and 8 in Team B. A cross-functional group of 5 must include at least 2 from each team. How many groups satisfy this?
- Probability. A hand of 5 cards is dealt from a 52-card deck. What is the probability the hand contains exactly 2 aces?
Error Analysis
Each solution below contains a mistake. Identify and explain the error, then give the correct solution.
Problem 1
From a group of 10, a team of 3 is chosen. Student answer: P(10,3) = 720.
Identify the error. What is the correct count and formula?
Problem 2
A shelf has 6 science and 4 history books. Selecting 2 science and 2 history: C(6,2) + C(4,2) = 15 + 6 = 21.
What operation error was made? What is the correct answer?
Problem 3
How many 5-person committees from 12 people, given that person A must be excluded? Answer: C(12,5) = 792.
What constraint was ignored? What is the correct answer?
Problem 4
A committee of 4 must have at least 1 woman (7 men, 5 women). Student computes the "at least 1 woman" cases directly AND separately adds C(12,4).
Explain what went wrong. Write the correct complementary counting solution.
Problem 5
A student writes C(10,7) = C(7,10) = 0, claiming the answer is undefined because 10 > 7.
Is this correct? Explain the symmetry property correctly and compute the right answer.
Chapter 4 Checkpoint
Chapter 4 Checkpoint
Complete without assistance — assesses all key skills and concepts from Chapter 4
Section A — Computation
- Compute
C(11,4).
- Compute
C(9,6) using the symmetry property.
- Compute
C(8,3) × C(6,2).
Section B — Concept
- A student is asked to count the number of 4-person groups that can be formed from 10 people. She computes 10 × 9 × 8 × 7 = 5040. What did she compute, and what should she compute instead?
- Explain in one paragraph why the combination formula divides by k!.
- State the symmetry property. Explain what it means in terms of choosing versus excluding objects.
Section C — Problems
- A jury of 6 is selected from 14 candidates. How many juries are possible?
- A team of 5 is selected from 8 programmers and 6 designers. The team must include at least 2 designers. How many valid teams are there?
- From 12 people including persons R and S who refuse to work together, how many 4-person committees are possible?
- A committee of 5 must include the department chair. The department has 11 eligible members. How many committees are possible?
Section D — Applications
- A standard deck of 52 cards is divided into 4 suits of 13 cards each. A hand of 5 is dealt. How many hands contain exactly 2 spades and 3 hearts?
- A bag has 7 white and 5 black balls. Three balls are drawn without replacement. What is the probability that exactly 2 are white?
Section E — Reflection
- Write a short paragraph explaining when to use a combination and when to use a permutation. Give one example of each, and explain which feature of the problem determined your choice.
Looking Ahead
Chapter 5: Binomial Coefficients and Pascal's Triangle
Chapter 4 gave you the combination formula and the binomial coefficients C(n,k). Chapter 5 will organize these numbers into Pascal's Triangle, reveal recursive patterns, establish the symmetry property as an identity, and prove Pascal's Identity — C(n,k) = C(n−1,k−1) + C(n−1,k) — using a combinatorial argument. The Binomial Theorem will then show that the coefficients of (x+y)ⁿ are exactly the binomial coefficients, for a reason rooted in counting choices. Every computational and conceptual skill built in Chapter 4 carries directly into that material.
MGU Library Connection
- Chapter 5: Binomial Coefficients and Pascal's Triangle — the direct continuation of this chapter's ideas into algebraic patterns and identities
- Chapter 7: Inclusion-Exclusion and Overlapping Structures — extends restricted counting to overlapping categories
- Chapter 9: Combinatorial Identities and Proof — proves identities involving C(n,k) by combinatorial argument
- MGU Probability and Statistics — binomial probabilities and hypergeometric probabilities use the combination formula directly
- MGU Computer Science and Algorithms — combinations appear in subset enumeration, search space analysis, and complexity theory
- MGU Cryptography — key-space analysis and error-correcting code design use combinatorial selection
- MGU Data Science Foundations — feature selection and sampling methods are built on combinatorial counting
- Combination Formula Reference — Appendix F of this textbook