AMC 8 Wiki › Counting & Probability › Advanced Counting Models

Advanced Counting Models · Lecture 13 · cp-advanced-counting

📺 Course materials — Lecture 13: lecture video · handout PDF (Lecture 13) · board notes (13.jpg) · homework answer key (Chapter 13) — all in the amc8/video folder.  ·  🖨 Printable PDF (answers & solutions at the back)

🔑 Key facts

The balls-and-urns model (stars and bars): put $m$ identical balls into $n$ distinct urns.

Almost every distribution problem on AMC 8 is one of these three formulas plus a correction (pre-dealing, complement, or PIE).

🧰 Instructor's toolbox (from the lecture video & board notes)

1 · Ask the two questions first. Before touching a formula, decide: are the balls identical? are the urns identical? The instructor's board chart runs all four cases for $5$ balls, $3$ urns: Mixing up these cases is the classic error of this chapter.
2 · Stars and bars, no empty urns. Line up the $m$ identical balls; they create $m-1$ gaps; choosing $n-1$ gaps for dividers cuts them into $n$ nonempty groups: $\dbinom{m-1}{n-1}$. Board example: $5$ balls, $3$ urns → $\binom42=6$.
2 dividers in 4 gaps → groups of 2, 2, 1 C(4,2) = 6
3 · Empty urns allowed → the phantom-ball trick. Give every urn one extra (phantom) ball first: now no urn is empty, and the count is $\dbinom{m+n-1}{n-1}$. Board example: $5$ balls, $3$ urns, empties OK → pretend it is $8$ balls → $\binom72=21$. Equivalent view from the board: arrange the $m$ balls and $n-1$ dividers in one row, any order — $\binom{m+n-1}{n-1}$ again.
4 · "At least $k$ each" → deal the guaranteed part first. Hand each urn $k-1$ balls and require nonempty — or hand each urn $k$ balls and allow empties. Both routes must agree, which is the instructor's built-in error check. Example 2 (24 apples, at least 2 each): deal 1 each → $21$ apples, none empty → $\binom{20}{2}=190$; deal 2 each → $18$ apples, empties OK → $\binom{20}{2}=190$. Same number, confidence doubled.
5 · Distinct balls, distinct urns: "every ball picks an urn." Each of the $m$ different balls independently chooses one of $n$ urns: $n\cdot n\cdots n = n^m$ (empty urns allowed). Board example: $5$ different balls, $3$ different urns → $3^5=243$. Don't reverse it — it is not $m^n$: the balls do the choosing, because each ball lands exactly once.
6 · Distinct balls, nobody empty-handed → complement or partition casework. Two board-approved routes for Example 3 ($5$ awards, $3$ students): When both give $150$, you know it's right.
7 · PIE cleans up the complement. For "at least one of the bad events happens": \[|A\cup B\cup C| = |A|+|B|+|C| - |A\cap B|-|A\cap C|-|B\cap C| + |A\cap B\cap C|.\] Board example (awards): $A,B,C$ = "student $X$ gets nothing": $3\cdot2^5 - 3\cdot1 + 0 = 93$ bad, so $243-93=150$. The same machine powers Challenge C1 and the seating bans in Challenge C2 (bad events = "banned pair sits together", counted with the glue-the-pair trick).
8 · Digit problems are balls and urns in disguise. "$3$-digit numbers with digit sum $8$" = drop $8$ balls into $3$ positions. Board version: digits all $\ge 1$ → $\binom72=21$; zeros allowed in the tens/units (only the leading digit $\ge1$) → phantom-ball those two positions: sum becomes $8+2=10$, all three positions $\ge1$ → $\binom92=36$. Ordered sums ("compositions", Practice 2) are exactly the same model.
9 · Paths and stairs: label the nodes, or recurse. To count routes, write on each node the number of ways to reach it — each label is the sum of the labels that feed it (a tilted Pascal's triangle). That is the board solution of Example 4. For stairs taken $1$, $2$, or $3$ at a time, the same idea becomes the recursion $f(n)=f(n-1)+f(n-2)+f(n-3)$ — the board runs $1,\,2,\,4,\,7,\,13,\,24$ up the staircase for Practice 3. And when the direct count is messy, count all paths minus the illegal ones (that's how Example 4 is checked: $\binom73-7=28$).
124 71324 f(n) = f(n−1)+f(n−2)+f(n−3) 28 919 3613 1249 each label = sum of the two below

