Counting Techniques

A smartphone lock screen with a 6-digit PIN has 1,000,000 possible codes. A 6-letter password from the 26 letters of the alphabet — no repeats — has 165,765,600 possibilities. Why the enormous difference?

In PR-1, you counted outcomes by listing them. That works for small sample spaces. This lesson gives you three systematic methods that handle problems too large to list — and they plug directly into the probability formula you already know.

In PR-1, — but you found and by listing. Today you build the machinery to count and without listing a single outcome.

After this lesson, you will be able to:

Apply the Fundamental Counting Principle to count outcomes for multi-stage processes.
Compute factorials and use them in the permutation and combination formulas.
Calculate permutations and combinations for problems with ordered and unordered selections.
Identify which counting method applies and use it to compute probabilities over equally-likely sample spaces.

What you need from PR-1

Equally-likely outcomes and (PR-1, Core Concepts C1–C2): Every counting technique in this lesson feeds directly into this formula. We will count and systematically — but the formula connecting them to probability is the one you already know.
Reading a sample space (PR-1, Core Concepts C2–C3): You listed sample spaces for small experiments. Today we replace that listing with formulas. Understanding what a sample space is — and why it must be complete — remains essential.
The complement rule (PR-1, Core Concepts C5): . In Section 9 (Challenge Problems), you will use the complement to avoid counting a large favorable set directly. The rule is the same; only the counting method is new.

Retrieval Checkpoint

A bag contains 5 red marbles and 3 blue marbles. One marble is drawn at random. What is ?

Also confirm you can recall:

I can identify n(S), the total number of equally-likely outcomes in a sample space. I know that

and can apply the complement rule. I understand that

requires all outcomes to be equally likely.

Success Factor:

From listing to counting. In PR-1, finding meant listing outcomes or using a simple sample space. Today we unlock three methods — the Fundamental Counting Principle, permutations, and combinations — that count thousands or millions of outcomes without listing a single one, then feed those counts directly into .

Navigation Guide — 6 Concepts

C1: Fundamental Counting Principle — “How many complete sequences are possible?” Use for multi-stage processes with independent choices.
C2: Factorials — the building block for permutation and combination formulas.
C3: Permutations — “How many ordered arrangements?” Use when the order of selection produces a different outcome.
C4: Combinations — “How many unordered selections?” Use when two selections with the same objects in different order count the same.
C5: Permutation vs. Combination decision — the single most important judgment call in this lesson.
C6: Counting-based probability — feeding counting results back into .

C1 — Fundamental Counting Principle

Imagine a restaurant with 3 starters, 5 main courses, and 4 desserts. How many distinct three-course meals can you order?

You have 3 choices for the starter. For each starter, 5 choices for the main. For each (starter, main) pair, 4 choices for dessert. Total meals:

This is the Fundamental Counting Principle (FCP): multiply the number of choices at each independent stage.

Fundamental Counting Principle

If a sequential process has independent stages — with choices at stage 1, choices at stage 2, …, choices at stage — the total number of complete sequences is:

Key requirement: The number of choices at each stage must not depend on the choices made at earlier stages.

Mini-example (2 stages): A student can take a morning class (4 options) and an afternoon class (6 options). How many distinct (morning, afternoon) pairs are possible?

pairs. Each morning choice pairs with each of the 6 afternoon options independently.

A tree diagram makes the multiplication visible. With 2 morning choices and 3 afternoon choices, every Stage-1 branch fans into 3 Stage-2 branches — giving complete paths:

Each Stage-1 branch fans into 3 Stage-2 branches — total is

, not

Adjust the choices at each stage and watch the tree grow multiplicatively. Try setting Stage 1 to 4 and Stage 2 to 3 — notice how every Stage-1 branch fans into exactly 3 Stage-2 branches, giving distinct paths. Then switch on No repeats to see what happens when each chosen item leaves the pool: every stage has one fewer choice, and the stages stop being independent — exactly the situation the trap below warns about.

Stage 1 =

