Counting Principles - Formulas & Techniques
IB Mathematics Analysis & Approaches (SL & HL)
🎯 Fundamental Counting Principles
Multiplication Rule (AND Rule):
If one event can happen in \(m\) ways AND another event can happen in \(n\) ways, then both events together can happen in:
\[m \times n \text{ ways}\]
Example: If there are 5 shirts and 3 pants, you can make \(5 \times 3 = 15\) different outfits
Addition Rule (OR Rule):
If one event can happen in \(m\) ways OR another event can happen in \(n\) ways (mutually exclusive), then:
\[m + n \text{ ways}\]
Example: If you can travel by 3 buses OR 2 trains, you have \(3 + 2 = 5\) transport options
❗ Factorial Notation
Definition:
The factorial of a positive integer \(n\), denoted \(n!\), is the product of all positive integers from 1 to \(n\).
\[n! = n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1\]
Special Cases:
\[0! = 1\]
\[1! = 1\]
Examples:
\(3! = 3 \times 2 \times 1 = 6\)
\(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\)
\(10! = 3,628,800\)
🔢 Permutations (Order Matters)
When to Use:
Use permutations when the order of arrangement matters. Different orders count as different outcomes.
Permutation of n objects taken r at a time:
\[P(n,r) = \frac{n!}{(n-r)!}\]
Also written as: \(^nP_r\) or \(P_r^n\) or \(_nP_r\)
where \(n\) = total number of items, \(r\) = number of items to arrange
Permutation of all n objects:
\[P(n,n) = n!\]
Example: Arranging 5 books on a shelf = \(5! = 120\) ways
Permutations with Repetition:
When some objects are identical, the number of distinct permutations of \(n\) objects where there are \(p\) of one type, \(q\) of another type, etc.:
\[\frac{n!}{p! \times q! \times r! \times \cdots}\]
Example: Arrangements of MISSISSIPPI = \(\frac{11!}{4! \times 4! \times 2!}\) (4 S's, 4 I's, 2 P's)
🎲 Combinations (Order Does NOT Matter)
When to Use:
Use combinations when the order does NOT matter. Only the selection itself matters, not the arrangement.
Combination of n objects taken r at a time:
\[C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}\]
Also written as: \(^nC_r\) or \(C_r^n\) or \(_nC_r\) or \(\binom{n}{r}\) (binomial coefficient)
where \(n\) = total number of items, \(r\) = number of items to select
Relationship Between Permutations and Combinations:
\[P(n,r) = C(n,r) \times r!\]
Permutations = Combinations × (arrangements of selected items)
⭐ Important Properties
Combination Properties:
\[C(n,0) = 1\]
\[C(n,n) = 1\]
\[C(n,1) = n\]
Symmetry Property:
\[C(n,r) = C(n,n-r)\]
Choosing \(r\) items is the same as choosing which \((n-r)\) items to leave out
Pascal's Identity:
\[C(n,r) = C(n-1,r-1) + C(n-1,r)\]
🔄 Circular Permutations
Arranging n distinct objects in a circle:
In circular arrangements, rotations of the same arrangement are considered identical.
\[(n-1)!\]
Example: Arranging 5 people around a circular table = \((5-1)! = 4! = 24\) ways
Circular arrangements with reflections considered identical:
When reflections are also considered the same (e.g., necklaces or bracelets):
\[\frac{(n-1)!}{2}\]
🔀 Complementary Counting
Method:
Sometimes it's easier to count the complement (what you DON'T want) and subtract from the total.
\[\text{Desired outcomes} = \text{Total outcomes} - \text{Unwanted outcomes}\]
When to Use:
• "At least one" problems
• Complex restriction problems
• When the complement is easier to count
🎨 Common Restriction Scenarios
Keeping certain items together:
Method: Treat the items that must stay together as a single unit, then arrange internally
Example: Arrange 5 people where 2 must sit together = \(4! \times 2!\)
Keeping certain items apart:
Method 1: Total arrangements - (arrangements where they're together)
Method 2: Arrange other items first, then place restricted items in gaps
Fixed positions:
Method: Place the fixed items first, then arrange the remaining items
Example: Arrange 6 books where 1 specific book must be first = \(5!\)
📊 Permutations vs Combinations
| Aspect | Permutation | Combination |
|---|---|---|
| Order | Matters | Does NOT matter |
| Formula | \(\frac{n!}{(n-r)!}\) | \(\frac{n!}{r!(n-r)!}\) |
| Example | Race positions (1st, 2nd, 3rd) | Selecting team members |
| Keywords | Arrange, order, sequence | Select, choose, group |
🧮 Calculator Functions
📱 On most calculators and GDCs:
• Factorial: Use the \(n!\) button or MATH menu
• Permutations: Use \(nPr\) function → Enter \(n\), press nPr, enter \(r\)
• Combinations: Use \(nCr\) function → Enter \(n\), press nCr, enter \(r\)
• TI Calculators: MATH → PRB menu
• Casio Calculators: OPTN → PROB menu
💡 Key Question to Ask: Does the order of selection matter? If YES → use Permutations. If NO → use Combinations. When in doubt, list out small examples to see if different orders create different outcomes.