Difficulty: Intermediate | Prerequisites: Basic algebra, factorial notation
Tags: product rule, sum rule, subtraction rule, division rule, inclusion-exclusion, pigeonhole principle, permutation, combination, r-permutation, r-combination, binomial theorem, binomial coefficient, Pascal's triangle, Pascal's identity, stars and bars, repetition, counting, combinatorics, CS182, discrete math, Purdue
Counting is the mathematical skill underneath probability, algorithm analysis, and cryptography. When you need to know how many passwords are possible, how many hands of poker exist, or how many ways to assign tasks to processors, you are doing combinatorics. This chapter gives you four fundamental counting rules (product, sum, subtraction, division), the pigeonhole principle (a surprisingly powerful existence argument), permutations and combinations (ordered vs unordered selections), and the binomial theorem. Master these and you have the tools for all of Chapter 7 (probability).
The product rule multiplies choices for sequential tasks; the sum rule adds choices for mutually exclusive tasks. The pigeonhole principle guarantees collisions when you have more objects than boxes. Permutations count ordered arrangements; combinations count unordered selections. The binomial theorem expands (x + y)ⁿ using binomial coefficients, which are arranged in Pascal's triangle.
Product rule
If a procedure consists of two sequential tasks, with n₁ ways for the first and n₂ ways for the second (for each way of doing the first), there are n₁ × n₂ ways total. Think of it as: each choice in step 1 branches into n₂ choices in step 2.
Sum rule
If a task can be done in one of n₁ ways OR in one of n₂ ways (mutually exclusive), there are n₁ + n₂ ways total. In simple terms, you add when choosing between disjoint options.
Subtraction rule (inclusion-exclusion for two sets)
|A ∪ B| = |A| + |B| - |A ∩ B|. Use this when two sets of options overlap and you would otherwise double-count.
Division rule
If a task can be done in n ways, and every outcome is counted exactly d times (due to symmetry), then there are n/d distinct outcomes.
Pigeonhole principle
If k + 1 objects are placed into k boxes, at least one box contains two or more objects. Think of it as: if you have more pigeons than pigeonholes, at least one hole has multiple pigeons.
Generalized pigeonhole principle
If N objects are placed into k boxes, at least one box contains at least ⌈N/k⌉ objects.
Permutation (r-permutation)
An ordered arrangement of r elements chosen from a set of n distinct elements. P(n, r) = n! / (n - r)!. In simple terms, order matters.
Combination (r-combination)
An unordered selection of r elements from a set of n elements. C(n, r) = n! / (r!(n - r)!). In simple terms, order does not matter.
Binomial coefficient
C(n, k), also written as "n choose k." The number of ways to choose k items from n, and the coefficient of x^k y^(n-k) in the expansion of (x + y)ⁿ.
Binomial theorem
(x + y)ⁿ = Σ(j=0 to n) C(n, j) xⁿ⁻ʲ yʲ.
Pascal's identity
C(n+1, k) = C(n, k-1) + C(n, k). Each entry in Pascal's triangle is the sum of the two entries above it.
Permutations with repetition
The number of r-permutations of n objects with repetition allowed is nʳ.
Combinations with repetition (stars and bars)
The number of r-combinations of n types with repetition allowed is C(n + r - 1, r) = C(n + r - 1, n - 1).
Product rule examples:
Bit strings of length 7: each bit is 0 or 1, so 2⁷ = 128 strings.
License plates with 3 uppercase letters followed by 3 digits: 26³ × 10³.
Number of subsets of a set S with |S| = k: each element is in or out, so 2ᵏ subsets.
Sum rule examples:
Choosing a student OR a faculty member as committee rep, with 558 students and 47 faculty (no overlap): 558 + 47 = 605 ways.
IDs that are either two uppercase letters or one letter followed by one digit: 26² + 26 × 10 = 936 IDs.
Subtraction rule example:
Bit strings of length 8 that start with 1 OR end with 00:
Strings starting with 1: 2⁷ = 128
Strings ending with 00: 2⁶ = 64
Strings starting with 1 AND ending with 00: 2⁵ = 32
Total: 128 + 64 - 32 = 160.
Division rule example:
Seating 4 people around a circular table (rotations are equivalent): 4! = 24 arrangements, but each seating has 4 rotations that look the same. So 24/4 = 6 distinct seatings.
Passwords example:
Password is 6 to 8 characters, each uppercase letter or digit, must contain at least one digit.
For length L: total passwords = 36^L, all-letter passwords = 26^L. Passwords with at least one digit = 36^L - 26^L.
Sum over L = 6, 7, 8: P₆ + P₇ + P₈ = (36⁶ - 26⁶) + (36⁷ - 26⁷) + (36⁸ - 26⁸).
If k + 1 objects go into k boxes, some box gets at least 2 objects.
Birthday problem: 367 people guarantee at least two share a birthday (366 possible birthdays + 1).
Multiples with only 0s and 1s: for any positive integer n, consider the n + 1 numbers: 1, 11, 111, ..., 111...1 (with n+1 ones). Divide each by n. By the pigeonhole principle, two have the same remainder. Their difference is a multiple of n containing only 0s and 1s.
Generalized pigeonhole principle: N objects in k boxes means at least one box has ⌈N/k⌉ objects.
100 people, 12 months: at least ⌈100/12⌉ = 9 people share a birth month.
Cards from a 52-card deck: to guarantee 3 cards of the same suit, you need 2 × 4 + 1 = 9 cards (two of each suit, then one more forces a third in some suit).
To guarantee 3 hearts specifically: worst case, draw all 39 non-hearts first, then 3 hearts. Need 39 + 3 = 42 cards.
Permutations (order matters):
P(n, r) = n! / (n - r)!
P(100, 3) = 100 × 99 × 98 = 970,200 (selecting 1st, 2nd, 3rd prize from 100 contestants)
Visiting 7 cities in any order from 8 (start fixed): 7! = 5,040
Permutations of ABCDEFGH containing the string ABC (treat ABC as a single block): 6! = 720
Combinations (order does not matter):
C(n, r) = n! / (r!(n - r)!)
C(52, 5) = 2,598,960 (poker hands)
C(52, 47) = C(52, 5) (complement property)
C(10, 5) = 252 (selecting 5 from 10 tennis players)
C(10, 3) = 120 (bit strings of length 10 with exactly three 1s)
Permutations with non-distinct objects (HONOLULU):
8 letters: H(1), O(2), N(1), L(2), U(2)
Place the O's: C(8, 2). Place the L's: C(6, 2). Place the U's: C(4, 2). Then H and N fill remaining spots: 2 × 1.
Total: C(8,2) × C(6,2) × C(4,2) × 2 = 5,040.
Equivalently: 8! / (2! × 2! × 2!) = 5,040.
SUCCESS example: 7 letters with S(3), C(2), U(1), E(1).
C(7,3) × C(4,2) × C(2,1) × C(1,1) = 420.
Or: 7! / (3! × 2!) = 420.
Binomial Theorem: (x + y)ⁿ = Σ(j=0 to n) C(n, j) xⁿ⁻ʲ yʲ.
Example: (x + y)⁷ = x⁷ + 7x⁶y + 21x⁵y² + 35x⁴y³ + 35x³y⁴ + 21x²y⁵ + 7xy⁶ + y⁷.
Coefficient of x¹²y¹³ in (2x - 3y)²⁵: C(25, 13) × 2¹² × (-3)¹³.
Pascal's Identity: C(n+1, k) = C(n, k-1) + C(n, k).
Pascal's Triangle: each row gives the binomial coefficients for that power. Each entry is the sum of the two above it. Fibonacci numbers appear along the diagonals.
Vandermonde's Identity (sums of squares): Σ(k=0 to n) C(n, k)² = C(2n, n).
Permutations with repetition: n objects, choose r with replacement, order matters. Count: nʳ.
Strings of length r from 26 uppercase letters: 26ʳ.
Combinations with repetition (stars and bars): n types of objects, choose r, order does not matter. Count: C(n + r - 1, r).
The idea: represent r identical items (stars) and n - 1 dividers (bars) in a row. Choose positions for the bars (or stars).
Examples:
x + y + z = 11 with non-negative integers: 11 stars, 2 bars. C(13, 2) = 78. Wait, C(13,2) = 78, the notes say 72. Let me recheck: C(13,2) = 13!/(2!11!) = 78. The notes say C(13,2) = 72 which appears to be an error in the source. The standard formula gives C(n+r-1, r) = C(11+3-1, 11) = C(13, 11) = C(13, 2) = 78.
6 cookies from 4 kinds: 6 stars, 3 bars. C(9, 3) = 84.
5 bills from 6 denominations: 5 stars, 5 bars (wait, 6 types means 5 bars). C(10, 5) = 252. The source notes say C(11,6)=462 with "6 bars and 5 stars, 11 items." That would be choosing from 6 denominations with 5 bills: C(6+5-1, 5) = C(10, 5) = 252. There may be a discrepancy in the source.
Type | Repetition? | Formula |
|---|---|---|
r-permutations | No | n! / (n-r)! |
r-combinations | No | n! / (r!(n-r)!) |
r-permutations | Yes | nʳ |
r-combinations | Yes | C(n+r-1, r) |
P(n, r) = n! / (n - r)!
C(n, r) = n! / (r!(n - r)!)
Binomial theorem: (x + y)ⁿ = Σ C(n, j) xⁿ⁻ʲ yʲ
Pascal's identity: C(n+1, k) = C(n, k-1) + C(n, k)
Inclusion-exclusion: |A ∪ B| = |A| + |B| - |A ∩ B|
Generalized pigeonhole: at least one box has ⌈N/k⌉ objects
Stars and bars: C(n + r - 1, r) for r-combinations with repetition from n types
Counting techniques are used to calculate the number of possible encryption keys (product rule), the number of ways to assign resources in networking (combinations), and the probability of hash collisions (pigeonhole principle). Password strength estimation is a direct application of the product rule. The binomial theorem appears in probability distributions (binomial distribution) and in signal processing.
"The product rule and sum rule are interchangeable." They are not. Product rule applies to sequential (AND) tasks; sum rule applies to mutually exclusive (OR) tasks.
"Permutations and combinations are the same." Permutations care about order; combinations do not. P(5, 3) = 60 but C(5, 3) = 10.
"The pigeonhole principle tells you which box has two objects." It does not. It is a pure existence result: it guarantees at least one box is overfull but does not identify which one.
"Stars and bars only works for equations like x + y + z = n." It works for any problem equivalent to distributing identical objects into distinct bins with unlimited supply.
⚠️ Be able to identify whether a problem calls for the product rule, sum rule, or subtraction rule.
⚠️ Know when to use permutations vs combinations. The key question: does order matter?
⚠️ For pigeonhole problems, clearly identify the "pigeons" (objects) and "pigeonholes" (boxes).
⚠️ For binomial coefficient questions, be comfortable extracting a specific term from the expansion of (ax + by)ⁿ.
⚠️ Practice stars-and-bars problems. Identify n (types/bins) and r (items to distribute).
⚠️ Be able to handle permutations of non-distinct objects (like HONOLULU or SUCCESS).
Fill in the blank: The number of bit strings of length 10 is ______.
True or False: C(n, r) = C(n, n - r).
Fill in the blank: To guarantee 3 cards of the same suit from a 52-card deck, you must draw at least ______ cards.
True or False: The number of ways to choose 5 items from 20 with repetition allowed is C(24, 5).
Fill in the blank: (x + y)⁴ expanded has ______ terms.
Answers: 1. 2¹⁰ = 1024. 2. True. 3. 9. 4. True (C(20+5-1, 5) = C(24, 5)). 5. 5 terms.
Q: How many ways can a committee of 5 be chosen from 12 people?
A: C(12, 5) = 12! / (5! × 7!) = 792.
Q: How many bit strings of length 8 start with 1 or end with 00?
A: Strings starting with 1: 2⁷ = 128. Strings ending with 00: 2⁶ = 64. Both: 2⁵ = 32. By inclusion-exclusion: 128 + 64 - 32 = 160.
Q: What is the coefficient of x³y⁴ in (x + y)⁷?
A: C(7, 4) = 35.
Q: How many non-negative integer solutions does x + y + z = 15 have?
A: Stars and bars: C(15 + 3 - 1, 3 - 1) = C(17, 2) = 136.
Q: Among 50 people, what is the minimum number guaranteed to share a birth month?
A: ⌈50/12⌉ = 5.
Counting is the prerequisite for discrete probability (Chapter 7), where p(E) = |E| / |S| requires you to count both E and S. Permutations and combinations appear in algorithm analysis when counting the number of possible inputs. The pigeonhole principle is used in proofs throughout number theory and graph theory.
counting principles, product rule, sum rule, subtraction rule, division rule, inclusion-exclusion, pigeonhole principle, generalized pigeonhole, permutation, combination, r-permutation, r-combination, factorial, binomial coefficient, n choose k, binomial theorem, Pascal's triangle, Pascal's identity, permutations with repetition, combinations with repetition, stars and bars, multiset, HONOLULU, SUCCESS, CS 182, Purdue, discrete math, combinatorics