Stage 2 =

Running product

When stages are NOT independent, the FCP does not directly apply. Suppose a PIN uses 4 distinct digits (no repeats). Stage 1: 10 choices. Stage 2: only 9 (one digit is used). Stage 3: 8. Stage 4: 7. Total = , not 10⁴ = 10000. The shrinking number of choices at each stage signals that this is a permutation problem — covered in C3.

In standard terminology: selecting with repetition means choices are independent (every stage has the same count). Selecting without repetition (also called without replacement) means earlier choices reduce later options, as in the PIN example above.

C2 — Factorials

How many ways can you arrange 3 books (A, B, C) in a row?

Position 1: 3 choices
Position 2: 2 remaining choices
Position 3: 1 remaining choice

Total: . List them to verify: ABC, ACB, BAC, BCA, CAB, CBA — exactly 6.

This product occurs so often it gets its own symbol.

Factorial

For any positive integer :

Convention: .

Factorials count the number of ways to arrange all distinct objects in a sequence. They grow rapidly: 5! = 120, , .

Why : The permutation formula (C3) requires to equal — the number of ways to arrange all objects. This forces . Also: there is exactly one way to arrange zero objects (do nothing).

See the cancellation: Expand into individual multiplied terms. Click “Show cancellation” to watch the denominator strike through the matching tail of the numerator, leaving only the highlighted terms — that is exactly how the permutation formula works.

n =

r =

"" is the most common factorial error. It makes undefined or zero — but there is exactly one way to choose nothing from a set (the empty selection). Always: .

C3 — Permutations: Ordered Arrangements

In a club of 8 members, how many ways can we elect a president, vice-president, and secretary (3 distinct roles)?

Apply the FCP with dependent stages: 8 choices for president, 7 for VP (one member used), 6 for secretary.

This is — a permutation. We can write this more compactly using factorials:

Permutation

A permutation selects objects from distinct objects and arranges them in order. We write :

Use a permutation when order matters — a different arrangement of the same objects is a different outcome.

Special case: (arranging all objects).

Derivation from FCP: For position 1, choices. Position 2: . Position 3: . … Position : . Product = . Multiplying numerator and denominator by closes the form:

Use only when order changes the outcome. If you are selecting a 3-person team from 8 (not assigning roles), the order of selection does not matter — {Ann, Bob, Carl} and {Carl, Ann, Bob} are the same team. That is a combination (C4). Using ₈P₃ = 336 when the answer is ₈C₃ = 56 overcounts by .

Build a permutation: Click an object from the pool to place it in the next position. Watch the choice count above each slot decrease as the pool shrinks — that shrinking count is exactly where the formula comes from.

Available pool — click to place

Your arrangement

Running product

C4 — Combinations: Unordered Selections

From 8 candidates, how many 3-person committees can be formed (no roles assigned)?

Each group of 3 candidates, regardless of the order we list their names, is the same committee. The permutation count of 336 overcounts each committee: every committee of 3 people can be arranged in orders — (A,B,C), (A,C,B), (B,A,C), (B,C,A), (C,A,B), (C,B,A) — all referring to the same committee.

Combination

A combination selects objects from distinct objects without regard to order. We write or :

Use a combination when order does not matter — two selections with the same objects in a different order count as the same outcome.

Properties:

(exactly one way to choose nothing, or choose everything)
Symmetry: (choosing to include is the same as choosing to exclude)

Symmetry as a shortcut: . When is large, use the symmetry to work with the smaller number.

Forward pointer to PR-5: In PR-5 (Binomial Distribution), the combination formula appears inside the binomial probability: . The counts the number of ways exactly successes can occur in trials — the formula you just learned is the key ingredient.

See the symmetry: The same split of five objects can be read two ways. Flip the reading below — choosing 2 to include is choosing 3 to exclude, so the two counts must be equal.

Read the split as:

{A, B} go in → C(5,2) = 10 ways to choose the 2 included.

Explore permutations and combinations interactively:

