Stats 1 Week 5: Counting & Permutations

0. Prerequisites

NOTE

What you need to know:

• Factorials ($n!$): $5!=5\times 4\times 3\times 2\times 1=120$.
• Basic Arithmetic: Multiplication tables.

Quick Refresher

• $0!=1$ (Definition).
• Multiplication Rule (AND): If you do A and then B, multiply choices.
• Addition Rule (OR): If you do A or B (mutually exclusive), add choices.
• Permutation (${}^n{P}_r$): Arrangement where Order Matters.

---

1. Core Concepts

1.1 Fundamental Principles of Counting

1. Multiplication Principle:
   • Scenario: 3 Shirts, 2 Pants. How many outfits?
   • Calc: $3\times 2=6$.
2. Addition Principle:
   • Scenario: Travel by Bus (3 routes) OR Train (2 routes). How many ways?
   • Calc: $3+2=5$.

1.2 Permutations (Order Matters)

• Formula: ${}^n{P}_r=\frac{n!}{(n-r)!}$.
• Key Idea: Selecting $r$ items from $n$ distinct items and arranging them.
• Repetition Allowed: $n^r$. (e.g., PIN codes).
• Circular Permutation: $(n-1)!$. (Sitting around a round table).

---

2. Pattern Analysis & Goated Solutions

Pattern 1: The “Together” Constraint (String Method)

Context: “How many ways to arrange 5 boys and 3 girls if all girls must sit together?”

TIP

Mental Algorithm:

1. Bundle: Treat the “Together” group as 1 Super-Person.
2. Outer Permutation: Arrange the Super-Person + Others.
   • Total entities = 5 (Boys) + 1 (Girl-Bundle) = 6.
   • Ways = $6!$.
3. Inner Permutation: Arrange the people inside the bundle.
   • 3 Girls = $3!$.
4. Multiply: Total = $6!\times 3!$.

Example (Detailed Solution)

Problem: 16 Men, 7 Women. Men sit together. Solution:

1. Bundle: 16 Men = 1 Unit.
2. Outer: 1 (Men-Unit) + 7 Women = 8 Units.
   • Wait! Question usually implies circular or linear. Let’s assume Linear first. $8!$.
   • Correction: If Circular (Round Table): $(8-1)!=7!$.
3. Inner: 16 Men can swap places: $16!$.
4. Total: $7!\times 16!$. Answer: $7!\times 16!$.

Pattern 2: Digits & Numbers (with/without Repetition)

Context: “Form a 4-digit number using 0, 1, 2, 3, 4, 5. No repetition. Divisible by 4?”

TIP

Mental Algorithm:

1. Slots: Draw 4 slots: [ ][ ][ ][ ].
2. Constraint First: Fill the restricted slot first.
   • Divisible by 4: Last 2 digits must be div by 4 (04, 12, 20, 24, 32, 40, 52…).
3. Zero Trap: First digit cannot be 0.
4. Fill Rest: Count remaining options for other slots.

Example (Detailed Solution)

Problem: 3-digit number from 0, 1, 2. No repetition. Solution:

1. Slots: [H][T][U].
2. Constraint: H cannot be 0.
   • H options: {1, 2} (2 choices).
3. Next: T options: Remaining 2 digits (including 0). (2 choices).
4. Next: U options: Remaining 1 digit. (1 choice).
5. Total: $2\times 2\times 1=4$.
   • (Check: 102, 120, 201, 210).

Pattern 3: Dictionary Rank (Lexicographic Order)

Context: “Rank of word ‘CAT’?”

TIP

Mental Algorithm:

1. Sort Letters: A, C, T.
2. Fix First:
   • Start with A: [A] _ _ $\to$ $2!=2$ words. (ACT, ATC).
   • Start with C: [C] _ _ $\to$ Match!
3. Fix Second:
   • Next available is A: [C][A] _ $\to$ Match!
4. Fix Third:
   • Next is T: [C][A][T] $\to$ Match!
5. Count: Previous full blocks + 1.
   • 2 (from A) + 1 (CAT itself) = 3.

---

3. Practice Exercises

1. Factorial: Calculate $\frac{10!}{8!}$.
   • Hint: $10\times 9=90$.
2. Arrangement: Ways to arrange letters of “DOG”?
   • Hint: $3!=6$.
3. Constraint: 5 people in a row, A and B must be at ends.
   • Hint: A_ _ B or B _ _A. $2\times 3!=12$.

---

🧠 Level Up: Advanced Practice

Question 1: Circular Permutation with Grouping

Problem: 16 men and 7 women at a round table (23 chairs). 16 men must sit together. Logic:

1. Group the Men: Treat 16 men as 1 unit ($M_{block}$).
2. Remaining Units: 7 women + 1 men-block = 8 units.
3. Circular Arrangement: $(n-1)!=(8-1)!=7!$.
4. Internal Arrangement: The 16 men can arrange themselves in $16!$ ways.
5. Total: $7!\times 16!$. Answer: $7!\times 16!$.

Question 2: Digit Problems (Divisibility)

Problem: 5-digit numbers from 0,2,4,5,7,9 (no repetition) divisible by 4. Logic:

1. Divisibility by 4: Last two digits must be divisible by 4.
2. Possible Endings (from given digits):
   • 04, 20, 24, 40, 52, 72, 92. (Wait, 04, 20, 40 involve 0).
   • Case 1 (Includes 0): Ends in 04, 20, 40. (3 endings).
     • Remaining 3 spots filled by remaining 4 digits. ${}^4{P}_3=24$.
     • Total = $3\times 24=72$.
   • Case 2 (No 0): Ends in 24, 52, 72, 92. (4 endings).
     • Remaining 3 spots: First spot cannot be 0.
     • Slots: $\underline{3}\times \underline{3}\times \underline{2}$. (Total 18).
     • Total = $4\times 18=72$.
3. Grand Total: $72+72=144$. Answer: 144.

Question 3: The “At Least One” Logic

Problem: 6 classmates. How many groups with teacher such that at least one student is there? Logic:

1. Total subsets of students: $2^6=64$.
2. Exclude empty set: $64-1=63$.
3. Add Teacher: Each group includes teacher. Answer: 63.