📖 Worked examples

2004 AMC 8 #17 · urns, none empty

Example 1. Three friends have a total of $6$ identical pencils, and each one has at least one pencil. In how many ways can this happen?

(A) 1(B) 3(C) 6(D) 10(E) 12
🧰 #1 Two questions#2 Stars & bars
Key idea: identical pencils (balls), distinct friends (urns), nobody empty — that's the pure model. $\binom{6-1}{3-1}=\binom52=10$.
Check by casework: give everyone $1$ pencil, distribute the remaining $3$: all to one person ($3$ ways), split $2{+}1$ between two people ($3\cdot2=6$ ways), or $1$ each ($1$ way) — $3+6+1=10$. Answer: D
2019 AMC 8 #25 · at least 2 each

Example 2. Alice has $24$ apples. In how many ways can she share them with Becky and Chris so that each of the three people has at least two apples?

(A) 105(B) 114(C) 190(D) 210(E) 380
🧰 #4 Deal first#2 Stars & bars#3 Phantom ball
Key idea: pre-deal the guaranteed apples. Give each person $2$ apples up front; the remaining $18$ go to $3$ people with empties allowed: $\binom{18+3-1}{3-1}=\binom{20}{2}=190$.
Board double-check: give each person only $1$ apple; the remaining $21$ must leave nobody empty: $\binom{21-1}{3-1}=\binom{20}{2}=190$. Same answer, two roads. Answer: C
2020 AMC 8 #23 · distinct balls

Example 3. Five different awards are to be given to three students. Each student will receive at least one award. In how many different ways can the awards be distributed?

(A) 120(B) 150(C) 180(D) 210(E) 240
🧰 #1 Two questions#6 Distinct + nonempty#7 PIE
Key idea: the awards are different, so this is NOT stars and bars. Shapes first: the split is $3{+}1{+}1$ or $2{+}2{+}1$. For $3{+}1{+}1$: pick who gets $3$ ($3$ ways), pick their awards $\binom53=10$, give the last two awards to the two others ($2$ ways): $3\cdot10\cdot2=60$. For $2{+}2{+}1$: pick who gets $1$ ($3$ ways), pick that award ($\binom51=5$), pick $2$ of the remaining $4$ for the next student ($\binom42=6$): $3\cdot5\cdot6=90$. Total $60+90=150$.
Complement check: $3^5 - \underbrace{(3\cdot2^5-3)}_{\text{someone empty (PIE)}} = 243-93=150$. Answer: B
2020 AMC 8 #21 · paths

Example 4. A game board consists of $64$ squares that alternate in color between black and white. The figure below shows square $P$ in the bottom row and square $Q$ in the top row. A marker is placed at $P$. A step consists of moving the marker onto one of the adjoining white squares in the row above. How many $7$-step paths are there from $P$ to $Q$? (The figure shows a sample path.)

(A) 28(B) 30(C) 32(D) 33(E) 35
🧰 #9 Label the nodes
Key idea: a white square can only be entered from the white squares diagonally below it — so label every white square with the number of ways to reach it, each label the sum of the (one or two) labels below. Climbing the seven rows gives $28$ at $Q$.
Complement check: each step goes diagonally left or right; to climb from $P$ to $Q$ takes $4$ rights and $3$ lefts $\Rightarrow\binom73=35$ orders. Paths that would run off the right edge: $RRR\ldots$ ($4$ ways), $RRLRR\ldots$, $RLRRR\ldots$, $LRRRR\ldots$ ($1$ each) — $7$ illegal. $35-7=28$. Answer: A

