PR-3 Solutions: Counting Techniques

Problem 1 — FCP Probability (Generator)

For any generated FCP probability problem, the general solution structure is:

1. Count total outcomes using FCP: multiply the number of options at each stage.
2. Count favorable outcomes: apply the same FCP product but replace the restricted stage count with the smaller favorable count.
3. Compute \(P(\text{event}) = \text{favorable} / \text{total}\).

For example, if a 3-stage process has \(a\), \(b\), and \(c\) options per stage, and a restriction limits stage 1 to \(a'\) choices:

\[ \text{Total} = a \times b \times c, \qquad \text{Favorable} = a' \times b \times c \]

\[ P = \frac{a' \times b \times c}{a \times b \times c} = \frac{a'}{a} \]

When the restriction applies to only one stage, the probability simplifies to the proportion of favorable options at that stage alone.

---

Problem 2 — Permutation vs. Combination Classification (Variants 0–4)

Variant 0 (ordered reading list: 4 books chosen from 9, order matters):

• (a) Method: Permutation — "book 1 is read first, book 4 last." Different orderings of the same 4 books produce different reading lists.
• (b) Result: \(_9P_4 = 9 \times 8 \times 7 \times 6 = 3024\)

Variant 1 (jury of 5 from 12, no roles assigned):

• (a) Method: Combination — a jury is an unordered group; the same 5 people form the same jury regardless of how they are listed. No roles → no ordering.
• (b) Result: \(\binom{12}{5} = \frac{12!}{5!\,7!} = 792\)

Variant 2 (distinct medals for 1st, 2nd, 3rd from 7 runners):

• (a) Method: Permutation — gold, silver, and bronze are distinct ranks. Swapping two runners changes the outcome.
• (b) Result: \(_7P_3 = 7 \times 6 \times 5 = 210\)

Variant 3 (2 scoops from 8 flavours, stacking order irrelevant):

• (a) Method: Combination — the problem explicitly states the stacking order does not change the dessert. Same 2 flavours → same outcome.
• (b) Result: \(\binom{8}{2} = \frac{8 \times 7}{2} = 28\)

Variant 4 (4-character password from 10 distinct letters, ABCD ≠ DCBA):

• (a) Method: Permutation — different orderings of the same 4 letters produce different passwords. Order matters by definition of a login code.
• (b) Result: \(_{10}P_4 = 10 \times 9 \times 8 \times 7 = 5040\)

---

Problem 3 — Combination-Based Probability (Generator)

For any generated combination probability problem of the form "from \(n\) people (\(k\) with a trait), choose \(r\) — find \(P(\text{exactly}\; m\; \text{have the trait})\)":

\[ P = \frac{\binom{k}{m} \times \binom{n-k}{r-m}}{\binom{n}{r}} \]

The numerator multiplies two independent combination counts: one for choosing \(m\) trait-holders from \(k\), and one for choosing the remaining \(r - m\) from the \(n - k\) without the trait.

Example (\(n = 20\), \(k = 8\), \(r = 5\), \(m = 2\)):

\[ \binom{8}{2} \times \binom{12}{3} = 28 \times 220 = 6160 \]

\[ \binom{20}{5} = 15504 \]

\[ P = \frac{6160}{15504} \approx 0.397 \]

---

Problem 4 — Find the Error (Variants 0–4)

Variant 0 (starting lineup of 4 from 7 players — student used \(_7P_4 = 840\)):

• Error: Used a permutation for an unordered group. A lineup with no positions assigned is a combination — {Player A, B, C, D} is the same lineup regardless of listing order.
• Correct: \(\binom{7}{4} = \frac{7 \times 6 \times 5 \times 4}{4!} = 35\). The ratio \(840/35 = 24 = 4!\) confirms the overcounting factor.

Variant 1 (3-digit code, all digits different — student used \(10 \times 10 \times 10 = 1000\)):

• Error: Treated stages as independent when repetition is disallowed. "All digits different" means each chosen digit is removed from the pool, making stages dependent.
• Correct: \(10 \times 9 \times 8 = 720\). Stage 1: 10 choices; stage 2: 9 (one used); stage 3: 8 (two used).

Variant 2 (hire 2 from 12, no titles — student computed \(\binom{12}{2} = 66\) then doubled to 132):

• Error: Unwarranted doubling. The combination \(\binom{12}{2} = 66\) already counts each unordered pair exactly once. Multiplying by 2 converts the answer from a combination to a permutation (\(_{12}P_2 = 132\)), which would only be correct if the two hires had distinct roles.
• Correct: \(\binom{12}{2} = 66\). No titles → no ordering → no doubling.

Variant 3 (5 people in a row — student used \(5^5 = 3125\)):

• Error: Assumed each position has 5 independent choices, as if a person could occupy multiple positions simultaneously. "Distinct people" means once a person takes position 1, they cannot also take position 2.
• Correct: \(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\). Stages are dependent: choices decrease as positions fill.

Variant 4 (student claimed \(\binom{10}{0} = 0\)):

• Error: Confused \(0!\) with 0. By definition \(0! = 1\) — there is exactly one way to arrange zero objects (do nothing).
• Correct: \(\binom{10}{0} = \frac{10!}{0! \cdot 10!} = \frac{1}{1} = 1\). Confirmed by symmetry: \(\binom{10}{0} = \binom{10}{10} = 1\).

---

Problem 5 — Synthesis: Hiring Committee

(a) Total ways to select 6 from 15 candidates:

\[ \binom{15}{6} = \frac{15 \times 14 \times 13 \times 12 \times 11 \times 10}{6!} = \frac{3{,}603{,}600}{720} = 5005 \]

(b) Selections with exactly 4 experienced candidates (and 2 inexperienced):

\[ \binom{9}{4} \times \binom{6}{2} = 126 \times 15 = 1890 \]

Choose 4 from the 9 experienced candidates AND 2 from the 6 inexperienced candidates. These are independent selections, so multiply — do not add.

(c) Probability:

\[ P(\text{exactly 4 experienced}) = \frac{1890}{5005} \approx 0.3776 \]

(d) Direct vs. complement for \(P(\text{at least 4 experienced})\):

Direct: sum over exactly 4, exactly 5, and exactly 6 experienced — 3 terms.

Complement: \(1 - P(\text{fewer than 4 experienced})\) requires summing exactly 0, 1, 2, and 3 experienced — 4 terms.

Direct is slightly fewer calculations here. The complement approach is preferable when the complement has fewer cases (the opposite of this situation).

Question 1 — Feynman Test

Model answer:

The Fundamental Counting Principle multiplies the number of choices at each stage only when those choices are independent — meaning the number of options at any stage does not change based on what was chosen earlier. When you select items without replacement, the stages are dependent: each choice removes one option from the pool for the next stage.

Counterexample — distinct digits: "How many 4-digit codes can be formed from 0–9 with no repeated digit?" Incorrect: \(10 \times 10 \times 10 \times 10 = 10{,}000\) (treats all stages as having 10 independent choices). Correct: \(10 \times 9 \times 8 \times 7 = 5040\) — each digit used at one position cannot reappear at later positions. The signal words "no repeats," "distinct," and "without replacement" always indicate dependent stages.

---

Question 2 — Apply: Required Committee Member

A student council of 8 members must form a 3-person committee that always includes the student body president.

Part (a) — Number of valid committees:

Fix the president as one of the 3 committee members. The remaining 2 spots must be filled from the 7 other members (unordered selection):

\[ \binom{7}{2} = \frac{7 \times 6}{2} = 21 \text{ committees} \]

Part (b) — Probability the president is included:

Total unrestricted 3-person committees from 8 members: \(\binom{8}{3} = 56\).

\[ P(\text{president included}) = \frac{21}{56} = \frac{3}{8} = 0.375 \]

Verification via complement:

\(P(\text{president excluded}) = \binom{7}{3} / \binom{8}{3} = 35/56 = 5/8\). Therefore \(P(\text{included}) = 1 - 5/8 = 3/8\) ✓.

---

Question 3 — Error Analysis

Student's error: Used a combination \(\binom{8}{3} = 56\) for a ranking problem where the prizes are distinct (1st, 2nd, 3rd place). Combinations do not account for order — they treat "gold to A, silver to B" and "gold to B, silver to A" as the same outcome. In a ranked contest, these are two different outcomes.

Correct calculation:

\[ _8P_3 = 8 \times 7 \times 6 = 336 \text{ possible ranked outcomes} \]

Relationship between permutation and combination:

\[ _8P_3 = \binom{8}{3} \times 3! = 56 \times 6 = 336 \quad \checkmark \]

Each unordered group of 3 winners (counted by the combination) can be arranged in \(3! = 6\) distinct ranked orders. Permutation = Combination × internal arrangements.

Path A — The Cryptographer

A security app uses passcodes of exactly 4 characters from a 36-character set (digits 0–9 and letters A–Z, case-insensitive). No character may be repeated.

Task 1 — Total 4-character passcodes (no repetition):

Apply FCP with dependent stages (each character used reduces the pool by 1):

\[ 36 \times 35 \times 34 \times 33 = 1{,}413{,}720 \]

Verification: \(36 \times 35 = 1260\); \(1260 \times 34 = 42{,}840\); \(42{,}840 \times 33 = 1{,}413{,}720\).

Task 2 — Passcodes with a digit as the first character:

Restrict stage 1 to digits only (10 choices). Stages 2–4 draw from the remaining 35, 34, 33 characters (the first character — whatever it was — is now used):

\[ 10 \times 35 \times 34 \times 33 = 392{,}700 \]

Task 3 — Probability the first character is a digit:

\[ P(\text{first is a digit}) = \frac{392{,}700}{1{,}413{,}720} = \frac{10}{36} \approx 0.2778 \]

Intuitively, 10 of the 36 characters are digits, so the fraction simplifies to exactly 10/36 — the proportion of digits in the full character set.

Task 4 — With repetition allowed (\(36^4\)):

\[ 36^4 = 1{,}679{,}616 \]

Key change: When repetition is allowed, each of the 4 positions independently has all 36 characters available — the stages are truly independent. In Task 1 (no repetition), using a character at one position removes it from subsequent positions, making the stages dependent (choices decrease from 36 to 35 to 34 to 33). The FCP "independent stages" assumption is satisfied in Task 4 but not in Task 1.

---

Path B — The Tournament Director

A hockey tournament has 10 teams. Two directors disagree about the number of possible gold-silver-bronze podium outcomes.

Task 1 — Who is correct?

Director B is correct: \(_{10}P_3 = 720\).

Director A's error: used a combination (\(\binom{10}{3} = 120\)) for an ordered outcome. Gold, silver, and bronze are distinct awards — "Team X gold, Team Y silver" is a different podium from "Team Y gold, Team X silver." Order matters → permutation is required. The combination counts the same 3 teams in all orderings as one outcome, undercounting by a factor of \(3! = 6\): \(120 \times 6 = 720\) ✓.

Task 2 — Organizing committee (3 teams, no hierarchy):

No team has a higher role than another → unordered selection → combination:

\[ \binom{10}{3} = \frac{10 \times 9 \times 8}{6} = 120 \text{ distinct committees} \]

Task 3 — Probability Falcons, Bears, Eagles take all three medals (any order):

• Favorable: arrangements of the 3 specific teams in the 3 medal positions = \(3! = 6\)
• Total: \(_{10}P_3 = 720\)

\[ P = \frac{6}{720} = \frac{1}{120} \approx 0.0083 \]

Task 4 — Probability Falcons wins gold AND Bears wins silver:

• Falcons must win gold: 1 choice. Bears must win silver: 1 choice. Any of the remaining 8 teams wins bronze: 8 choices.
• Favorable: \(1 \times 1 \times 8 = 8\). Total: 720.

\[ P = \frac{8}{720} = \frac{1}{90} \approx 0.0111 \]

Problem 1 — Algebraic Proof + Combinatorial Argument

(a) Algebraic proof that \(\binom{n}{r} = \binom{n}{n-r}\):

Substitute \((n - r)\) for \(r\) in the combination formula:

\[ \binom{n}{n-r} = \frac{n!}{(n-r)!\,(n-(n-r))!} = \frac{n!}{(n-r)!\,r!} = \binom{n}{r} \quad \checkmark \]

The key simplification is \(n - (n - r) = r\), so the denominator becomes \((n-r)! \cdot r!\) — exactly the same as in \(\binom{n}{r}\).

(b) Combinatorial word argument:

Every time you choose \(r\) objects to include from a set of \(n\), you simultaneously determine exactly \(n - r\) objects to exclude. Each inclusion decision uniquely determines its complementary exclusion decision, and vice versa. Therefore the number of ways to choose \(r\) to include equals the number of ways to choose \(n - r\) to exclude.

Verification with \(n = 5\), \(r = 2\): All \(\binom{5}{2} = 10\) pairs from {A, B, C, D, E} chosen, each paired with its complementary triple of excluded elements — 10 pairs map to exactly 10 complementary triples, confirming \(\binom{5}{2} = \binom{5}{3} = 10\).

(c) Efficient evaluation using symmetry:

\[ \binom{20}{17} = \binom{20}{20-17} = \binom{20}{3} = \frac{20 \times 19 \times 18}{3 \times 2 \times 1} = \frac{6840}{6} = 1140 \]

No need to compute \(20!\) — symmetry converts the large \(r = 17\) into the small \(n - r = 3\), making the calculation trivial.

---

Problem 2 — Complement Technique (Generator)

For the generated complement counting problem (5-card hand from 52 cards, at least one card from a specified suit):

It is far easier to count the complement (no cards from the suit) than to enumerate all ways of getting at least one card from that suit (which requires summing over exactly 1, 2, 3, 4, and 5 cards from the suit — 5 terms).

\[ P(\text{no cards from suit}) = \frac{\binom{39}{5}}{\binom{52}{5}} = \frac{575{,}757}{2{,}598{,}960} \approx 0.2215 \]

\[ P(\text{at least one card from suit}) = 1 - 0.2215 = 0.7785 \]

(The specific suit name varies between generated instances; the computation is identical for hearts, diamonds, clubs, or spades — each suit has 13 cards, leaving 39 non-suit cards.)

---

Problem 3 — Restricted Arrangements (Block Method)

Six friends (Alex, Blake, Cam, Dana, Evan, Fran) are seated in a row of 6 chairs.

(a) Total seating arrangements:

\[ 6! = 720 \]

All 6 friends are distinct and all 6 chairs are distinct — this is a full permutation of 6 objects.

(b) Arrangements where Alex and Blake sit next to each other (block method):

Treat Alex and Blake as a single "AB block." Now there are 5 entities to arrange (the block + Cam, Dana, Evan, Fran):

\[ 5! \text{ arrangements of 5 entities} \]

Within the block, Alex and Blake can be ordered in \(2! = 2\) ways (Alex–Blake or Blake–Alex). Multiply:

\[ 2 \times 5! = 2 \times 120 = 240 \text{ arrangements with Alex and Blake adjacent} \]

(c) Arrangements where Alex and Blake are NOT adjacent:

\[ 720 - 240 = 480 \]

(d) Probability Alex and Blake are not adjacent:

\[ P(\text{not adjacent}) = \frac{480}{720} = \frac{2}{3} \approx 0.667 \]

Equivalently, \(P(\text{adjacent}) = 240/720 = 1/3\), so \(P(\text{not adjacent}) = 1 - 1/3 = 2/3\) ✓.