Combinatorics is the art of counting without listing everything. The two foundational rules β the Multiplication Principle and the Addition Principle β are all you need to build everything else. Master these, and permutations, combinations, and all advanced counting techniques will follow naturally.
If there are $m$ ways to do one thing, and $n$ ways to do a second thing, then there are $ m \times n $ ways to do both.
More formally: if task A has $a$ outcomes and task B has $b$ outcomes, then combined there are $a \cdot b$ outcomes.
\(Example: 3 shirts \\times 4 pants = 12 outfits\)
Key condition: the choices must be independent (the number of choices for B doesn't depend on what you picked for A).
If there are $m$ ways to do one thing and $n$ ways to do another, and you can't do both at the same time, then there are $ m + n $ ways to choose one of them.
Example: 3 fiction books + 5 non-fiction books = 8 ways to pick one book to read
Key condition: the options must be mutually exclusive (no overlap between the two sets).
$ n! $ (read "n factorial") = product of all positive integers from 1 to n
\[ n! = n \times (n-1) \times (n-2) \times ... \times 2 \times 1 \]
\(Examples: 5! = 5 \\times 4 \\times 3 \\times 2 \\times 1 = 120, 3! = 6, 1! = 1\)
Special definition: 0! = 1 (by convention, makes the formulas work)
How many ways to arrange n distinct objects in order?
\[ P(n, n) = n! \]
Reasoning: n choices for first position, n-1 for second, ..., 1 for last.
Example: arranging 3 books on a shelf: 3! = 6 ways (ABC, ACB, BAC, BCA, CAB, CBA)
How many ways to choose AND arrange k objects out of n distinct ones?
\[ P(n, k) = \frac{n!}{(n-k)!} = n \times (n-1) \times ... \times (n-k+1) \]
\(Example: picking president and vice-president from 10 people: P(10,2) = 10 \\times 9 = 90\)
Arranging n people around a circular table (rotations count as the same):
\[ (n-1)! \]
Why n-1? Fix one person's position to account for rotational symmetry, then arrange the rest: (n-1)! ways.
If reflections also count as the same (necklace problem): (n-1)! / 2
If you have n objects where some are identical:
\[ \frac{n!}{n_1! \cdot n_2! \cdot ... \cdot n_k!} \]
where $n_1, n_2, ..., n_k$ are counts of each identical type.
Example: arranging letters of "MISSISSIPPI"\(: 11! / (4! \\cdot 4! \\cdot 2! \\cdot 1!) = 34,650\)
When a problem has different scenarios, break it into mutually exclusive cases, count each separately, then add them up.
This is the Addition Principle applied strategically.
Key skill: make sure cases are complete (cover all possibilities) and disjoint (no double-counting).
Sometimes it's easier to count what you DON'T want and subtract from the total.
Answer = Total - Unwanted
Useful when the problem says "at least one" or "not all" β the complement is often simpler.
Multiplication principle: \(independent choices \\to multiply.\)
Step 1: Identify the independent choices.
Appetizer: 4 options
Main course: 6 options
Dessert: 3 options
Step 2: Multiply them.
\[ 4 \times 6 \times 3 = 72 \]
There are 72 different meal combinations.
Answer: 72
Permutations of n distinct objects = n!
Step 1: Think position by position.
Position 1: 5 choices (any of the 5 books)
Position 2: 4 remaining choices
Position 3: 3 choices
Position 4: 2 choices
Position 5: 1 choice (only one book left)
Step 2: Multiply (multiplication principle).
\[ 5 \times 4 \times 3 \times 2 \times 1 = 5! = 120 \]
Answer: 120
Permutations with repetition formula: \(n! / (n_{1}! \\times n_{2}! \\times ...)\)
Step 1: Count total letters and duplicates.
Total letters: 5 (A, A, B, B, C)
A appears: 2 times
B appears: 2 times
C appears: 1 time
Step 2: Apply formula.
\[ \frac{5!}{2! \times 2! \times 1!} = \frac{120}{2 \times 2 \times 1} = \frac{120}{4} = 30 \]
Why divide? Swapping the two A's gives the same arrangement, so we've overcounted by factor 2! for the A's and 2! for the B's. Dividing corrects the overcount.
Answer: 30