🎲 Counting & Probability Tactics

Master the essential counting and probability techniques that will help you solve problems involving arrangements, combinations, and likelihood calculations efficiently.

🎯 Core Counting Strategies

Complement Counting

• Count what you don’t want: Subtract from total
• Use when direct counting is hard: Often easier than direct approach
• Apply to probability: $P(A) = 1 - P(A^c)$
• Use for “at least” problems: Count “none” and subtract

Principle of Inclusion-Exclusion (PIE)

• Two sets: $|A \cup B| = |A| + |B| - |A \cap B|$
• Three sets: $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$
• General formula: Alternating sum of intersections
• Use for overlapping sets: When sets have common elements

Indicator Variables

• Define indicator: $I_A = 1$ if event A occurs, 0 otherwise
• Expected value: $E[I_A] = P(A)$
• Linearity of expectation: $E[X + Y] = E[X] + E[Y]$
• Use for counting: Count occurrences of events

🔄 Complement Counting Mastery

When to Use Complement

• “At least” problems: Count “none” and subtract
• “At most” problems: Count “more than” and subtract
• Complex direct counting: When direct approach is difficult
• Probability problems: $P(A) = 1 - P(A^c)$

Complement Process

1. Identify what you want: What are you counting?
2. Identify what you don’t want: What’s the complement?
3. Count the complement: Use direct counting
4. Subtract from total: Total - complement
5. Check answer: Verify the result

Complement Example

Problem: How many ways can 5 people sit in a row if A and B cannot sit together?

Solution:

• Total arrangements: $5! = 120$
• Arrangements with A and B together: Treat A and B as one unit
• A and B together: $4! \cdot 2! = 24 \cdot 2 = 48$ (4 units, A and B can switch)
• Arrangements with A and B apart: $120 - 48 = 72$

Complement Probability Example

Problem: What’s the probability of getting at least one head in 3 coin flips?

Solution:

• $P(\text{at least one head}) = 1 - P(\text{no heads})$
• $P(\text{no heads}) = P(\text{all tails}) = \left(\frac{1}{2}\right)^3 = \frac{1}{8}$
• $P(\text{at least one head}) = 1 - \frac{1}{8} = \frac{7}{8}$

⚡ Principle of Inclusion-Exclusion

Two-Set PIE

Formula: $|A \cup B| = |A| + |B| - |A \cap B|$

When to use: Two overlapping sets

Process:

1. Count set A: Find $|A|$
2. Count set B: Find $|B|$
3. Count intersection: Find $|A \cap B|$
4. Apply formula: $|A| + |B| - |A \cap B|$
5. Check answer: Verify the result

Two-Set PIE Example

Problem: In a class of 30 students, 18 like math and 15 like science. If 8 like both, how many like at least one?

Solution:

• $|A| = 18$ (math), $|B| = 15$ (science), $|A \cap B| = 8$ (both)
• $|A \cup B| = 18 + 15 - 8 = 25$
• Answer: 25 students like at least one subject

Three-Set PIE

Formula: $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

When to use: Three overlapping sets

Process:

1. Count individual sets: Find $|A|, |B|, |C|$
2. Count pairwise intersections: Find $|A \cap B|, |A \cap C|, |B \cap C|$
3. Count triple intersection: Find $|A \cap B \cap C|$
4. Apply formula: Use the three-set formula
5. Check answer: Verify the result

🎯 Indicator Variable Techniques

Defining Indicators

Indicator variable: $I_A = \begin{cases} 1 & \text{if event A occurs} \ 0 & \text{if event A does not occur} \end{cases}$

Properties:

• $E[I_A] = P(A)$
• $E[I_A^2] = P(A)$ (since $I_A^2 = I_A$)
• $E[I_A I_B] = P(A \cap B)$

Linearity of Expectation

Formula: $E[X + Y] = E[X] + E[Y]$ for any random variables X and Y

Applications:

• Counting problems: Count occurrences of events
• Probability problems: Find expected values
• Complex problems: Break into simpler parts

Indicator Example

Problem: What’s the expected number of heads in 5 coin flips?

Solution:

