MGU Mathematics Series — Discrete Mathematics
Part III: Counting, Probability, and Combinatorics
Permutations · Combinations · Binomial Theorem · Discrete Probability
Chapter 8 of 14
MGU Mathematics Series  ·  Discrete Mathematics  ·  Library Textbook Edition

Chapter 8:
Permutations, Combinations,
and Discrete Probability

Arrangements, selections, factorials, binomial coefficients, Pascal's Triangle, the Binomial Theorem, and counting-based probability — the tools that make combinatorics precise

■ Math Level: Discrete Mathematics ■

■ 14 Sections  •  Part III of 5 ■

Follows Chapter 7: Counting Principles  ·  Prepares students for Chapter 9: Advanced Counting and Combinatorial Reasoning

Chapter 8 — Front Matter

Purpose and Overview

Chapter 7 introduced the fundamental principles of counting: the sum rule, the product rule, complement counting, and inclusion-exclusion. Those tools helped you count outcomes by organizing choices into structured decisions. Chapter 8 deepens that foundation by naming and formalizing two of the most important kinds of counting problems: arrangements and selections.

When the order of choices matters, you are counting arrangements. When only which items are chosen matters — not their order — you are counting selections. These two ideas appear everywhere in mathematics and computing: scheduling, passwords, cryptographic keys, card games, survey design, probability, and combinatorial proofs.

This chapter also introduces discrete probability, which is probability built entirely on counting. In a finite setting where all outcomes are equally likely, probability is simply a ratio: the number of favorable outcomes divided by the total number of outcomes. No calculus is needed. No continuous distributions or density functions are required. Discrete probability is counting applied to chance.

Opening Question

A committee of five students is to be chosen from a group of twelve. Two different students will also be designated as chair and co-chair of the committee. How many ways can this be arranged? Before you can answer this question, you need to decide: does the problem involve arrangements, selections, or both? As you work through this chapter, you will return to this question and solve it with confidence.

14Sections
14Objectives
17Key Terms
20+Worked Examples

Why This Chapter Matters

Counting arrangements and selections is not merely a mathematical exercise. In computer security, the number of possible passwords determines how resistant a system is to brute-force attack. In cryptography, the size of a key space determines whether encryption is feasible to break. In database design, the number of ways to order or group records matters. In probability and statistics, combination counts underlie virtually every calculation involving random samples. In algorithm design, knowing how many cases a brute-force algorithm must examine tells you whether it will run in seconds or centuries.

Learning Objectives

  1. 1Explain the difference between an arrangement and a selection.
  2. 2Compute factorials and use them in formulas.
  3. 3Use the permutation formula to count ordered arrangements without repetition.
  4. 4Use permutation formulas with repetition to count arrangements where items may repeat.
  5. 5Use the combination formula to count unordered selections.
  6. 6Decide whether a problem requires a permutation, a combination, or both.
  7. 7Compute and interpret binomial coefficients.
  8. 8Identify patterns in Pascal's Triangle and connect them to binomial coefficients.
  9. 9Use the Binomial Theorem as an algebraic identity for expanding powers of binomials.
  10. 10Compute probabilities in finite, equally-likely settings using counting.
  11. 11Compute probabilities that involve combinations.
  12. 12Calculate expected value in simple finite settings.
  13. 13Identify and avoid the most common permutation and combination mistakes.
  14. 14Describe how this chapter connects to combinatorics, probability theory, algorithms, and data science.
Chapter 8 — Contents

Sections at a Glance

Sections 8.1 – 8.2
Arrangements, Selections, and Factorials
The Core Question · Signal Words · Factorial Definition · Simplification
Section 8.1

Arrangements and Selections

Before applying any formula, you must ask one question: does the order of choices matter? Consider two situations. In the first, three students — Amara, Beto, and Cleo — are finalists for three distinct awards: first place, second place, and third place. Amara getting first and Beto getting second is a different outcome from Beto getting first and Amara getting second. This is an arrangement problem, and it is counted with a permutation. In the second situation, those same three students are simply chosen to serve together on a committee. The committee of {Amara, Beto} is the same committee regardless of who was chosen first. This is a selection problem, counted with a combination.

How to Identify the Type

If the problem involves…Then…Use…
Distinct positions, roles, or ranksOrder mattersPermutation
A group with no internal structureOrder does not matterCombination
Words: first, arrange, rank, sequence, scheduleOrder mattersPermutation
Words: choose, select, committee, team, subsetOrder does not matterCombination
Student Warning

Do not rush to a formula before deciding whether order matters. Applying the wrong formula gives a wrong answer that can be very hard to detect. Read the problem carefully, identify what makes two outcomes different, and only then choose your tool.

Section 8.2

Factorials

Factorials are the arithmetic foundation for both permutations and combinations. For any positive integer n, the factorial of n, written n!, is the product of all positive integers from 1 to n.

Definition — Factorial
n! = n · (n − 1) · (n − 2) · · · 2 · 1

By convention: 0! = 1

This convention is required to make permutation and combination formulas work correctly in boundary cases. It is not arbitrary.

nn!nn!
015120
116720
2275,040
36103,628,800
42420≈ 2.4 × 10¹⁸
Tip — Canceling Factorials

Many formulas involve ratios of factorials. Cancel common factors before multiplying: 7!/5! = (7 · 6 · 5!)/5! = 7 · 6 = 42. This avoids computing large products unnecessarily.

