Combinatorics
Introduction
Combinatorics is the mathematics of counting. How many ways can something happen? How many arrangements exist? These questions arise constantly in computer science: analyzing algorithm complexity, calculating probabilities, and understanding data structures.
Learning Objectives
By the end of this reading, you will be able to:
- Apply fundamental counting principles
- Calculate permutations and combinations
- Use the binomial theorem
- Solve problems with repetition and restrictions
- Apply the pigeonhole principle
1. Fundamental Counting Principles
Product Rule (AND)
If task A can be done in m ways AND task B can be done in n ways, then doing both can be done in m × n ways.
Example: A restaurant offers 3 appetizers and 5 entrees. How many different two-course meals are possible? 3 × 5 = 15 meals
Sum Rule (OR)
If task A can be done in m ways OR task B can be done in n ways (mutually exclusive), then doing one or the other can be done in m + n ways.
Example: A student can choose from 4 math courses OR 3 science courses. How many choices? 4 + 3 = 7 choices
Subtraction Rule (Complement)
To count items with property P, sometimes it's easier to count all items and subtract those without P.
|P| = |Total| - |not P|
Example: How many 3-digit numbers have at least one digit 5? Total 3-digit numbers: 900 (100-999) Numbers with no 5: 8 × 9 × 9 = 648 (first digit: 1-9 except 5) Numbers with at least one 5: 900 - 648 = 252
Division Rule
If a task can be done in n ways, but there are d ways to get each distinct outcome, then there are n/d distinct outcomes.
Example: How many ways to seat 4 people at a round table? Linear arrangements: 4! = 24 But rotations are equivalent, and there are 4 rotations. Distinct arrangements: 24/4 = 6
2. Permutations
A permutation is an ordered arrangement of objects.
Permutations of n distinct objects
The number of ways to arrange n distinct objects is:
n! = n × (n-1) × (n-2) × ... × 2 × 1
Example: Arrange letters A, B, C, D 4! = 24 arrangements
Permutations of r objects from n
The number of ways to arrange r objects from n distinct objects is:
P(n, r) = n!/(n-r)!
Example: How many ways can 3 people finish 1st, 2nd, 3rd in a race of 10? P(10, 3) = 10!/7! = 10 × 9 × 8 = 720
Permutations with Repetition
If we have n objects where n₁ are identical of type 1, n₂ are identical of type 2, etc.:
n!/(n₁! × n₂! × ... × nₖ!)
Example: Arrangements of MISSISSIPPI
- Total letters: 11
- M: 1, I: 4, S: 4, P: 2
11!/(1! × 4! × 4! × 2!) = 39,916,800/(1 × 24 × 24 × 2) = 34,650
3. Combinations
A combination is an unordered selection of objects.
Combinations of r objects from n
The number of ways to choose r objects from n (order doesn't matter):
C(n, r) = n!/[r!(n-r)!]
Also written as "n choose r" or $\binom{n}{r}$
Example: How many ways to choose 3 students from 10 for a committee? C(10, 3) = 10!/(3! × 7!) = (10 × 9 × 8)/(3 × 2 × 1) = 120
Key Properties
- C(n, 0) = C(n, n) = 1
- C(n, 1) = C(n, n-1) = n
- C(n, r) = C(n, n-r) (symmetry)
- C(n, r) = C(n-1, r-1) + C(n-1, r) (Pascal's identity)
Pascal's Triangle
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Each entry is C(row, position)
Each entry = sum of two entries above it
4. The Binomial Theorem
(x + y)ⁿ = Σₖ₌₀ⁿ C(n, k) × xⁿ⁻ᵏ × yᵏ
Example: (x + y)⁴ = x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴
Coefficients come from row 4 of Pascal's triangle: 1, 4, 6, 4, 1
Useful Corollaries
Setting x = y = 1: 2ⁿ = Σₖ₌₀ⁿ C(n, k) (Sum of entries in row n of Pascal's triangle)
Setting x = 1, y = -1: 0 = Σₖ₌₀ⁿ (-1)ᵏ C(n, k) (Alternating sum equals 0)
5. Counting with Repetition
Permutations with Repetition (Sequences)
When choosing r items from n with repetition allowed, order matters:
nʳ
Example: 4-digit PIN using digits 0-9 10⁴ = 10,000 possible PINs
Combinations with Repetition (Multisets)
When choosing r items from n types with repetition, order doesn't matter:
C(n + r - 1, r) = C(n + r - 1, n - 1)
Also called "stars and bars" formula.
Example: How many ways to buy 5 donuts from 3 varieties? C(3 + 5 - 1, 5) = C(7, 5) = 21
Stars and Bars Intuition: Represent 5 donuts as ⭐⭐⭐⭐⭐ and use 2 bars to divide into 3 groups: ⭐⭐|⭐|⭐⭐ means 2 glazed, 1 chocolate, 2 cream
We're arranging 5 stars and 2 bars: C(7, 2) = 21
6. Inclusion-Exclusion Principle
For counting elements in unions of sets:
|A ∪ B| = |A| + |B| - |A ∩ B|
|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
Example: How many integers from 1-100 are divisible by 2 or 3?
- Divisible by 2: ⌊100/2⌋ = 50
- Divisible by 3: ⌊100/3⌋ = 33
- Divisible by 6: ⌊100/6⌋ = 16
Answer: 50 + 33 - 16 = 67
7. The Pigeonhole Principle
If n items are placed into m containers where n > m, at least one container must have more than one item.
Generalized Form
If n items are placed into m containers, at least one container has at least ⌈n/m⌉ items.
Examples
Example 1: In any group of 13 people, at least 2 share a birth month. (13 people, 12 months)
Example 2: In any group of 367 people, at least 2 share a birthday. (367 people, 366 possible days)
Example 3: In any set of 6 integers, at least 2 have the same remainder mod 5. (6 integers, 5 possible remainders)
Example 4: If you have 5 points inside a unit square, at least 2 are within √2/2 of each other. (Divide square into 4 quarters; 5 points, 4 quarters → 2 in same quarter)
8. Application to Computer Science
Algorithm Analysis
# How many comparisons in bubble sort?
# For n elements, we make at most:
# (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparisons
# This is C(n, 2) - choosing 2 elements to compare
def bubble_sort(arr):
n = len(arr)
comparisons = 0
for i in range(n):
for j in range(n - i - 1):
comparisons += 1
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return comparisons
# For n=10: C(10,2) = 45 comparisons
Password Strength
# Calculate password possibilities
def password_combinations(length, char_types):
"""
char_types: dict of character types and their counts
"""
total_chars = sum(char_types.values())
# Permutations with repetition
return total_chars ** length
# Example: 8-character password
chars = {
'lowercase': 26,
'uppercase': 26,
'digits': 10,
'special': 32
}
possibilities = password_combinations(8, chars)
# 94^8 = 6,095,689,385,410,816 possibilities
Hash Table Collisions (Pigeonhole)
# Birthday paradox - probability of hash collision
import math
def collision_probability(n_items, n_buckets):
"""
Probability that at least 2 of n_items hash to same bucket
"""
if n_items > n_buckets:
return 1.0
# Probability of no collision
prob_no_collision = 1.0
for i in range(n_items):
prob_no_collision *= (n_buckets - i) / n_buckets
return 1 - prob_no_collision
# With 23 people and 365 days: ~50% chance of shared birthday
print(collision_probability(23, 365)) # ≈ 0.507
Generating Combinations
from itertools import combinations, permutations
# All combinations of 3 items from [1,2,3,4]
items = [1, 2, 3, 4]
print(list(combinations(items, 3)))
# [(1,2,3), (1,2,4), (1,3,4), (2,3,4)]
# All permutations of 2 items from [1,2,3]
items = [1, 2, 3]
print(list(permutations(items, 2)))
# [(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)]
# Generate all subsets (power set)
def power_set(s):
result = []
for r in range(len(s) + 1):
result.extend(combinations(s, r))
return result
print(power_set([1, 2, 3]))
# [(), (1,), (2,), (3,), (1,2), (1,3), (2,3), (1,2,3)]
Counting Binary Trees
The number of structurally different binary trees with n nodes is the nth Catalan number:
Cₙ = C(2n, n)/(n+1)
def catalan(n):
"""nth Catalan number"""
if n <= 1:
return 1
# C(2n, n) / (n + 1)
numerator = 1
for i in range(n + 1, 2 * n + 1):
numerator *= i
denominator = 1
for i in range(1, n + 1):
denominator *= i
return numerator // (denominator * (n + 1))
# Number of binary trees with n nodes
for n in range(6):
print(f"n={n}: {catalan(n)} trees")
# n=0: 1, n=1: 1, n=2: 2, n=3: 5, n=4: 14, n=5: 42
9. Common Problem Patterns
"At Least One" Problems
Use complement: P(at least one) = 1 - P(none)
Example: Probability that 4-digit number has at least one 7?
- Total: 9000 (1000-9999)
- No 7s: 8 × 9³ = 5832
- At least one 7: 9000 - 5832 = 3168
"Exactly k" Problems
Often use combinations.
Example: Probability of exactly 3 heads in 5 coin flips?
- Favorable: C(5, 3) = 10 ways to choose which 3 flips are heads
- Total: 2⁵ = 32 outcomes
- Probability: 10/32 = 5/16
Distribution Problems
Distinct objects to distinct boxes: n! / (product of box sizes) Identical objects to distinct boxes: Stars and bars Distinct objects to identical boxes: Stirling numbers
Exercises
Basic
How many 5-letter "words" can be formed from {A, B, C, D, E} if:
- Letters can repeat?
- Letters cannot repeat?
A committee of 5 is formed from 8 men and 6 women. How many ways if:
- No restrictions?
- Must include exactly 2 women?
How many arrangements of ARRANGEMENT are there?
Intermediate
How many ways can 10 identical balls be placed in 4 distinct boxes?
How many 8-bit strings have exactly three 1s?
In how many ways can 5 distinct books be distributed to 3 students if each student gets at least one book?
Advanced
Prove: C(n, 0)² + C(n, 1)² + ... + C(n, n)² = C(2n, n)
How many integers from 1 to 1000 are not divisible by 2, 3, or 5?
Prove that in any group of 6 people, there are either 3 mutual friends or 3 mutual strangers. (Hint: Pigeonhole + cases)
Summary
- Product rule: multiply independent choices
- Sum rule: add mutually exclusive choices
- Permutations: ordered arrangements (n! or P(n,r))
- Combinations: unordered selections (C(n,r))
- With repetition: nʳ for sequences, C(n+r-1,r) for multisets
- Inclusion-exclusion: count unions by adding and subtracting overlaps
- Pigeonhole: n items in m containers → some container has multiple