Selection (Counting Framework)

Context: FIT1058_MOC · choosing $r$ from $n$ objects · classified by order × replacement · unifies $n^r$, falling factorial, $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, and stars-and-bars

Quick Revision

• 🎯 Objective: count ways to pick $r$ from $n$ ➔ by two yes/no questions: order? replacement?.
• 📦 Core Components: ordered/with $n^r$ ➔ ordered/without $(n{)}_r$ ➔ unordered/without $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ ➔ unordered/with $\left(\genfrac{}{}{0ex}{}{r+n-1}{r}\right)$.
• ⚡ Key Constraint: identify the cell first; order divides ordered counts by $r!$.

📝 Core

1. Two Questions

• Order? ➔ ordered vs unordered.
• Replacement? ➔ with vs without reuse.
• Result ➔ the $2\times 2$ gives four formulas.

2. The Four Cells

• Ordered, with ➔ $n^r$ (strings/functions).
• Ordered, without ➔ $(n{)}_r=\frac{n!}{(n-r)!}$ (queues/injections).
• Unordered, without ➔ $\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\frac{(n{)}_r}{r!}$ (committees/subsets).
• Unordered, with ➔ $\left(\genfrac{}{}{0ex}{}{r+n-1}{r}\right)$ (Stars and Bars, multisets).

3. The Falling Factorial

• $(n{)}_r$ ➔ shrinking option count $n,n-1,\dots ,n-r+1$ ($r$ factors).
• ÷ $r!$ ➔ removes ordering ⟹ $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ (Binomial Coefficient).

Key identities:

$\text{ordered: }{n}^r\text{ (with)},(n{)}_r=\frac{n!}{(n-r)!}\text{ (without)}$ $\text{unordered: }\left(\genfrac{}{}{0ex}{}{r+n-1}{r}\right)\text{ (with)},\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\frac{(n{)}_r}{r!}\text{ (without)}$

⚖️ Core Decision Matrix

	Without replacement	With replacement
Ordered	$(n{)}_r=\frac{n!}{(n-r)!}$	$n^r$
Unordered	$\left(\genfrac{}{}{0ex}{}{n}{r}\right)$	$\left(\genfrac{}{}{0ex}{}{r+n-1}{r}\right)$

When It Flips: ordered counts exceed their unordered partners by exactly $r!$ (the orderings of the chosen items), so $\left(\genfrac{}{}{0ex}{}{n}{r}\right)=(n{)}_r/r!$. Each cell was met before: $n^r$ = functions/strings, $(n{)}_r$ = injections, $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ = subsets.

📊 Exam Execution Trace

Manual Execution Trace

$n=5$, $r=3$, all four modes:

Step / State	Mode	Formula	Count
0 (Init)	—	—	—
1	ordered, with	$5^3$	125
2	ordered, without	$(5{)}_3$	60
3	unordered, without	$\left(\genfrac{}{}{0ex}{}{5}{3}\right)$	10
4	unordered, with	$\left(\genfrac{}{}{0ex}{}{7}{3}\right)$	35

⚠️ Common Mistakes

• 💡 Replacement’s “simpler” side flips ➔ for ordered, with-replacement ($n^r$) is simpler; for unordered, without-replacement ($\left(\genfrac{}{}{0ex}{}{n}{r}\right)$) is simpler and the with-replacement case needs the bijection trick.

🧠 Active Recall

Give the four selection counts for choosing $r$ from $n$.

• Hint: Order × replacement.

Answer

• Short answer: $n^r$ (ord/with), $(n{)}_r$ (ord/without), $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ (unord/without), $\left(\genfrac{}{}{0ex}{}{r+n-1}{r}\right)$ (unord/with).
• Why: ÷$r!$ ➔ order divides the ordered counts down to unordered.

Why is $\left(\genfrac{}{}{0ex}{}{n}{r}\right)=(n{)}_r/r!$, and which two questions decide the formula?

• Hint: Remove ordering.

Answer

• Short answer: Each unordered choice arises from $r!$ ordered arrangements; divide to remove order.
• Why: Two questions ➔ does order matter, is replacement allowed — select one of four cells.