Example 8.2.1
Computing and simplifying factorial expressions
  • ProblemCompute 8!/6! and 9!/(3! · 6!).
  • ThinkCancel the common factorial factor rather than computing large products in full.
  • Solve 8! / 6! = (8 · 7 · 6!) / 6! = 8 · 7 = 56 9! / (3! · 6!) = (9 · 8 · 7 · 6!) / (6 · 6!) = (9 · 8 · 7) / 6 = 504 / 6 = 84
  • Check8 · 7 = 56. And 9 · 8 · 7 = 504, then 504/6 = 84. Both verify.
Answer: 8!/6! = 56 and 9!/(3! · 6!) = 84.
Sections 8.3 – 8.4
Permutations: Counting Ordered Arrangements
Without Repetition · With Repetition · Identical Elements
Section 8.3

Permutations Without Repetition

A permutation of items is an ordered arrangement. When items are chosen from a larger set and each item may be used at most once, we are counting permutations without repetition. Suppose you have n distinct items and want to arrange r of them in order. There are n choices for the first position, then n − 1 for the second, then n − 2 for the third, and so on. By the product rule, the total is n · (n−1) · (n−2) · · · (n−r+1) — a product of r consecutive integers starting from n.

Formula — Permutations Without Repetition
P(n, r) = n! / (n − r)!

Also written ₙPᵣ or nPr. Read: "the number of permutations of n things taken r at a time."

The (n − r)! cancels the unwanted tail of the factorial, leaving exactly r factors.

Example 8.3.1
Race placements
  • ProblemEight runners compete in a race. How many ways can first, second, and third place be awarded?
  • ThinkThe positions are distinct, so order matters. We choose 3 runners from 8 without repetition.
  • Solve P(8, 3) = 8! / (8 − 3)! = 8! / 5! = 8 · 7 · 6 = 336
  • Check8 choices for first, 7 for second, 6 for third: 8 · 7 · 6 = 336. Matches the formula. ✓
Answer: 336 ways to award first, second, and third place.
Example 8.3.2
Arranging all items — why 0! = 1 matters
  • ProblemHow many ways can five distinct books be arranged on a shelf?
  • ThinkAll five books are being arranged, so n = 5 and r = 5.
  • Solve P(5, 5) = 5! / (5 − 5)! = 5! / 0! = 120 / 1 = 120
  • CheckArranging n items always gives n!. If 0! were 0, the formula would fail here. This confirms why 0! = 1.
Answer: 120 ways to arrange the five books.
Example 8.3.3
Four-letter sequences from an alphabet
  • ProblemHow many four-letter sequences can be formed from the 26-letter alphabet if no letter may be repeated?
  • ThinkArranging 4 letters chosen from 26, without repetition. Order matters because ABCD ≠ DCBA.
  • Solve P(26, 4) = 26! / 22! = 26 · 25 · 24 · 23 = 358,800
Answer: 358,800 four-letter sequences.
Tip

Always verify that r ≤ n. If you are asked to arrange more items than are available without repetition, the answer is zero — it cannot be done.

Section 8.4

Permutations With Repetition

Sometimes each position can be filled with any of the available items, and an item can be selected more than once. When filling r positions with n choices available for each position independently, the product rule gives the simple formula nr. This is easier than the without-repetition formula because there is no reduction in choices at each step.

Formula — Permutations With Repetition
Arrangements with repetition = n^r

Where n is the number of choices at each position and r is the number of positions.

Example 8.4.1
Four-digit PIN codes
  • ProblemHow many four-digit PIN codes are possible if each digit can be any of the ten digits 0 through 9?
  • ThinkEach of the four positions can be any digit, and digits may repeat: n = 10, r = 4.
  • Solve10^4 = 10,000
  • CheckPINs range from 0000 to 9999, which is exactly 10,000 total values. ✓
Answer: 10,000 possible PIN codes.
Example 8.4.2
License plates
  • ProblemA license plate format consists of three letters followed by three digits. Letters and digits may repeat. How many distinct plates are possible?
  • ThinkThree letter positions: 26 choices each. Three digit positions: 10 choices each. Both allow repetition. Use the product rule to combine.
  • Solve26^3 · 10^3 = 17,576 · 1,000 = 17,576,000
Answer: 17,576,000 distinct license plates.

Arrangements of Items With Identical Elements

A different kind of repetition occurs when the items being arranged are not all distinct. Suppose you want to arrange the letters in MISS: M, I, S, S — with two identical S's. If the S's were labeled S₁ and S₂, there would be 4! = 24 arrangements. But since the two S's are identical, swapping them produces the same arrangement, so we divide by 2!. The general formula when n items include groups of identical items of sizes n₁, n₂, …, nₖ is:

Formula — Multinomial Arrangements
n! / (n₁! · n₂! · · · nₖ!)

Where n is the total number of items and n₁, n₂, …, nₖ are the sizes of the identical groups.

Example 8.4.3
Arranging letters with repeated elements
  • ProblemHow many distinct arrangements of the letters in the word COMMITTEE are there?
  • ThinkCount the letters: C, O, M, M, I, T, T, E, E. That is 9 letters. M appears twice, T appears twice, E appears twice.
  • Solve 9! / (2! · 2! · 2!) = 362,880 / 8 = 45,360
Answer: 45,360 distinct arrangements of the letters in COMMITTEE.
Sections 8.5 – 8.6
Combinations and Choosing the Right Tool
Unordered Selections · Symmetry · Comparison Table · Multi-Stage Problems
Section 8.5

