Unit 1, Lesson 1: Counting Principles, Permutations, Combinations

Section 1 of 7: Notes/How to use the lesson

This lesson is split into 7 sections. Work them in order. Each solutions section is a gate: do not open it until you have finished every problem in the section before it.

Section 1. Notes. Read straight through, including all four worked examples. Do not skim the examples. They are where the technique gets shown, and every problem below is built on one of them. Budget 30 minutes.

Section 2. Part A problems. Five warm-ups at the difficulty of AMC 12 questions 1 to 10. Target 2 minutes each. Do all five before opening Section 3.

Section 3. Part A solutions. Check all five, then diagnose every miss using the list at the bottom of that file.

Section 4. Part B problems. Five harder problems at the difficulty of AMC 12 questions 13 to 22. Target 5 minutes each. Some will not fall in 5 minutes. That is the point. Write down where you got stuck. Do all five before opening Section 5.

Section 5. Part B solutions. Check and diagnose.

Section 6. Part C problems. Five real past AMC problems. Set a timer for 25 minutes, close your notes, and treat it like the contest. No calculator, no restarting, no looking anything up.

Section 7. Part C solutions. Check and diagnose.

Total working time is roughly 2 hours, and it does not have to be one sitting. A good split is Sections 1 to 3 on one day and 4 to 7 on the next.

SECTION 1: NOTES

1.1 The two basic rules

Product rule. If a process consists of k independent stages with n₁, n₂, ..., nₖ options respectively, the number of outcomes is n₁ n₂ ... nₖ.

Sum rule. If a set of outcomes splits into disjoint cases with n₁, n₂, ..., nₖ outcomes, the total is n₁ + n₂ + ... + nₖ.

Why. The product rule is a tree: each of the n₁ first-stage branches carries a full copy of the n₂ second-stage branches, and so on. The sum rule is the size of a disjoint union. The word "and" across stages signals multiplication; "or" across mutually exclusive cases signals addition.

The word "independent" means the count at each stage is fixed, not that the choices are unrelated. Arranging 4 letters from 6 distinct letters is 6 · 5 · 4 · 3: the later stages depend on earlier ones, but the number of options at each stage does not.

1.2 Permutations

The number of ways to arrange k objects chosen from n distinct objects, order mattering:

P(n,k) = n(n − 1)(n − 2)...(n − k+1) = n!/((n − k)!)

Why. Fill k slots left to right: n choices, then n − 1, down to n − k+1.

Special case k=n: there are n! arrangements of n distinct objects in a row.

1.3 Combinations

The number of ways to choose k objects from n distinct objects, order not mattering:

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

Why. Every unordered k-subset corresponds to exactly k! ordered selections, so divide the ordered count by k!. This is the division principle and it is the single most important idea in the lesson.

Useful facts:

C(n, k) = C(n, n − k), C(n, 0)=C(n, n)=1, C(n, 1)=n, C(n, 2)=(n(n − 1))/2

1.4 The division principle in general

If a counting method counts each valid object exactly d times, divide by d. Three standard instances:

Multiset permutations. Arrangements of n objects where n₁ are identical of type 1, n₂ of type 2, …:

n!/(n₁! n₂!... nᵣ!) Why. Treat all objects as distinct (n! ways), then note that permuting the nᵢ identical copies of type i among themselves (nᵢ! ways) produces the same visible arrangement.

Circular arrangements. n distinct objects around a circle, rotations considered the same: (n − 1)!. Why. Each circular arrangement corresponds to n linear arrangements (one per starting point), so n!/n = (n − 1)!. Equivalently: fix one object's position to kill the rotational symmetry, then arrange the other n − 1 freely. If reflections are also identified (bracelets, necklaces), divide by 2 more, but only when n ≥ 3.

Unlabeled groups. Splitting n distinct objects into g groups of equal size m where the groups have no names:

n!/((m!)ᵍ · g!) The g! is the step everyone forgets.

1.5 Two structural techniques

Handle the restriction first. If one slot is constrained, fill it before the free slots. Filling free slots first makes the constrained count depend on earlier choices and forces casework.

Gap method (non-adjacency). To place k objects among n others so that no two of the k are adjacent: arrange the n others first, creating n+1 gaps, then choose k of those gaps. Number of gap choices: C(n+1, k).

Worked examples

Example 1: restriction first How many 4-digit PINs use only the digits 1–9, repeat no digit, and begin with an odd digit?

The constrained slot is the first one, so fill it first. Odd digits available: 1,3,5,7,9, five choices.

The remaining three slots draw from the eight unused digits, and order matters: 8 · 7 · 6 = 336.

5 · 336 = 1680

Filling the last three slots first would have been a disaster: whether the first slot still has an odd digit available depends on what you used, forcing casework. Constrained slot first, always.

Example 2: "at least one" A club has 10 members, 4 of whom are officers. How many 3-person committees contain at least one officer?

"At least one" almost always means: count everything, subtract the ones with none.

Total committees: C(10, 3) = 120. Committees with no officer: choose all three from the 6 non-officers, C(6, 3) = 20.

120 − 20 = 100

The direct approach (one officer, two officers, three officers) gives C(4, 1)C(6, 2) + C(4, 2)C(6, 1) + C(4, 3)C(6, 0) = 60 + 36 + 4 = 100. Same answer, three times the work, three times the error surface.

Example 3: multiset permutation How many distinguishable arrangements are there of the letters in COMMITTEE?

Nine letters: C, O, I are single; M, T, E each appear twice.

9!/(2! 2! 2!) = 362880/8 = 45360

The denominator is a product over letters, not over positions. A frequent error is dividing by 6! (the count of repeated letters) or by 3! (the number of repeated letter types). Neither is correct.

Example 4: division principle, two ways In how many ways can 8 distinct people be split into 4 unordered pairs?

Method 1 (sequential). The lowest-numbered unpaired person has 7 possible partners. Remove that pair; the lowest-numbered remaining person has 5 choices. Then 3, then 1.

7 · 5 · 3 · 1 = 105 This method never overcounts, because "lowest-numbered unpaired person" is a canonical choice, no ordering of pairs is ever introduced.

Method 2 (overcount and divide). Line all 8 people up (8! ways) and pair positions (1,2), (3,4), (5,6), (7,8). Each pairing is produced many times: the two people inside each pair can swap (2⁴), and the four pairs can be permuted among the four slots (4!).

8!/(2⁴ · 4!) = 40320/384 = 105

Agreement is the check. When a division-principle count feels shaky, redo it sequentially with a canonical choice.

Common traps

Speed notes

Answer choices are diagnostics. If your answer is exactly k! times a listed choice, you counted an ordering that doesn't exist. If it's exactly k! times too small, you missed one. The unrestricted count is an upper bound. Compute it first as a sanity check and as a distractor filter. The largest answer choice is often exactly the "ignored the restriction" count. Small-case check. Run your formula at n=2 or n=3 where you can brute-force by hand. This catches off-by-one gap errors instantly. Prefer complementary counting whenever the phrase "at least one" or "no two" appears. C(n, k) with n large means wrong approach. AMC answers are computable by hand; if you're staring at C(40, 12), back up. If casework exceeds four cases, there is almost always a symmetry, complement, or canonical-choice argument that collapses it. Look for it before grinding.