Discrete Maths: Elementary counting principles (chapter 1) – ethiotemari.com

📘 Chapter 1: Elementary counting principles – the backbone of combinatorics

Hello, dear student! 🇪🇹 Welcome to your first step in discrete mathematics. Counting might sound simple, but in combinatorics we count huge possibilities systematically. By the end of this lesson you’ll master the two pillars: addition and multiplication principles. I’ll give you everything you need for your Mid, Final or even Exit Exam – with examples, exercises and hidden answers (click to check yourself!).

👩🏫 Remember: We’re not just counting fingers – we’re counting outcomes, choices, passwords, license plates. Stay curious, and let’s dive!

1.1 Basic counting principles – the two rules that rule them all

➕ Addition principle (the “or” rule)

📌 If event E₁ can happen in e₁ ways, E₂ in e₂ ways, … , Eₙ in eₙ ways, and no two events can occur together (they are mutually exclusive), then the total ways = e₁ + e₂ + … + eₙ.

Think of it as: you go to a café and can order one drink or one cake. If there are 5 drinks and 7 cakes, you have 5 + 7 = 12 different choices (because you never take both). In set language: disjoint sets → add sizes.

🧪 Example 1 (typical exam style): A student can choose one project from three lists. List A: 23 projects, list B: 15, list C: 19. No project appears twice. How many total projects to choose from?
➕ Solution: 23 + 15 + 19 = 57 projects.
(Using addition principle because the lists are disjoint.)

🎲 Example 2: Roll two distinguishable dice. In how many ways can we get sum 4 OR sum 8?
• Sum 4: (1,3), (2,2), (3,1) → 3 ways.
• Sum 8: (2,6), (3,5), (4,4), (5,3), (6,2) → 5 ways.
They are disjoint (a roll can’t sum both), so total = 3 + 5 = 8.

✖️ Multiplication principle (the “and” rule – tasks in sequence)

📌 If a task T₁ can be done in e₁ ways, T₂ in e₂ ways, … , Tₙ in eₙ ways (each after the previous), then the number of ways the whole sequence can happen = e₁ · e₂ · … · eₙ.

Example: choose a password: first choose a letter (26 ways) and then choose a digit (10 ways) → 26 × 10 = 260 possibilities.

🧪 Example 3 (Ethiopian ministry exam style): A man, woman, boy and girl are to be selected from 5 men, 6 women, 2 boys, 4 girls. How many selections?
✖️ This is a sequence of independent choices: 5 × 6 × 2 × 4 = 240 ways.
(Multiplication principle because we choose one from each category.)

┌────┐ ┌────┐ ┌────┐ ┌────┐ │ 5 │ → │ 6 │ → │ 2 │ → │ 4 │ = 240 └────┘ └────┘ └────┘ └────┘ (choose man) (woman) (boy) (girl)

🔐 Example 4 – passwords (very common exam question): A computer password is 6–8 characters, each an uppercase letter or a digit. At least one digit. How many possible passwords?
Step 1 – total without restriction: each char 26+10=36 choices.
For length 6: 36⁶, length 7: 36⁷, length 8: 36⁸.
Step 2 – subtract those with no digit (all letters): 26⁶, 26⁷, 26⁸.
Step 3 – add them: P = (36⁶−26⁶)+(36⁷−26⁷)+(36⁸−26⁸) = 2 684 483 063 360.

Length	Total (36ⁿ)	all letters (26ⁿ)	at least one digit
6	2 176 782 336	308 915 776	1 867 866 560
7	78 364 164 096	8 031 810 176	70 332 353 920
8	2 821 109 907 456	208 827 064 576	2 612 282 842 880

Sometimes both rules work together. For example: two‑digit numbers with distinct nonzero digits. You can count directly by multiplication: tens digit (9 ways) × units digit (8 ways) = 72.
Or by addition: total two‑digit numbers (90) minus those with zero (9) minus those with equal digits (9) = 72. Both give same answer.

✍️ Exam‑style questions – test yourself (answers hidden – click!)

1️⃣ A class has 8 male and 6 female students. In how many ways can we select one class representative (either a boy or a girl)?