Combinations

A combination is a selection of items from a larger set where order does not matter. Two selections are the same combination if they contain exactly the same items, regardless of the order they were chosen. To derive the formula, start with the number of ordered arrangements P(n, r) = n!/(n−r)!. Every unordered selection of r items corresponds to exactly r! ordered arrangements of those same items — one for each way of ordering the selected group. So we divide by r! to remove the ordering.

Formula — Combinations (Binomial Coefficient)
C(n, r) = n! / (r! · (n − r)!)

Also written as the binomial coefficient C(n,r) or "n choose r." This is one of the most important quantities in all of discrete mathematics.

Key symmetry: C(n, r) = C(n, n − r). Choosing r items to include is equivalent to choosing n − r items to exclude.

Example 8.5.1
Forming a committee
  • ProblemA club has twelve members. A committee of four is to be selected. How many possible committees are there?
  • ThinkThe committee has no internal rank. Only which four members are chosen matters, not the order. This is a combination.
  • Solve C(12, 4) = 12! / (4! · 8!) = (12 · 11 · 10 · 9) / (4 · 3 · 2 · 1) = 11,880 / 24 = 495
  • CheckNumerator: 12 · 11 · 10 · 9 = 11,880. Denominator: 4! = 24. Then 11,880/24 = 495. ✓
Answer: 495 possible committees.
Example 8.5.2
Selecting cards from a deck
  • ProblemFrom a standard deck of 52 playing cards, how many ways can a hand of 5 cards be dealt?
  • ThinkA hand of cards is unordered — it does not matter in what sequence you receive them.
  • Solve C(52, 5) = (52 · 51 · 50 · 49 · 48) / 5! = 311,875,200 / 120 = 2,598,960
Answer: 2,598,960 possible five-card hands.
Tip — Use Symmetry to Simplify

When r is large but n − r is small, use the smaller value. C(100, 97) = C(100, 3) = (100 · 99 · 98)/6 = 161,700. Choosing 97 to include is the same as choosing 3 to exclude.

Section 8.6

Choosing Between Permutations and Combinations

The most important skill in this chapter is identifying which counting formula applies. Ask yourself: does a different ordering of the same items produce a different outcome? If yes, use a permutation. If no, use a combination.

SituationOrder Matters?Tool
Awarding first, second, third prizes to 3 of 10 peopleYesPermutation
Choosing a 5-person committee from 20 candidatesNoCombination
Arranging 7 books on a shelfYesPermutation
Selecting 3 toppings from 10 availableNoCombination
Assigning president, VP, and secretary from a groupYesPermutation
Choosing 4 students to represent a classNoCombination
Setting a 6-digit combination lockYesPermutation
Dealing a 4-card hand from a deckNoCombination
Student Warning — "Combination Lock"

The everyday word "combination" (as in a combination lock) is misleading. A combination lock actually uses an ordered sequence — entering 3-14-7 is different from 7-14-3. In mathematics, "combination" has a precise meaning: unordered selection. A combination lock is really a permutation lock.

Example 8.6.1
Filling distinct positions
  • ProblemA group of 8 people applies for 3 distinct positions: director, assistant director, and coordinator. How many ways can the positions be filled?
  • ThinkThree distinct positions are assigned. A different assignment is a different outcome, so order matters.
  • SolveP(8, 3) = 8! / 5! = 8 · 7 · 6 = 336
Answer: 336 ways to fill the three positions.
Example 8.6.2
Forming an advisory panel
  • ProblemThe same group of 8 people forms a three-person advisory panel with no titles or ranks. How many panels are possible?
  • ThinkThe panel has no internal structure. The same three people form the same panel regardless of who was selected first.
  • SolveC(8, 3) = 8! / (3! · 5!) = (8 · 7 · 6) / 6 = 56
  • CheckP(8,3)/3! = 336/6 = 56. ✓ Every combination corresponds to 3! = 6 permutations.
Answer: 56 advisory panels.
Example 8.6.3
A combined problem — resolving the opening question
  • ProblemTwelve students apply. Five are chosen for a committee. Two of the five are then designated chair and co-chair. How many total outcomes are possible?
  • ThinkStage 1: choose 5 from 12 — unordered, so combination. Stage 2: from those 5, assign chair and co-chair — ordered, so permutation. Use the product rule to combine both stages.
  • Solve Stage 1: C(12, 5) = (12 · 11 · 10 · 9 · 8) / 120 = 792 Stage 2: P(5, 2) = 5 · 4 = 20 Total: 792 · 20 = 15,840
Answer: 15,840 possible outcomes.
Sections 8.7 – 8.9
Binomial Coefficients, Pascal's Triangle, and the Binomial Theorem
Properties · Pascal's Identity · Triangle Patterns · Algebraic Expansion
Section 8.7

Binomial Coefficients

The combination count C(n, r) is called a binomial coefficient because it appears in the expansion of (x + y)ⁿ. Before exploring that connection in Section 8.9, it is worth understanding the properties of binomial coefficients on their own.

Key Properties of Binomial Coefficients

Boundary values: C(n, 0) = 1 and C(n, n) = 1

Choosing zero items can be done in exactly one way (choose nothing). Choosing all n items can also be done in exactly one way (choose everything).

Symmetry: C(n, r) = C(n, n − r)

Pascal's Identity: C(n, r) = C(n−1, r−1) + C(n−1, r)