✏️ Practice

Try each one before opening the solution. Figures are from the official exams.

mock · course problem

1. Three friends have a total of $6$ identical pencils. In how many ways can the pencils be distributed among them? (A friend may end up with no pencil.)

(A) 10(B) 12(C) 28(D) 24(E) 16
Solution
🧰 #3 Phantom ball
Same pencils as Example 1, but now empties are allowed: $\binom{6+3-1}{3-1}=\binom82=28$. (Phantom-ball view: pretend it's $9$ pencils with nobody empty.) Answer: C
mock · course problem

2. In how many ways may we write the number $9$ as the sum of three positive integer summands? Here order counts, so, for example, $1+7+1$ is regarded as different from $7+1+1$.

(A) 16(B) 27(C) 30(D) 14(E) 28
Solution
🧰 #8 Digits & sums#2 Stars & bars
An ordered sum is a distribution: drop $9$ identical balls into $3$ ordered slots, none empty: $\binom{9-1}{3-1}=\binom82=28$. Answer: E
2010 AMC 8 #25

3. Every day at school, Jo climbs a flight of $6$ stairs. Jo can take the stairs $1$, $2$, or $3$ at a time. For example, Jo could climb $3$, then $1$, then $2$. In how many ways can Jo climb the stairs?

(A) 13(B) 18(C) 20(D) 22(E) 24
Solution
🧰 #9 Recursion#2 Stars & bars
Recursion (fastest): ways to reach step $n$: $f(n)=f(n-1)+f(n-2)+f(n-3)$, giving $1,2,4,7,13,\mathbf{24}$.
Balls-and-urns casework (the board's other route): split $6$ into $k$ hops, none empty, parts $\le3$: $k=2$: only $3{+}3$ → $1$; $k=3$: $\binom52=10$ minus the $3$ arrangements of $4{+}1{+}1$ → $7$; $k=4$: $\binom53=10$; $k=5$: $\binom54=5$; $k=6$: $1$. Total $1+7+10+5+1=24$. Answer: E
2003 AMC 10A #21 · AMC 10

4. Pat is to select cookies from a tray containing only chocolate chip, oatmeal, and peanut butter cookies. There are at least six of each of these three kinds of cookies on the tray. How many different assortments of six cookies can be selected?

(A) 22(B) 25(C) 27(D) 28(E) 29
Solution
🧰 #1 Two questions#3 Phantom ball
Choosing $6$ cookies from $3$ kinds is distributing $6$ identical picks among $3$ kinds, where a kind may get zero: $\binom{6+3-1}{3-1}=\binom82=28$. Answer: D
2018 AMC 10A #11 · AMC 10

5. When $7$ fair standard $6$-sided dice are thrown, the probability that the sum of the numbers on the top faces is $10$ can be written as $\dfrac{n}{6^7}$, where $n$ is a positive integer. What is $n$?

(A) 42(B) 49(C) 56(D) 63(E) 84
Solution
🧰 #2 Stars & bars#1 Two questions
Each die shows at least $1$ — that's $7$ urns, none empty, holding $10$ identical balls (the pips): $n=\binom{10-1}{7-1}=\binom96=\binom93=84$. (Faces max out at $6$, but with sum $10$ over $7$ dice no die can exceed $4$, so the cap never binds.) Answer: E

🆕 Fresh from the latest exams

The same ideas, exactly as they appeared on the most recent tests.

2024 AMC 8 #13

6. Buzz Bunny is hopping up and down a set of stairs, one step at a time. In how many ways can Buzz Bunny start on the ground, make a sequence of $6$ hops, and end up back on the ground? (For example, one sequence of hops is up-up-down-down-up-down.)

(A) 4(B) 5(C) 6(D) 8(E) 12
Solution
🧰 #9 Label the nodes
Three ups and three downs, never dipping below the ground. Label each (hop, height) node with the number of ways to reach it — each label is the sum of its feeders, and heights below $0$ don't exist. The labels give $5$ sequences: UUUDDD, UUDUDD, UUDDUD, UDUUDD, UDUDUD. Answer: B
2026 AMC 8 #20

7. The land of Catania uses gold coins and silver coins. Gold coins are $1$ mm thick and silver coins are $3$ mm thick. In how many ways can Taylor make a stack of coins that is $8$ mm tall using any arrangement of gold and silver coins, assuming order matters?

(A) 3(B) 7(C) 10(D) 13(E) 16
Solution
🧰 #9 Recursion#8 Ordered sums
Jo's staircase in disguise: ordered sums of $8$ using parts $1$ and $3$. Casework on the number of silver coins: zero $3$s → $1$ way; one $3$ (with five $1$s): $6$ coins, choose the $3$'s position → $6$; two $3$s (with two $1$s): $\binom42=6$. Total $1+6+6=13$.
Recursion check: $f(n)=f(n-1)+f(n-3)$: $1,1,2,3,4,6,9,\mathbf{13}$. Answer: D
2026 AMC 8 #17

8. Four students are seated in a row. They chat with the people sitting next to them, then rearrange themselves so that they are no longer seated next to any of the same people. How many rearrangements are possible?

(A) 2(B) 4(C) 9(D) 12(E) 24
Solution
🧰 #7 PIE / banned pairs
Call them $A,B,C,D$ in original order; the banned adjacent pairs are $AB$, $BC$, $CD$ — the same setup as Challenge C2. With only $24$ arrangements, smart enumeration wins: $B$ and $C$ can't be neighbors of their old partners, which forces them to the outside seats with $A,D$ tucked between strangers. Only $CADB$ and $BDAC$ survive. Answer: A

⭐ Challenge (AMC 10 level)

2010 AMC 10B #22 · distinct balls + PIE

C1. Seven distinct pieces of candy are to be distributed among three bags. The red bag and the blue bag must each receive at least one piece of candy; the white bag may remain empty. How many arrangements are possible?

(A) 1930(B) 1931(C) 1932(D) 1933(E) 1934
Solution
🧰 #5 Balls choose urns#7 PIE
Total: each of $7$ distinct candies picks a bag → $3^7=2187$. Bad = red or blue empty. By PIE: $|R\cup B| = 2^7 + 2^7 - 1^7 = 255$ (if red is empty the candies pick from $2$ bags, etc.). $2187-255=1932$. Answer: C
2017 AMC 10A #19 · PIE + gluing

C2. Alice refuses to sit next to either Bob or Carla. Derek refuses to sit next to Eric. In how many ways can the five of them sit in a row of five chairs under these conditions?

(A) 12(B) 16(C) 28(D) 32(E) 40
Solution
🧰 #7 PIE
Bad events: $AB$ together, $AC$ together, $DE$ together. Glue a pair into one block: $2\cdot4!=48$ each. Pairwise overlaps: $AB\cap AC$ = $BAC$ glued with $A$ in the middle: $2\cdot3!=12$; $AB\cap DE$ and $AC\cap DE$: two glued blocks: $2\cdot2\cdot3!=24$ each. Triple: $BAC$ glued and $DE$ glued: $2\cdot2\cdot2!=8$. PIE: $48\cdot3-(12+24+24)+8=92$ bad, so $5!-92=120-92=28$. Answer: C

🗝 Answer key

Example1234
DCBA
Practice12345678
CEEDEBDA
ChallengeC1C2
CC

Sources: prep-course Lecture 13 (video + board notes + 11 worked examples, translated to English) and official AMC 8 / AMC 10 problems from the local bank (kb/content/banks/). Answers verified against the bank's official answer keys where available.