Select a value of below. The left panel shows all ordered arrangements; the right panel shows all unordered selections. Matching tints mark the orderings that contain the same objects — switch the group view to Grouped to watch them collapse into a single combination when order is ignored.

Ordered — ₄P_r 12

12 ÷ 2! = 6

Unordered — ₄C_r 6

Group view:

C5 — Permutation vs. Combination: The Decision

The core question is: does changing the order of the selected items give a different outcome?

Yes → Permutation. “Being first is different from being second.”
No → Combination. “Only the membership of the group matters.”

Scenario	Order matters?	Method
Elect president, VP, secretary from 12 members	Yes — different roles	Permutation
Form a 3-person committee from 12 members	No — same committee regardless of listing order	Combination
Arrange 5 songs on a playlist	Yes — different order is a different playlist	Permutation
Choose 3 toppings from a menu of 8	No — same toppings in any order	Combination

Signal words:

→ Permutation: “arrangement,” “ranking,” “ordered list,” “schedule,” “sequence,” “1st, 2nd, 3rd,” “code or password (when the problem states that order matters)”
→ Combination: “group,” “team,” “committee,” “set,” “selection,” “sample,” “subset”

“Combination lock” is a misnomer. A lock where 3-7-4 is different from 4-7-3 is actually a permutation lock — order matters. The everyday English use of “combination” does not match the mathematical meaning. In mathematics: “combination” always means unordered selection.

Use this flowchart to classify any counting problem. Expand the examples to see the formula applied to the scenarios from this lesson.

First: can the same item be chosen again (repetition allowed)?
YES → use the FCP (multiply choices per stage). NO → continue ↓ to the order question.

Does swapping two selected items
produce a different outcome?

Permutation

_nP_r = n! / (n − r)!

arrangement ranking ordered list schedule code (no repeats)

Electing a president, VP, and secretary from 12 — which branch? Check

Swapping president and VP gives a different outcome — order matters, so Permutation.
₁₂P₃ = 12 × 11 × 10 = 1320

Combination

C(n, r) = n! / [r! · (n − r)!]

group team committee set selection

Choosing a 3-person committee from 12 — which branch? Check

{Ann, Bob, Carl} and {Carl, Ann, Bob} are the same committee — order doesn't matter, so Combination.
C(12, 3) = 12! / (3! · 9!) = 220
Note: 220 = 1320 ÷ 3! — the same 12 · 11 · 10 selections, with each group's 6 orderings collapsed into one.

"Combination lock" is a misnomer — it is actually a permutation lock, because 3‑7‑4 ≠ 4‑7‑3.

C6 — Counting-Based Probability

When all outcomes in a sample space are equally likely, . Counting techniques give us both and when manual enumeration is not feasible.

The formula from PR-1 still applies — we just use counting tools to find the numbers:

Counting-Based Probability

When all outcomes are equally likely:

Both numerator and denominator are counted using the same method (FCP, permutation, or combination). The counting method must be consistent — never mix permutations in the numerator with combinations in the denominator.

End-to-end example: From a class of 20 students (8 who are athletes, 12 who are not), 3 are chosen at random. Find .

Total outcomes: equally-likely committees.

Favorable outcomes: All 3 from the 8 athletes: .

Explore all four outcomes: The bar below divides all 1,140 equally-likely committees by the number of athletes included. Click any segment to see the combination formula and exact probability.

Click a segment to see the probability formula

Counting by complement. When the favorable set is large but its complement is small, it is easier to count what you do not want and subtract: . For example, is easier as than by summing three direct cases. This strategy becomes essential whenever a problem uses “at least one” or “at least ” phrasing — you will use it in the Challenge Problems (Section 9) and again in PR-5.

The bar below makes the strategy visible: the “0 athletes” slice is the only thing you have to count — everything else is “at least one,” no case-by-case work required.

The opening hook — resolved. A 6-digit PIN uses 10 digits with repetition allowed: each position independently has 10 choices, so the FCP gives . A 6-letter password with no repeated letters selects without replacement — a permutation: . The enormous difference comes down to one design decision: repetition allowed (independent stages) vs. not (dependent stages).