To count the r-element subsets of an n-element set: separate into those that include a fixed element — C(n−1, r−1) subsets — and those that do not — C(n−1, r) subsets. Together they cover all r-element subsets.

Proof
Pascal's Identity: C(n, r) = C(n−1, r−1) + C(n−1, r) for 1 ≤ r ≤ n−1.
  • ThinkExpress both sides using the factorial formula and simplify algebraically.
  • Proof C(n−1, r−1) + C(n−1, r) = (n−1)! / [(r−1)!(n−r)!] + (n−1)! / [r!(n−1−r)!] Write both fractions with a common denominator of r!(n−r)!: = r·(n−1)! / [r!(n−r)!] + (n−r)·(n−1)! / [r!(n−r)!] = (n−1)! · [r + (n−r)] / [r!(n−r)!] = n! / [r!(n−r)!] = C(n, r)
  • CheckEvery algebraic step is valid. The common denominator was correctly identified and the numerators combined cleanly.
Conclusion: Pascal's Identity holds for all integers n ≥ 1 and 1 ≤ r ≤ n−1. □
Section 8.8

Pascal's Triangle

Pascal's Triangle is an infinite triangular array of numbers in which each entry is a binomial coefficient C(n, r), organized by row n and position r. Row 0 corresponds to n = 0. Each entry equals the sum of the two entries directly above it — precisely Pascal's Identity. The edges are always 1.

Row 01
Row 11    1
Row 21    2    1
Row 31    3    3    1
Row 41    4    6    4    1
Row 51    5    10    10    5    1
Row 61    6    15    20    15    6    1
Row 71    7    21    35    35    21    7    1
Diagram Instruction

Draw Pascal's Triangle to at least row 7. Label each row number on the left side. Draw light arrows from two adjacent entries in one row down to their sum in the next row, to illustrate Pascal's Identity directly.

Key Properties of Pascal's Triangle

Row sums: Sum of all entries in row n = 2ⁿ

This means an n-element set has exactly 2ⁿ subsets (including the empty set and the full set).

Alternating sums (for n ≥ 1): alternating sum of row n = 0

Diagonal patterns reveal triangular numbers, powers of 2, and Fibonacci-related structures studied in advanced combinatorics.

Example 8.8.1
Using Pascal's Triangle to find a binomial coefficient
  • ProblemUse Pascal's Triangle to compute C(6, 2).
  • ThinkGo to row 6, position 2 (counting from position 0 at the left). Read the value directly from the triangle.
  • SolveRow 6 reads: 1, 6, 15, 20, 15, 6, 1. Position 2 (the third entry) is 15.
  • CheckC(6, 2) = (6 · 5)/2 = 15. ✓
Answer: C(6, 2) = 15.
Section 8.9

The Binomial Theorem as an Algebraic Identity

The Binomial Theorem gives a formula for expanding (x + y)ⁿ for any non-negative integer n. This is a purely algebraic result — no calculus is required. When you expand (x + y)ⁿ = (x + y)(x + y)···(x + y), each term in the expansion is formed by choosing either x or y from each factor. A term x^(n−r) y^r is produced by choosing y from exactly r of the n factors. The number of ways to choose which r factors supply the y is exactly C(n, r).

The Binomial Theorem
(x + y)ⁿ = C(n,0)xⁿ + C(n,1)xⁿ⁻¹y + C(n,2)xⁿ⁻²y² + · · · + C(n,n)yⁿ

The coefficient of x^(n−r) y^r is C(n, r). The coefficients of row n of Pascal's Triangle give exactly the coefficients of (x + y)ⁿ.

PowerExpansion
(x + y)²x² + 2xy + y²
(x + y)³x³ + 3x²y + 3xy² + y³
(x + y)⁴x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴
Example 8.9.1
Expanding a binomial power
  • ProblemExpand (x + y)⁵.
  • ThinkUse row 5 of Pascal's Triangle: 1, 5, 10, 10, 5, 1.
  • Solve(x + y)⁵ = x⁵ + 5x⁴y + 10x³y² + 10x²y³ + 5xy⁴ + y⁵
Answer: x⁵ + 5x⁴y + 10x³y² + 10x²y³ + 5xy⁴ + y⁵
Example 8.9.2
Finding a specific term
  • ProblemWhat is the coefficient of x³y⁴ in the expansion of (x + y)⁷?
  • ThinkThe term x³y⁴ corresponds to r = 4 (since the power of y is r) and n = 7.
  • SolveC(7, 4) = C(7, 3) = (7 · 6 · 5) / 6 = 35
Answer: The coefficient of x³y⁴ is 35.
Example 8.9.3
Expanding with a constant factor
  • ProblemExpand (2a − b)³.
  • ThinkSubstitute x = 2a and y = −b into the Binomial Theorem with n = 3. The row 3 coefficients are 1, 3, 3, 1.
  • Solve (2a − b)³ = C(3,0)(2a)³ + C(3,1)(2a)²(−b) + C(3,2)(2a)(−b)² + C(3,3)(−b)³ = 8a³ + 3(4a²)(−b) + 3(2a)(b²) + (−b³) = 8a³ − 12a²b + 6ab² − b³
Answer: (2a − b)³ = 8a³ − 12a²b + 6ab² − b³
Tip

In (x + y)ⁿ, the power of y in each term increases from 0 to n, while the power of x decreases from n to 0. The two exponents always sum to n in every term. Use this to check your expansion term by term.

