Combinatorics
Page 1: Basic Counting Principles
🎯 What Is Combinatorics?
Combinatorics is a branch of mathematics concerned with counting - how many ways there are to perform a task, choose, arrange, or organise objects.
💡 Typical questions:
- In how many ways can 5 people be arranged in a row?
- How many 4-digit numbers can be formed?
- In how many ways can 3 students be chosen from 10?
- How many secret codes can be created?
✖️ Multiplication Principle
If a task consists of successive steps:
Step 1 can be done in \(n_1\) ways, step 2 in \(n_2\) ways, etc.…
Total number of ways = \(n_1 \times n_2 \times n_3 \times ...\)
✏️ Example 1: Choosing a meal
A restaurant has 3 starters, 5 main courses, and 2 desserts.
In how many ways can a full meal be composed?
Starter: 3 options
Main course: 5 options
Dessert: 2 options
Total: 3 × 5 × 2 = 30 ways
✏️ Example 2: Secret code
A 4-digit code (0–9), repetition allowed.
How many codes are possible?
First digit: 10 options (0–9)
Second digit: 10 options
Third digit: 10 options
Fourth digit: 10 options
Total: 10 × 10 × 10 × 10 = 10⁴ = 10,000 codes
✏️ Example 3: Code without repetition
A 4-digit code (0–9), no repetition.
First digit: 10 options
Second digit: 9 options (one already chosen)
Third digit: 8 options
Fourth digit: 7 options
Total: 10 × 9 × 8 × 7 = 5,040 codes
➕ Addition Principle
If a task can be done in distinct and separate ways ((either this or that):
Total number of ways = \(n_1 + n_2 + n_3 + ...\)
✏️ Example 4: Choosing a representative
A class has 12 boys and 15 girls. In how many ways can one be chosen one representative?
either a boy (12 options) or a girl (15 options)
Total: 12 + 15 = 27 ways
⚠️ When to multiply and when to add?
| Multiply ("and also") | Add ("or") |
|---|---|
| successive steps | Separate alternatives |
| Choose from each category | Choose from one category |
| "and also", "and then" | "or", "one of" |
🔀 Combining Multiplication and Addition
✏️ Example 5: Even numbers
How many numbers even numbers of 3 digits from digits 1,2,3,4,5 (no repetition)?
Even number → units digit must be 2 or 4
Case 1: units digit = 2
Hundreds: 4 options (1,3,4,5)
Tens: 3 options
Total: 4 × 3 = 12
Case 2: units digit = 4
Hundreds: 4 options (1,2,3,5)
Tens: 3 options
Total: 4 × 3 = 12
Total: 12 + 12 = 24 numbers
✏️ Example 6: Mixed committee
There are 4 teachers and 6 students. In how many ways can a committee of one teacher and one student be chosen?
choose a teacher and also a student (successive steps)
Total: 4 × 6 = 24 ways
🌳 Tree Diagram
A tree diagram is a visual tool for counting all possibilities in an organised way.
✏️ Example 7: Tossing a coin twice
4 Possible outcomes (also 2 × 2 = 4)
✏️ Example 8: Choosing an outfit
Shirts: red, blue | Trousers: black, white, grey
6 combinations (and also 2 × 3 = 6)
🔄 Complement Principle
Sometimes it is easier to count what we do NOT want and subtract:
What we want = everything − what we do not want
✏️ Example 9: Codes with at least one even digit
A 3-digit code (1–9). How many codes with at least one even digit?
Total: 9 × 9 × 9 = 729 codes
No even digits (only odd: 1,3,5,7,9):
5 × 5 × 5 = 125 codes
At least one even digit: 729 − 125 = 604 codes
💡 Exam Tips
"and also": multiplication
"or": addition
"at least": complement
No repetition: count decreases
📝 Summary – Page 1
Multiplication principle: successive steps → multiply
Addition principle: separate alternatives → add
Complement principle: everything − what we do not want