• Let $X_i = 1$ if flip $i$ is heads, 0 otherwise
• $E[X_i] = P(\text{heads}) = \frac{1}{2}$ for each $i$
• $E[\text{total heads}] = E[X_1 + X_2 + \cdots + X_5] = E[X_1] + E[X_2] + \cdots + E[X_5] = 5 \cdot \frac{1}{2} = 2.5$

🔢 Symmetry Techniques

When to Use Symmetry

• Symmetric problems: When problem has symmetric structure
• Equal probability: When outcomes are equally likely
• Geometric problems: When shapes are symmetric
• Combinatorial problems: When arrangements are symmetric

Symmetry Process

1. Identify symmetry: Look for symmetric structure
2. Use symmetric properties: Apply symmetry principles
3. Count symmetric cases: Count one case and multiply
4. Check answer: Verify the result

Symmetry Example

Problem: How many ways can 4 people sit around a circular table?

Solution:

• Total arrangements: $4! = 24$
• But rotations are the same: $4$ rotations
• Distinct arrangements: $\frac{24}{4} = 6$
• Answer: 6 ways

🎯 Advanced Counting Techniques

Generating Functions

For counting: Use power series to count combinations For probability: Use generating functions for distributions For recurrence: Use generating functions to solve recurrences

Recurrence Relations

Define recurrence: Express current term in terms of previous terms Solve recurrence: Find closed form or use generating functions Apply to counting: Use recurrences to count arrangements

Catalan Numbers

Definition: $C_n = \frac{1}{n+1}\binom{2n}{n}$ Applications: Binary trees, parentheses, paths Recurrence: $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$

⚡ Quick Counting Tricks

Permutations

Formula: $P(n,r) = \frac{n!}{(n-r)!}$ When to use: Order matters, no repetition Examples: Arrangements, rankings, passwords

Combinations

Formula: $C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$ When to use: Order doesn’t matter, no repetition Examples: Committees, teams, subsets

Permutations with Repetition

Formula: $n^r$ When to use: Order matters, repetition allowed Examples: Passwords, license plates

Combinations with Repetition

Formula: $\binom{n+r-1}{r}$ When to use: Order doesn’t matter, repetition allowed Examples: Distributing identical objects

🎯 Problem-Specific Strategies

Arrangement Problems

• Use permutations: When order matters
• Use combinations: When order doesn’t matter
• Use complement: When direct counting is hard
• Use symmetry: When problem is symmetric

Probability Problems

• Use complement: $P(A) = 1 - P(A^c)$
• Use PIE: For overlapping events
• Use indicators: For counting problems
• Use symmetry: When outcomes are equally likely

Counting Problems

• Use direct counting: When straightforward
• Use complement: When direct counting is hard
• Use PIE: For overlapping sets
• Use generating functions: For complex problems

🚨 Common Counting Mistakes

Avoid These Errors:

• Order errors: Distinguish between permutations and combinations
• Repetition errors: Check if repetition is allowed
• Complement errors: Make sure you’re counting the right complement
• PIE errors: Apply the correct PIE formula
• Symmetry errors: Don’t double-count symmetric cases

Red Flags:

• Answer too large: Check for double-counting
• Answer too small: Check for missing cases
• Negative answer: Check your calculations
• Impossible result: Check your logic

📊 Quick Reference

Complement Counting Checklist:

• Identify what you want: What are you counting?
• Identify what you don’t want: What’s the complement?
• Count the complement: Use direct counting
• Subtract from total: Total - complement
• Check answer: Verify the result

PIE Checklist:

• Identify sets: What are the overlapping sets?
• Count individual sets: Find $|A|, |B|, |C|$
• Count intersections: Find pairwise and triple intersections
• Apply formula: Use appropriate PIE formula
• Check answer: Verify the result

Indicator Checklist:

• Define indicators: What events are you counting?
• Use linearity: Apply linearity of expectation
• Calculate expectations: Find $E[I_A]$ for each event
• Sum expectations: Use linearity to find total
• Check answer: Verify the result

Prev: Geometry Tactics | Next: Precalculus Tactics | Back to: Strategy Guide