MGU Library Connection
  • Pascal's Triangle connects to number theory, combinatorics, probability, and algebra throughout the MGU Mathematics Library
  • The Binomial Theorem reappears in MGU Algebra II, Probability and Statistics, and Data Science Foundations
  • Binomial coefficients are central to the MGU Combinatorics Dictionary and Symbol Reference appendix
Sections 8.10 – 8.12
Discrete Probability and Expected Value
Sample Spaces · Events · Equally-Likely Outcomes · Complement Rule · Expected Value
Section 8.10

Counting-Based Probability

In a discrete probability setting, we work with a finite sample space where all outcomes are equally likely. A sample space S is the set of all possible outcomes of a random process. An event E is a subset of the sample space. When all outcomes are equally likely, the probability of event E is simply the ratio of favorable outcomes to total outcomes.

Equally-Likely Probability
P(E) = |E| / |S|

Where |E| is the number of outcomes in the event and |S| is the total number of outcomes. Probability satisfies 0 ≤ P(E) ≤ 1.

Complement rule: P(not E) = 1 − P(E)

Use the complement when the complementary event is easier to count than the event itself.

Example 8.10.1
Rolling a fair die
  • ProblemA fair six-sided die is rolled. What is the probability of rolling an even number?
  • ThinkThe sample space is S = {1, 2, 3, 4, 5, 6}. The event is E = {2, 4, 6}.
  • SolveP(E) = |E| / |S| = 3 / 6 = 1/2
Answer: The probability of rolling an even number is 1/2.
Example 8.10.2
Tossing three coins
  • ProblemThree fair coins are tossed. What is the probability of getting exactly two heads?
  • ThinkEach coin has two outcomes, so the sample space has 2³ = 8 equally likely outcomes.
  • Solve S = {HHH, HHT, HTH, THH, HTT, THT, TTH, TTT} E = {HHT, HTH, THH} → |E| = 3 P(E) = 3/8
Answer: The probability of exactly two heads is 3/8.
Example 8.10.3
Using the complement rule
  • ProblemA fair die is rolled three times. What is the probability that at least one roll is a six?
  • ThinkCounting "at least one six" directly requires adding several cases. The complement — "no sixes appear" — is much easier.
  • Solve Total outcomes: 6³ = 216 Outcomes with no six: 5³ = 125 P(at least one six) = 1 − 125/216 = 91/216 ≈ 0.421
Answer: The probability of at least one six is 91/216 ≈ 0.421.
Section 8.11

Probability With Combinations

Many probability problems require combinations to count both the favorable outcomes and the total outcomes. The general approach is to identify the event, count how many ways it can occur using combinations, divide by the total number of outcomes (also counted with combinations), and simplify the resulting fraction.

Example 8.11.1
Selecting a mixed committee
  • ProblemA committee of 4 is chosen at random from 6 men and 5 women. What is the probability that the committee consists of exactly 2 men and 2 women?
  • ThinkTotal outcomes: C(11, 4). Favorable outcomes: C(6, 2) ways to choose the men, times C(5, 2) ways to choose the women.
  • Solve |S| = C(11, 4) = (11 · 10 · 9 · 8) / 24 = 330 |E| = C(6, 2) · C(5, 2) = 15 · 10 = 150 P(E) = 150 / 330 = 5/11
  • Check150/330 reduces to 5/11 by dividing both by 30. ✓
Answer: The probability of exactly 2 men and 2 women is 5/11 ≈ 0.455.
Example 8.11.2
All hearts from a deck
  • ProblemA five-card hand is dealt from a standard 52-card deck. What is the probability that all five cards are hearts?
  • ThinkThere are 13 hearts in a deck. Total five-card hands: C(52, 5). All-hearts hands: C(13, 5).
  • Solve |S| = C(52, 5) = 2,598,960 |E| = C(13, 5) = (13 · 12 · 11 · 10 · 9) / 120 = 1,287 P(E) = 1,287 / 2,598,960 ≈ 0.000495
Answer: The probability is approximately 0.000495, or about 5 in 10,000.
Example 8.11.3
At least one from a subgroup
  • ProblemFrom a group of 10 students (4 seniors and 6 juniors), 3 are chosen at random. What is the probability that at least one senior is chosen?
  • ThinkUse the complement: calculate the probability that no seniors are chosen, then subtract from 1.
  • Solve |S| = C(10, 3) = 120 |complement| = C(6, 3) = 20 (all three are juniors) P(at least one senior) = 1 − 20/120 = 1 − 1/6 = 5/6
Answer: The probability that at least one senior is chosen is 5/6 ≈ 0.833.
Section 8.12

Expected Value in Finite Settings

The expected value of a random quantity is the average outcome you would expect over many repetitions of a random process. In a finite setting with equally likely outcomes, it is computed by weighting each possible outcome by its probability and summing. The expected value does not have to be a value the process can actually produce — it represents the long-run average.

Definition — Expected Value
E = v₁p₁ + v₂p₂ + · · · + vₖpₖ

Where v₁, v₂, …, vₖ are the possible outcomes and p₁, p₂, …, pₖ are their probabilities (which must sum to 1).

Example 8.12.1
Expected value of a die roll
  • ProblemWhat is the expected value of a single roll of a fair six-sided die?
  • ThinkEach face (1 through 6) has probability 1/6.
  • Solve E = 1·(1/6) + 2·(1/6) + 3·(1/6) + 4·(1/6) + 5·(1/6) + 6·(1/6) = 21/6 = 3.5