A) 48 B) 14 C) 20 D) 56

Correct: B) 14
Addition principle: 8+6 = 14 (choose one from disjoint groups).

2️⃣ How many different license plates can be made with 2 different letters followed by 3 different digits? (alphabet 26 letters, digits 0‑9, repetition not allowed for letters nor digits)

A) 26·25·10·9·8 B) 26·26·10·10·10 C) 26·25·10·10·10 D) 26·26·10·9·8

Correct: A) 26·25·10·9·8
Step1: 1st letter 26 ways, 2nd letter 25 (different). Step2: 1st digit 10 ways, 2nd digit 9, 3rd digit 8 (all distinct). Multiplication rule gives that product.

3️⃣ (exit‑exam style) How many 5‑digit numbers neither start with zero nor end with zero?

A) 9·10·10·10·9 B) 9·10·10·10·10 C) 9·9·8·7·6 D) 8·10·10·10·9

Correct: A) 9·10·10·10·9
First digit: 1‑9 (9 ways). Middle three digits: each 0‑9 (10 ways). Last digit: cannot be zero, so 1‑9 (9 ways). Multiply → 9·10·10·10·9.

4️⃣ (work‑out) In how many ways can we get a sum of 8 when two indistinguishable dice are rolled? An even sum?

Part a – sum 8: possible unordered pairs: (2,6), (3,5), (4,4) → 3 ways.
Part b – even sum: outcomes: (1,1),(1,3),(1,5),(2,2),(2,4),(2,6),(3,3),(3,5),(4,4),(4,6),(5,5),(6,6) → 12 ways.
(Hint: use symmetry – even sum occurs exactly half of the 36 ordered pairs, but dice are identical so careful counting needed.)

📚 Exercise 1.1 (from your module) – selected answers

Problem 1: A→B (2 ways), B→C (5), C→D (3) → travel A to D = 2·5·3 = 30 ways.

Problem 2: digits {2,3,5,6,7,9}
a) three‑digit numbers (reps not allowed) = 6·5·4 = 120.
b) less than 400 → first digit 2 or 3 (2 ways), then any 2 of remaining → 2·5·4 = 40.
c) even → last digit even (2 or 6) → case 1: last=2 (first 5 choices, middle 4) =20; case 2: last=6 (first 5, middle 4)=20 → total 40.

Problem 4: license plates: 2 non‑repeating letters (26·25) followed by 3 even digits {0,2,4,6,8} (even digits, repetition? not specified, so with repetition → 5³ =125) → 26·25·125 = 81 250.

💡 Exam tip: When you see “at least one”, often it’s easier to count total and subtract the complement. For passwords, phone numbers, license plates always check if digits/letters can repeat and if zero is forbidden. Also, “distinct” means use permutation P(n,r) later, but for now multiplication rule is your friend.

📌 Important points – at a glance

Addition principle (OR): disjoint events → sum of individual ways.
Multiplication principle (AND): sequential tasks → multiply possibilities.
Both together: break problem into disjoint cases (add) and inside each case count step by step (multiply).
Zero restriction: “numbers cannot start with zero” – first digit choices reduce.
Common exam trick: “at least one special character” = total without restriction minus the case with no special characters.

🎯 ASCII set diagram – addition vs multiplication:

Addition: set A (23) set B (15) set C (19) ┌─────┐ ┌─────┐ ┌─────┐ │ 23 │ │ 15 │ │ 19 │ → total 57 └─────┘ └─────┘ └─────┘ Multiplication: (select man, woman, boy, girl) 5 → 6 → 2 → 4 = 240

🤔 You ask: “teacher, how do I know whether to add or multiply?”
Great question! If the choice is this OR that (and they don’t happen together), add. If the process is do this AND then that, multiply. Example: choose a drink (tea or coffee) – addition. Choose a drink AND a cake – multiplication.

⚡ more practice (click to reveal)

5️⃣ How many 2‑digit numbers have distinct and nonzero digits?

9·8 = 72 (tens digit 1‑9, units any of remaining 8).

🌟 Keep practicing – counting is the language of possibilities. See you in the next lesson: permutations! 🌟

Discrete Mathematics and Combinatorics