📚 Introduction to Counting
Counting problems arise throughout mathematics and computer science. We must count successful outcomes of experiments, determine probabilities of discrete events, and analyze algorithm complexity. This guide covers the fundamental techniques needed to answer these questions.
- Determining probabilities in discrete events
- Analyzing time complexity of algorithms
- Solving password and security problems
- Understanding combinatorial structures
🔢 Set Theory Fundamentals
Key Definitions
- Set: An unordered collection of distinct objects (elements)
- Empty Set: A set with no elements
- Cardinality |A|: The number of elements in a finite set A
- Union (A ∪ B): The set of all elements in A or B
- Intersection (A ∩ B): The set of all elements in both A and B
🎯 The Four Basic Counting Rules
1. The Sum Rule (OR Rule)
If a first task can be done in n₁ ways and a second task in n₂ ways, and if only one of these tasks can be done (but not both), then there are n₁ + n₂ ways to do either task.
|A ∪ B| = |A| + |B|
Problem: A gallery has 3 German cars in one room and 2 Japanese cars in another room. How many choices do you have to buy a car?
You can choose either a German car OR a Japanese car (not both).
Number of choices = 3 + 2 = 5 choices
Problem: Statement labels in a programming language must be a single letter OR a single decimal digit. How many possible labels are there?
Letters (A-Z): 26 choices
Digits (0-9): 10 choices
Total = 26 + 10 = 36 possible labels
2. The Product Rule (AND Rule)
If a procedure can be broken down into two tasks, where the first task can be done in n₁ ways and the second task in n₂ ways (after the first task has been done), then there are n₁ × n₂ ways to complete the procedure.
|A × B| = |A| × |B|
Problem: You travel from country A to country C through country B. There are 3 ways to go from A to B and 2 ways to go from B to C. How many ways to reach C from A?
You must go from A to B AND then from B to C.
Number of ways = 3 × 2 = 6 ways
Problem: Phone numbers in Riyadh have 7 digits starting with 4 or 2. How many phone lines are possible?
Case 1: Repetition allowed
Position 1: 2 choices (4 or 2)
Positions 2-7: 10 choices each (0-9)
Total = 2 × 10⁶ = 2,000,000 phone lines
Case 2: No repetition
Position 1: 2 choices (4 or 2)
Position 2: 9 choices (can't repeat first digit)
Position 3: 8 choices
And so on...
Total = 2 × 9 × 8 × 7 × 6 × 5 × 4 = 120,960 phone lines
3. The Subtraction Rule (Inclusion-Exclusion)
If a task can be done in n₁ ways or n₂ ways, then the total number of ways is n₁ + n₂ minus the number of ways that are common to both.
|A ∪ B| = |A| + |B| - |A ∩ B|
Problem: A company receives 350 applications. 220 majored in computer science, 147 majored in business, and 51 majored in both. How many majored in neither?
Let A₁ = set of CS majors = 220
Let A₂ = set of business majors = 147
A₁ ∩ A₂ = both majors = 51
|A₁ ∪ A₂| = |A₁| + |A₂| - |A₁ ∩ A₂|
|A₁ ∪ A₂| = 220 + 147 - 51 = 316
Neither major = 350 - 316 = 34 applicants
4. The Division Rule
If a task can be done in n ways, but every outcome can be achieved in d different ways, then the number of distinct outcomes is n/d.
Problem: How many ways can we seat n people around a circular table?
In a line: n! arrangements
Around a circle: Each arrangement can be rotated n ways
Distinct circular arrangements = n!/n = (n-1)!
🤔 Decision Guide: Which Rule to Use?
| Situation | Rule to Use | Key Words |
|---|---|---|
| Tasks are alternatives (can't do both) | Sum Rule | OR, either...or, one of |
| Tasks are sequential (do one then another) | Product Rule | AND, followed by, then |
| Sets overlap (some elements in common) | Subtraction Rule | At least one, some...some, overlap |
| Multiple ways to achieve same outcome | Division Rule | Distinct, unique, different |
🔄 Permutations
What is a Permutation?
A permutation is an ordered arrangement of objects. Order matters!
The number of permutations of r distinct objects chosen from n distinct objects is denoted P(n,r).
P(n,r) = n!/(n-r)!
Special case: P(n,n) = n!
(All n objects arranged in all n positions)
P(n,r) = n × (n-1) × (n-2) × ... × (n-r+1)
- First position: n choices
- Second position: n-1 choices
- r-th position: n-r+1 choices
Problem: How many ways can 3 birds be taken from among 8 birds if order matters?
n = 8, r = 3
P(8,3) = 8!/(8-3)! = 8!/5!
= 8 × 7 × 6 × 5!/5!
= 8 × 7 × 6
= 336 ways
Problem: There are 8 runners in a race. Gold, silver, and bronze medals are awarded. How many different ways can the medals be awarded?
This is a permutation because the order matters (gold ≠ silver ≠ bronze)
P(8,3) = 8!/(8-3)! = 8 × 7 × 6 = 336 ways
🎲 Combinations
What is a Combination?
A combination is an unordered selection of objects. Order doesn't matter!
The number of combinations of r objects chosen from n objects is denoted C(n,r) or (n choose r) or ⁿCᵣ.
C(n,r) = n! / (r!(n-r)!)
Relationship to Permutations:
C(n,r) = P(n,r) / r!
(We divide by r! because order doesn't matter)
Each combination of r objects can be arranged in r! different ways. Since we don't care about order, we divide out these duplicate arrangements.
Problem: How many ways can 2 books be chosen from among 10 books?
n = 10, r = 2
C(10,2) = 10!/(2!(10-2)!)
= 10!/(2! × 8!)
= (10 × 9 × 8!)/(2 × 1 × 8!)
= (10 × 9)/2
= 45 ways
Problem: We need to create a team of 5 players from 10 team members. How many different teams can be created?
Order doesn't matter (a team is just a group of people)
C(10,5) = 10!/(5!(10-5)!)
= 10!/(5! × 5!)
= (10 × 9 × 8 × 7 × 6)/(5 × 4 × 3 × 2 × 1)
= 252 different teams
⚖️ Permutations vs Combinations
| Aspect | Permutation | Combination |
|---|---|---|
| Order | Matters | Doesn't matter |
| Formula | P(n,r) = n!/(n-r)! | C(n,r) = n!/(r!(n-r)!) |
| Example | (a,b) and (b,a) are different | {a,b} and {b,a} are the same |
| Keywords | Arrange, order, sequence | Select, choose, group |
| Result | Always larger | Always smaller |
P(3,2) = 3!/(3-2)! = 6
Combinations: {ab, ac, bc} = 3 selections
C(3,2) = 3!/(2!×1!) = 3
📐 The Binomial Theorem
What is a Binomial?
A binomial is a polynomial that is the sum of two terms, such as (x + y).
(x + y)ⁿ = Σ(k=0 to n) C(n,k) × xⁿ⁻ᵏ × yᵏ
Expanded form:
(x + y)ⁿ = C(n,0)xⁿ + C(n,1)xⁿ⁻¹y + C(n,2)xⁿ⁻²y² + ... + C(n,n)yⁿ
(x + y)⁴ = C(4,0)x⁴ + C(4,1)x³y + C(4,2)x²y² + C(4,3)xy³ + C(4,4)y⁴
= 1x⁴ + 4x³y + 6x²y² + 4xy³ + 1y⁴
= x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴
Problem: What is the coefficient of x¹²y¹³ in the expansion of (2x - 3y)²⁵?
First, rewrite as (2x + (-3y))²⁵
For x¹²y¹³, we need j = 13 in the binomial theorem:
Coefficient = C(25,13) × (2)¹² × (-3)¹³
= [25!/(13!×12!)] × 2¹² × (-3)¹³
= -[25!/(13!×12!)] × 2¹² × 3¹³
🔺 Pascal's Triangle
Pascal's Identity
The binomial coefficients can be arranged in a triangular pattern called Pascal's Triangle.
C(n+1, k) = C(n, k-1) + C(n, k)
Each entry is the sum of the two entries above it.
Pascal's Triangle
- Row n contains the coefficients for (x + y)ⁿ
- Entry at position k in row n is C(n,k)
- Each row is symmetric
- Each entry equals the sum of the two entries above it
- Sum of row n equals 2ⁿ
📋 Quick Reference Guide
All Formulas at a Glance
• Sum Rule: |A ∪ B| = |A| + |B| (if A and B are disjoint)
• Product Rule: |A × B| = |A| × |B|
• Subtraction Rule: |A ∪ B| = |A| + |B| - |A ∩ B|
Permutations:
• P(n,r) = n!/(n-r)!
• P(n,n) = n!
Combinations:
• C(n,r) = n!/(r!(n-r)!)
• C(n,r) = C(n, n-r)
• C(n,0) = C(n,n) = 1
Binomial Theorem:
• (x + y)ⁿ = Σ C(n,k) × xⁿ⁻ᵏ × yᵏ
Factorial:
• n! = n × (n-1) × (n-2) × ... × 3 × 2 × 1
• 0! = 1
Problem-Solving Strategy
- Identify: What are you counting?
- Decide: Does order matter?
- YES → Use permutations
- NO → Use combinations
- Check: Are tasks sequential or alternatives?
- Sequential → Use product rule
- Alternatives → Use sum rule
- Apply: Use the appropriate formula
- Verify: Does your answer make sense?
💪 Practice Problems
A license plate consists of 3 letters followed by 3 digits. How many license plates are possible?
Letters: 26 choices each (3 positions) = 26³
Digits: 10 choices each (3 positions) = 10³
Total = 26³ × 10³ = 17,576,000 plates
From a group of 12 people, how many ways can we select a committee of 5 people?
Order doesn't matter, so use combinations:
C(12,5) = 12!/(5!×7!) = 792 ways
A password must be 8 characters long using lowercase letters. How many passwords are possible if repetition is allowed?
Each position: 26 choices
Total = 26⁸ = 208,827,064,576 passwords