Answer: The expected value is 3.5. The die never shows 3.5, but over many rolls the average converges toward 3.5.
Example 8.12.2
Expected value of a simple game
  • ProblemA game costs $2 to play. Draw one card from a standard deck. Win $10 for an ace, $4 for a face card, $0 otherwise. What is the expected net gain per game?
  • ThinkCalculate the probability and net gain (after subtracting the $2 cost) for each case.
  • Solve Ace: P = 4/52 = 1/13, net gain = $10 − $2 = +$8 Face: P = 12/52 = 3/13, net gain = $4 − $2 = +$2 Other: P = 36/52 = 9/13, net gain = $0 − $2 = −$2 E = 8·(1/13) + 2·(3/13) + (−2)·(9/13) = (8 + 6 − 18) / 13 = −4/13 ≈ −$0.31
Answer: The expected net gain is approximately −$0.31 per game. The player loses about 31 cents per game on average over many plays.
Note on Scope

A full treatment of expected value, variance, and distributions belongs to the Probability and Statistics course in the MGU Mathematics pathway. This section introduces the concept so students understand what expected value measures before encountering it in later courses.

Sections 8.13 – 8.14
Common Mistakes and the Road Ahead
Seven Recurring Errors · Corrections · Bridge to Chapter 9
Section 8.13

Common Permutation and Combination Mistakes

Mistake 1 — Applying the Wrong Formula
Using P(10, 5) = 30,240 to count five-person committees from a group of ten.

This overcounts by a factor of 5! = 120. A committee has no internal order. The correct answer is C(10, 5) = 252. Always ask whether order matters before choosing the formula.

Mistake 2 — Forgetting the r! in the Denominator
C(n, r) = n! / (n−r)! (stopping at P(n, r))

The combination formula requires both r! and (n−r)! in the denominator: C(n, r) = n! / [r! · (n−r)!]. Stopping early gives the permutation count, not the combination count.

Mistake 3 — Confusing Repetition Rules
Applying n^r when items cannot be reused, or P(n,r) when repetition is allowed.

Check whether the same item can appear more than once. If yes, use n^r. If no, use P(n,r) or C(n,r) as appropriate.

Mistake 4 — Miscounting the Sample Space
Using an incorrect value for |S|, for instance by computing only partial outcomes or double-counting.

Define the sample space carefully before computing any probability. Make sure all outcomes are accounted for and that they are all equally likely.

Mistake 5 — Setting 0! = 0
0! = 0, so P(n, n) = n! / 0! is undefined.

0! = 1 by definition. This is required for the permutation and combination formulas to work at their boundary values. Memorize it and apply it without hesitation.

Mistake 6 — Treating Multi-Stage Problems as Single Stages
Trying to use one formula for a problem that has two or more distinct stages (e.g., choosing a committee and then assigning roles within it).

Break multi-stage problems into stages. Apply the correct formula at each stage. Use the product rule to combine the counts from all stages.

Mistake 7 — Misapplying Pascal's Identity
C(n, r) = C(n, r−1) + C(n, r) or other incorrect form of Pascal's Identity.

Pascal's Identity reduces the upper index by 1: C(n, r) = C(n−1, r−1) + C(n−1, r). Both terms on the right side use n−1, not n.

Section 8.14

Preparing for Advanced Combinatorics

Chapter 8 has developed the core tools for counting arrangements and selections. Chapter 9 extends this foundation into more sophisticated territory. The Pigeonhole Principle guarantees that if more objects are placed into fewer containers than objects, some container holds more than one. Combinations with repetition count selections where items may be chosen more than once, using the elegant stars-and-bars model. Recurrence relations define sequences where each term depends on previous ones — a structure that connects combinatorics to algorithm analysis and the mathematics of recursion. Combinatorial proofs prove identities by counting the same set two different ways, turning equations into statements about structure.

These tools address problems that go beyond what formulas alone can handle. They require flexible reasoning and structural insight. Chapter 9 will show how combinatorics grows from a set of formulas into a way of seeing structure in finite systems too large to enumerate manually.

MGU Library Connection — Bridge to Computing
  • Cryptography: Key spaces of size 2¹²⁸ mean brute-force attacks are computationally infeasible — Chapter 8 tools explain why
  • Machine Learning: Expected value underlies decision trees, Bayesian methods, and reinforcement learning
  • Algorithm Design: Knowing a problem has C(n, k) configurations determines whether exhaustive search is practical
  • Data Science: Feature selection from 50 candidate variables gives C(50, 10) = 10,272,278,170 possibilities — enumeration is impossible
  • See the MGU Algorithms and Combinatorics library pages for extended applications in each of these areas
Chapter 8 — Back Matter

Chapter Summary

Key Terms Review

