Stats 1 Week 6: Combinations

0. Prerequisites

NOTE

What you need to know:

• Permutations (${}^n{P}_r$): Arrangement (Order Matters).
• Factorials: Calculation of $n!$.

Quick Refresher

• Combination (${}^n{C}_r$): Selection where Order Does NOT Matter.
• Formula: ${}^n{C}_r=\frac{n!}{r!(n-r)!}$.
• Relation: ${}^n{P}_r{=}^n{C}_r\times r!$.
• Symmetry: ${}^n{C}_r{=}^n{C}_{n-r}$. (Selecting 2 to keep is same as selecting 8 to throw away).

---

1. Core Concepts

1.1 Permutation vs Combination

• Permutation: “Arrangement”, “Line up”, “Rank”, “Titles (Pres/VP)“.
  • Key: AB is different from BA.
• Combination: “Selection”, “Group”, “Committee”, “Handshake”.
  • Key: AB is same as BA.

1.2 Important Identities

1. Pascal’s Identity: ${}^n{C}_r{+}^n{C}_{r-1}{=}^{n+1}{C}_r$.
2. Sum of Coefficients: \sum_{r=0}^n \: ^nC_r = 2^n. (Total subsets of a set).
3. Selection from Identical Items:
   • Select $r$ items from $n$ identical items? 1 way. (Since they look same).

---

2. Pattern Analysis & Goated Solutions

Pattern 1: Forming Committees with Constraints

Context: “Select 5 people from 6 Men and 4 Women. Must have at least 3 Men.”

TIP

Mental Algorithm:

1. Cases: List all valid scenarios (Cases are mutually exclusive $\to$ Add).
   • Case 1: 3 Men, 2 Women.
   • Case 2: 4 Men, 1 Woman.
   • Case 3: 5 Men, 0 Women.
2. Calculate Each: Use Multiplication Rule within each case.
   • Case 1: ${}^6{C}_3{\times }^4{C}_2$.
3. Sum: Add the results of all cases.

Example (Detailed Solution)

Problem: Select 3 from 4 Boys, 3 Girls. At least 2 Boys. Solution:

1. Case 1 (2B, 1G): ${}^4{C}_2{\times }^3{C}_1=6\times 3=18$.
2. Case 2 (3B, 0G): ${}^4{C}_3{\times }^3{C}_0=4\times 1=4$.
3. Total: $18+4=22$. Answer: 22.

Pattern 2: Handshakes / Matches (Pairing)

Context: “10 people in a room. Everyone shakes hands with everyone. How many handshakes?”

TIP

Mental Algorithm:

1. Identify $n$: Total people = 10.
2. Identify $r$: A handshake involves 2 people. $r=2$.
3. Order?: Does “A shakes B” differ from “B shakes A”? No. $\to$ Combination.
4. Calc: ${}^{10}{C}_2$.

Example (Detailed Solution)

Problem: 10 teams in a league. Each plays each other once. Solution:

1. Select 2 teams: ${}^{10}{C}_2$.
2. Calc: $\frac{10\times 9}{2\times 1}=45$. Answer: 45 matches.

Pattern 3: Palindromes (Symmetry Constraint)

Context: “How many 5-digit palindromes?” (Reads same forward/backward).

TIP

Mental Algorithm:

1. Slots: [1][2][3][4][5].
2. Mirroring:
   • Slot 1 must match Slot 5.
   • Slot 2 must match Slot 4.
   • Slot 3 is independent.
3. Count Independent Choices:
   • Slot 1: 1-9 (9 choices). (Cannot be 0).
   • Slot 2: 0-9 (10 choices).
   • Slot 3: 0-9 (10 choices).
4. Dependent Slots: Have 1 choice (must match).
5. Total: $9\times 10\times 10\times 1\times 1=900$.

---

3. Practice Exercises

1. Basic: Calculate ${}^5{C}_2$.
   • Hint: $\frac{5\times 4}{2}=10$.
2. Committee: 3 Men, 3 Women. Select 2. No restrictions.
   • Hint: Total 6 people. ${}^6{C}_2=15$.
3. Geometry: Diagonals in a pentagon ($n=5$)?
   • Hint: Lines connecting any 2 points minus sides. ${}^5{C}_2-5=10-5=5$.

---

🧠 Level Up: Advanced Practice

Question 1: Team Formation with Exclusion

Problem: Select 5 from 10. But if A is selected, B must NOT be. Logic:

1. Total ways: ${}^{10}{C}_5=252$.
2. Bad cases (Both A and B selected):
   • Select A and B. Need 3 more from remaining 8.
   • ${}^8{C}_3=56$.
3. Valid ways: Total - Bad = $252-56=196$. Answer: 196.

Question 2: Binomial Identity

Problem: Find value of ${\sum }_{r=0}^n{3}^r{\cdot }^n{C}_r$. Logic:

1. Binomial Theorem: $(x+y{)}^n={\sum }^n{C}_r{x}^{n-r}{y}^r$.
2. Match: Let $y=3,x=1$.
3. Result: $(1+3{)}^n=4^n$. Answer: $4^n$.

Question 3: Geometry (Diagonals)

Problem: Number of diagonals in a decagon (10 sides). Logic:

1. Total connections: Connect any 2 points. ${}^{10}{C}_2=45$.
2. Subtract sides: 10 sides are not diagonals.
3. Result: $45-10=35$. Answer: 35.