Example 1 — Fully Worked: FCP and Permutation

Part A: A restaurant has 4 appetizers and 6 main courses. How many distinct (appetizer, main course) pairs are possible?

Part B: In how many ways can a president, vice-president, and secretary be elected from a club of 12 members?

Part A — FCP:

I see two independent stages: choose an appetizer (4 options), then choose a main course (6 options). The number of main options does not depend on which appetizer I pick — the stages are independent. Apply FCP directly.

Total pairs = .

Part B — Permutation:

First I ask: does order matter? Yes — being elected president is a different outcome from being elected vice-president, even if the same person is chosen. The three roles are distinct. So I use a permutation.

members, positions. I write out the product from the FCP derivation to check my answer:

Using the formula: ✓

I pause to check: is 1320 reasonable? There are 12 choices for president, then 11 for VP, then 10 for secretary — . Confirmed.

Example 2 — Prediction Checkpoint: Combinations

A committee of 4 people is chosen from 10 candidates. No roles are assigned — the 4 members are equal.

Before computing: Predict whether is closer to 200 or to 5040. Write your reasoning, then check below.

Compute:

The answer is close to 200 — much smaller than 5040 (which is , the ordered version). Dividing by removes all the overcounting from treating different orderings of the same 4 people as distinct.

Symmetry check: . Verify: ✓. Choosing 4 to include is equivalent to choosing 6 to exclude.

Example 3 — Details/Summary: Counting-Based Probability

A class of 30 students contains 12 who play varsity sports and 18 who do not. Five students are randomly selected to present projects. What is the probability that exactly 3 of the 5 selected are athletes?

Show Solution

Step 1 — Identify the method. Order of selection doesn’t matter (3 athletes chosen from 12, 2 non-athletes chosen from 18, for a total committee of 5). Use combinations throughout.

Step 2 — Count total outcomes:

Step 3 — Count favorable outcomes: Choose 3 athletes from 12, AND 2 non-athletes from 18. The two choices are independent, so multiply:

Step 4 — Compute the probability:

Check the method consistency: Both numerator and denominator used combinations — appropriate since we’re forming an unordered group.

Example 4 — Find the Error

A student is asked: “In how many ways can a 4-person project team be formed from 9 students?” The student writes:

Student’s work:

“The team needs 4 people. The order in which we pick them gives the team its structure, so I should use a permutation."

"There are 3024 possible teams.”

Identify and correct the error:

The error is using a permutation when the problem asks for a team (unordered group). A project team has no internal ranking — {Ann, Bob, Carl, Dana} and {Dana, Carl, Bob, Ann} are the same team. The permutation count of 3024 treats every ordering of the same 4 people as a separate team, overcounting each team by .

Correct calculation:

There are 126 possible teams — exactly , confirming the overcounting factor.

Key signal missed: The word “team” signals an unordered selection. Had the problem asked for a president, secretary, treasurer, and recorder, a permutation would be correct.

Problem 1 — Fundamental Counting Principle

Apply the FCP to count the total number of outcomes for a multi-stage process.

Problem 2 — Permutation Calculation

Given a scenario where order matters, compute the permutation.

Problem 3 — Combination Calculation and Symmetry

Compute and verify the symmetry property .

Problem 4 — Perm vs. Combo Decision and Counting Probability

From a class with a subgroup who share a trait, some students are randomly selected to give presentations. Work through the full decision-and-probability pipeline: classify the problem, count the total, count the favorable outcomes, then compute the probability.

Problem 5 — Factorials

Compute the number of ways to arrange all of a set of distinct objects.

Problem 1 — FCP Probability

Count total and favorable outcomes using the FCP, then compute the probability.

Problem 2 — Permutation vs. Combination Classification

Classify each scenario and compute the result.

9 books are available; 4 are chosen for an ordered reading list (the order matters — book 1 is read first, book 4 last).