arrangement
An ordered selection of items. Two arrangements are different if the same items appear in a different order.
selection
An unordered group of items. Two selections are the same if they contain exactly the same items.
factorial (n!)
The product n · (n−1) · (n−2) · · · 1, with 0! = 1 by convention. The foundation for permutation and combination formulas.
permutation
A counting formula for ordered arrangements. P(n, r) = n!/(n−r)! counts ordered selections of r from n without repetition.
combination
A counting formula for unordered selections. C(n, r) = n!/[r!(n−r)!] counts the number of r-element subsets of an n-element set.
binomial coefficient
The quantity C(n, r), also written "n choose r." It appears as the coefficient of x^(n−r)y^r in the expansion of (x+y)ⁿ.
Pascal's Identity
C(n, r) = C(n−1, r−1) + C(n−1, r). Each binomial coefficient equals the sum of the two coefficients directly above it in Pascal's Triangle.
Pascal's Triangle
The triangular array of binomial coefficients organized by row n. Row n sums to 2ⁿ; each entry is the sum of the two entries above it.
Binomial Theorem
The algebraic identity (x+y)ⁿ = Σ C(n,r) x^(n−r) y^r. Gives the coefficients for expanding any power of a binomial.
sample space
The set S of all possible outcomes of a random process.
event
A subset E of the sample space. The probability of E is P(E) = |E|/|S| when outcomes are equally likely.
complement
The event "not E," written E̅. P(E̅) = 1 − P(E). Useful when the complement is easier to count than the event itself.
discrete probability
Probability in a finite, equally-likely setting. Computed by counting favorable and total outcomes. No calculus or density functions required.
expected value
E = Σ vᵢpᵢ. The probability-weighted average outcome over many repetitions. May not equal any actual outcome value.
equally-likely outcomes
All outcomes in the sample space have the same probability. This condition must hold for the formula P(E) = |E|/|S| to apply.
multinomial count
The formula n!/(n₁!·n₂!···nₖ!) for counting distinct arrangements when n items contain groups of identical elements of sizes n₁, …, nₖ.
symmetry of C(n,r)
The property C(n, r) = C(n, n−r). Choosing r items to include equals choosing n−r items to exclude.

Concept Review Questions

  1. What is the difference between an arrangement and a selection? Give one example of each.
  2. Why is 0! = 1, and where does this matter in counting formulas?
  3. Explain in words why P(n, r) = n!/(n−r)!. Where does the (n−r)! come from?
  4. Explain in words why C(n, r) = P(n, r)/r!. What are we dividing out, and why?
  5. State Pascal's Identity and describe its combinatorial meaning: what does it say about selecting a fixed element?
  6. How do the row sums of Pascal's Triangle relate to the number of subsets of a set?
  7. Explain why C(n, r) = C(n, n−r). Give a combinatorial interpretation.
  8. What is the Binomial Theorem, and why do binomial coefficients appear in the expansion of (x+y)ⁿ?
  9. What does it mean for outcomes to be "equally likely"? Why does this condition matter for the probability formula?
  10. When is it useful to use the complement rule in a probability calculation? Give a situation where the complement is clearly easier to count than the event itself.
Skill Practice APermutations
  1. Compute P(6, 2)
  2. Compute P(9, 3)
  3. Compute P(10, 4)
  4. Compute P(7, 7)
  5. 10 members: choose president, VP, treasurer
  6. 4-letter sequences, no repeated letters, 26-letter alphabet
  7. 5-digit numbers from digits 1–9, no repeats
  8. Arrange 8 distinct books on a shelf
  9. Arrangements of letters in ALGEBRA
  10. Arrangements of letters in MISSISSIPPI
  11. Arrangements of letters in DISCRETE
  12. 10 runners: how many gold/silver/bronze assignments?
Skill Practice BCombinations
  1. Compute C(8, 3)
  2. Compute C(10, 4)
  3. Compute C(12, 5)
  4. Compute C(7, 7)
  5. 15 employees: three-person project teams
  6. 52 cards: hands of 7 cards
  7. 12 toppings: three-topping pizzas
  8. Five-element subsets of a 9-element set
  9. 20 applicants: select 4 scholarship recipients
  10. Confirm C(9,4) = C(9,5) by computing both
  11. Use Pascal's Identity to compute C(8,3) from row 7 values
  12. How many subsets does a 6-element set have? Verify using row 6.
Skill Practice CBinomial Coefficients and Pascal's Triangle
  1. Write rows 0 through 8 of Pascal's Triangle
  2. Verify row 5 matches C(5,r) for r = 0 to 5
  3. Expand (x + y)⁶
  4. Expand (a − b)⁴
  5. Expand (2x + 3)³
  6. Expand (x − 2y)⁵
  7. Find coefficient of x⁴y³ in (x + y)⁷
  8. Find coefficient of a²b⁵ in (a + b)⁷
  9. Show that row 6 sums to 64 = 2⁶
  10. Find the term containing x³ in (x + 2)⁵
Skill Practice DDiscrete Probability
  1. Roll a die: P(rolling a 4)?
  2. Roll a die: P(prime number)?
  3. Roll a die: P(greater than 4)?
  4. Two dice: P(sum = 7)?
  5. Bag: 3 red, 5 blue, 2 green — P(red)?
  6. Bag: 3 red, 5 blue, 2 green — P(not blue)?
  7. Three coins: P(exactly 1 head)?
  8. Three coins: P(at least 1 tail)?
  9. C(3 from 5 men and 4 women): P(exactly 2 women)?
  10. 5-card hand: P(exactly 3 aces)?
  11. Select 4 from 12 (7 seniors, 5 juniors): P(at least one junior)?
  12. Game pays $5 with P = 1/5, $0 otherwise, costs $1: find expected net gain.

Word Problems and Applications

For each problem, identify the type of counting involved and justify your formula choice before computing.

  1. Passwords. A website requires passwords of exactly 8 characters. Characters may be uppercase letters (26), lowercase letters (26), or digits (10). How many passwords are possible (a) with repetition allowed, (b) with no character repeated?
  2. Scheduling. A teacher schedules 6 different class periods in a day. How many orderings of the 6 periods are possible?
  3. Tournament. Eight teams play in a tournament. How many ways can first, second, and third place be determined?
  4. Task Force. A company has 12 engineers. (a) How many five-person task forces are possible? (b) If one specific engineer must be included, how many five-person task forces are possible?
  5. Quality Control. A batch contains 20 items, of which 3 are defective. A sample of 4 is selected at random. Find the probability that the sample contains (a) no defective items, (b) exactly 1 defective item, (c) at least 1 defective item.
  6. Lottery. A lottery draws 6 numbers from 1 to 49 without repetition (order does not matter). How many possible outcomes are there? What is the probability of matching all 6 numbers?
  7. Card Game. From a 52-card deck, 5 cards are dealt. Find the probability that the hand contains (a) exactly 2 hearts, (b) at least one ace.
  8. Binary Strings. How many binary strings of length 10 contain exactly 4 ones? What fraction of all binary strings of length 10 contain exactly 4 ones?

Error Analysis

Each problem shows a student's work containing an error. Identify the error and write the correct solution.

Problem 1
A student counts committees of 3 from 8 people as: P(8, 3) = 8·7·6 = 336.

What error was made? What is the correct answer and why?

Problem 2
A student expands (x+y)⁴ as: x⁴ + 4x³y + 4x²y² + 4xy³ + y⁴

Identify the error in the coefficients. Write the correct expansion.

Problem 3
A student counts distinct arrangements of NOON as 4! = 24.

What error was made? Identify the repeated letters and compute the correct answer.

Problem 4
Drawing 2 cards from 5 red and 3 blue: P(2 red) = (5/8) · (5/8) = 25/64.

Explain the conceptual error. Compute the correct probability using combinations, assuming sampling without replacement.

Problem 5
0! = 0, so C(5, 0) = 5! / (0! · 5!) is undefined.

Correct this error. State the true value of 0! and explain why C(5, 0) = 1.

Chapter 8 Checkpoint

Chapter 8 Checkpoint
Complete without assistance — assesses all key skills and concepts from Chapter 8
Section 1 — Vocabulary and Concepts
  1. Explain the difference between a permutation and a combination. Give one example of a situation that calls for each.
  2. State Pascal's Identity. Describe what it means in terms of counting subsets that either include or exclude a fixed element.
  3. Explain why the Binomial Theorem produces binomial coefficients as the coefficients of (x + y)ⁿ.
Section 2 — Permutation and Combination Skills
  1. Compute P(7, 3) and C(7, 3). State what each counts.
  2. How many distinct 5-letter sequences (no repeated letters) can be formed from a 26-letter alphabet?
  3. A committee of 5 is chosen from 9 candidates. Two of the five are then designated co-chairs. How many outcomes are possible?
  4. How many distinct arrangements are there of the letters in PARALLEL?
Section 3 — Binomial Theorem
  1. Expand (x + y)⁵ using the Binomial Theorem. Verify that the coefficients match row 5 of Pascal's Triangle.
  2. Find the coefficient of x²y⁴ in the expansion of (x + y)⁶.
  3. Expand (3a − b)³.
Section 4 — Discrete Probability
  1. From a class of 8 males and 6 females, 4 students are selected at random. Find: (a) the probability all four are male, (b) the probability exactly 2 are female.
  2. A game costs $3 to play. Roll a die: win $15 if you roll a 6, $6 if you roll a 5, $0 otherwise. Compute the expected net gain. Is this a favorable game for the player?
Section 5 — Proof
  1. Prove Pascal's Identity algebraically: C(n, r) = C(n−1, r−1) + C(n−1, r). Show every step.
Section 6 — Error Analysis
  1. A student simplifies C(5, 0) and gets 0 because "choosing nothing means 0 ways." Identify the error and state the correct answer.
  2. A student computes the probability of getting exactly 2 aces in a 5-card hand as 4/52 · 3/51 · 48/50 · 47/49 · 46/48. What is wrong with this approach? Describe the correct method.
Looking Ahead
Chapter 9: Advanced Counting and Combinatorial Reasoning

Chapter 8 gave you the core tools for counting arrangements and selections. Chapter 9 will extend this foundation into more powerful territory. You will study the Pigeonhole Principle, which guarantees that in certain situations some container must hold more than one item — a deceptively simple idea with surprising mathematical power. You will learn to count selections where repetition is allowed using the stars-and-bars method, and to count the integer solutions to equations of the form x₁ + x₂ + x₃ = n. You will also encounter recurrence relations, which define sequences by their own past behavior, and combinatorial proofs, which prove identities by showing two counting processes produce the same answer. Together, these tools show how combinatorics becomes a way of reasoning about structure in finite systems far too large to enumerate by listing.

MGU Library Connection
  • Counting Rules Formula Sheet — Appendix I of this textbook
  • Permutation and Combination Reference — Appendix J of this textbook
  • Discrete Mathematics: Chapter 7 (Counting Principles) — prerequisite content
  • Probability and Statistics — MGU Mathematics Series: extends discrete probability to continuous distributions and inference
  • MGU Dictionary entries: permutation, combination, factorial, binomial coefficient, sample space, event, expected value
  • MGU Algorithms Library: counting arguments applied to algorithm complexity analysis
  • MGU Cryptography Pages: key space size and brute-force attack resistance