MTH202 — Final Term Summary (Lectures 23–45)

📘 Lecture 23 — Mathematical Induction

📖 Overview: This lecture introduces the Principle of Mathematical Induction, a fundamental proof technique used to verify propositions for all positive integers. It demonstrates the method through multiple examples and exercises, including formulas for sums of integers, series, and set theory laws, establishing why this technique is essential for proving infinite sequences of statements.

🗂️ Topics Covered

The lecture covers the definition and structure of mathematical induction with its basis and inductive steps, followed by detailed proofs of seven different propositions including sum of first n integers, sum of odd numbers, sum of powers of 2, sum of squares, sum of reciprocals of consecutive products, sigma notation with powers of 2, product of fractions, sum involving factorials, and DeMorgan's Law generalization.

📝 Lecture Summary

PRINCIPLE OF MATHEMATICAL INDUCTION

Let P(n) be a propositional function defined for all positive integers n. P(n) is true for every positive integer n if:

1. Basis Step: The proposition P(1) is true.
2. Inductive Step: If P(k) is true then P(k + 1) is true for all integers k ≥ 1. i.e. ∀k P(k) → P(k + 1)

🔑 Definition — Mathematical Induction: A proof technique consisting of two steps: proving the base case (usually n=1) and proving that if the statement holds for n=k, it also holds for n=k+1. 📌 Example: Proving 1 + 2 + 3 + ... + n = n(n+1)/2 for all n ≥ 1

• Basis: n=1: LHS=1, RHS=1(2)/2=1 ✓
• Inductive: Assume true for k: 1+2+...+k = k(k+1)/2
• Prove for k+1: 1+2+...+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2 ✓

EXAMPLE — Sum of Odd Numbers

Prove: 1 + 3 + 5 + ... + (2n - 1) = n² for all n ≥ 1

🔑 Key Identity: Sum of first n odd numbers = n² 📌 Example:

• Basis: n=1: LHS=1, RHS=1²=1 ✓
• Inductive: Assume 1+3+5+...+(2k-1)=k²
• Prove for k+1: 1+3+5+...+(2k-1)+(2k+1) = k² + (2k+1) = (k+1)² ✓

EXAMPLE — Sum of Powers of 2

Prove: 1 + 2 + 2² + ... + 2ⁿ = 2ⁿ⁺¹ - 1 for all n ≥ 0

🔑 Definition — Base case starting at n=0: Induction can start at any integer; here the basis step checks n=0. 📌 Example:

• Basis: n=0: LHS=1, RHS=2⁰⁺¹-1=2-1=1 ✓
• Inductive: Assume 1+2+2²+...+2ᵏ = 2ᵏ⁺¹-1
• Prove for k+1: (1+2+...+2ᵏ)+2ᵏ⁺¹ = (2ᵏ⁺¹-1)+2ᵏ⁺¹ = 2·2ᵏ⁺¹-1 = 2ᵏ⁺²-1 ✓

EXAMPLE — Sum of Squares

Prove: 1² + 2² + 3² + ... + n² = n(n+1)(2n+1)/6 for all n ≥ 1

📐 Formula: ∑ᵢ₌₁ⁿ i² = n(n+1)(2n+1)/6 📌 Example:

• Basis: n=1: LHS=1, RHS=1(2)(3)/6=6/6=1 ✓
• Inductive: Assume 1²+2²+...+k² = k(k+1)(2k+1)/6
• Prove for k+1: Add (k+1)² to both sides and factor to get (k+1)(k+2)(2k+3)/6 ✓

EXAMPLE — Sum of Reciprocals

Prove: 1/(1·2) + 1/(2·3) + ... + 1/[n(n+1)] = n/(n+1) for all n ≥ 1

📌 Example:

• Basis: n=1: LHS=1/(1·2)=1/2, RHS=1/(1+1)=1/2 ✓
• Inductive: Assume sum to k terms = k/(k+1)
• Prove: Add 1/[(k+1)(k+2)] and simplify to get (k+1)/(k+2) ✓

EXAMPLE — Summation with Powers

Prove: ∑ᵢ₌₁ⁿ⁺¹ i·2ⁱ = n·2ⁿ⁺² + 2 for all n ≥ 0

📐 Formula: ∑ᵢ₌₁ⁿ⁺¹ i·2ⁱ = n·2ⁿ⁺² + 2 📌 Example:

• Basis: n=0: ∑ᵢ₌₁¹ i·2ⁱ = 1·2¹=2, RHS=0·2²+2=2 ✓
• Inductive: Assume for k, then add (k+2)·2ᵏ⁺² and factor to prove for k+1 ✓

EXAMPLE — Product of Fractions

Prove: (1-1/2²)(1-1/3²)...(1-1/n²) = (n+1)/(2n) for all n ≥ 2

📌 Example:

• Basis: n=2: LHS=1-1/4=3/4, RHS=(2+1)/(2·2)=3/4 ✓
• Inductive: Multiply assumed product by (1-1/(k+1)²) and simplify to get (k+2)/(2(k+1)) ✓

EXAMPLE — Sum with Factorials

Prove: ∑ᵢ₌₁ⁿ i(i!) = (n+1)! - 1 for all n ≥ 1

🔑 Key Factorial Property: (k+2)(k+1)! = (k+2)! 📌 Example:

• Basis: n=1: LHS=1·1!=1, RHS=2!-1=2-1=1 ✓
• Inductive: Assume ∑ᵢ₌₁ᵏ i(i!) = (k+1)!-1
• Prove: Add (k+1)(k+1)! and factor to get (k+2)(k+1)!-1 = (k+2)!-1 ✓

EXAMPLE — DeMorgan's Law Generalization

Prove: (∩ⱼ₌₁ⁿ Aⱼ)' = ∪ⱼ₌₁ⁿ Aⱼ' where A₁,...,Aₙ are subsets of U and n ≥ 2

🔑 Definition — Complement: A' represents the complement of set A (elements not in A). 📌 Example:

• Basis: n=2: Uses basic DeMorgan's Law (A₁ ∩ A₂)' = A₁' ∪ A₂' ✓
• Inductive: Assume true for k sets. For k+1 sets, write (∩ⱼ₌₁ᵏ⁺¹ Aⱼ)' = ((∩ⱼ₌₁ᵏ Aⱼ) ∩ Aₖ₊₁)' and apply basic DeMorgan's Law, then use inductive hypothesis to get ∪ⱼ₌₁ᵏ⁺¹ Aⱼ' ✓

⭐ Key Takeaways

The Principle of Mathematical Induction is a rigorous two-step proof method: first verify the base case (often n=1), then prove the inductive step showing that truth for P(k) implies truth for P(k+1). Mastering this technique requires practicing with various types of propositions including arithmetic series, factorial expressions, set theory identities, and sigma notation. The key algebraic skill is manipulating expressions from the inductive hypothesis to match the desired form for k+1. Always verify that the algebraic manipulation correctly demonstrates the equivalence between the assumed form and the target form.

🧠 Quick Revision Questions

1. What are the two essential steps in a proof by mathematical induction?
2. How would you prove 2 + 4 + 6 + ... + 2n = n(n+1) using induction?
3. Why can mathematical induction start at n=0 instead of n=1?
4. In the sum of squares proof, what algebraic manipulation converts k(k+1)(2k+1)/6 + (k+1)² into (k+1)(k+2)(2k+3)/6?
5. How does the inductive hypothesis for DeMorgan's Law help prove the statement for k+1 sets?

📘 Lecture 24 — Mathematical Induction for Divisibility

📖 Overview: This lecture covers the application of mathematical induction to prove divisibility statements and inequalities, as well as properties of recursively defined sequences. It demonstrates the structured two-step proof process—basis step and inductive step—essential for establishing truths about all positive integers.

🗂️ Topics Covered

The lecture covers mathematical induction for divisibility problems, including proofs that n³−n is divisible by 3 and 6, that 2²ⁿ−1 is divisible by 3, that the product of two consecutive integers is divisible by 2, and that xⁿ−yⁿ is divisible by x−y. It also covers proving inequalities like 2n+1 < 2ⁿ and 1+nx ≤ (1+x)ⁿ, and proving properties of recursively defined sequences.

📝 Lecture Summary

MATHEMATICAL INDUCTION FOR DIVISIBILITY PROBLEMS INEQUALITY PROBLEMS

DIVISIBILITY:

Let n and d be integers and d ≠ 0. Then n is divisible by d or d divides n, written d | n, iff n = d·k for some integer k.

Alternatively, we say that: n is a multiple of d, d is a divisor of n, d is a factor of n.

Thus d|n ⇔ ∃ an integer k such that n = d·k

🔑 Definition — Divisibility: An integer n is divisible by an integer d (d ≠ 0) if there exists an integer k such that n = d·k.

EXERCISE: Use mathematical induction to prove that n³ - n is divisible by 3 whenever n is a positive integer.

SOLUTION:

1. Basis Step: For n = 1, n³ - n = 1³ - 1 = 1 - 1 = 0. Since 0 = 0·3, it is divisible by 3. Therefore, the statement is true for n = 1.

2. Inductive Step: Suppose the statement is true for n = k, i.e., k³ - k is divisible by 3 for all n ∈ Z⁺. Then k³ - k = 3·q for some q ∈ Z. We need to prove that (k+1)³ - (k+1) is divisible by 3. Now (k+1)³ - (k+1) = (k³ + 3k² + 3k + 1) - (k + 1) = k³ + 3k² + 2k = (k³ - k) + 3k² + 2k + k = (k³ - k) + 3k² + 3k = 3·q + 3·(k² + k) = 3[q + k² + k]. ⇒ (k+1)³ - (k+1) is divisible by 3. Hence, by mathematical induction, n³ - n is divisible by 3 whenever n is a positive integer.

📐 Formula for inductive step manipulation: (k+1)³ - (k+1) = (k³ - k) + 3k(k+1)

EXAMPLE: Use mathematical induction to prove that for all integers n ≥ 1, 2²ⁿ - 1 is divisible by 3.

SOLUTION: Let P(n): 2²ⁿ - 1 is divisible by 3.

1. Basis Step: P(1) is true. Now P(1): 2²⁽¹⁾ - 1 = 4 - 1 = 3, which is divisible by 3. Hence P(1) is true.

2. Inductive Step: Suppose P(k) is true, i.e., 2²ᵏ - 1 is divisible by 3. Then ∃ integer q such that 2²ᵏ - 1 = 3·q. To prove P(k+1) is true, i.e., 2²⁽ᵏ⁺¹⁾ - 1 is divisible by 3. Now consider 2²⁽ᵏ⁺¹⁾ - 1 = 2²ᵏ⁺² - 1 = 2²ᵏ·2² - 1 = 2²ᵏ·4 - 1 = 2²ᵏ(3+1) - 1 = 2²ᵏ·3 + (2²ᵏ - 1) = 2²ᵏ·3 + 3·q = 3(2²ᵏ + q). ⇒ 2²⁽ᵏ⁺¹⁾ - 1 is divisible by 3. Accordingly, by mathematical induction, 2²ⁿ - 1 is divisible by 3 for all integers n ≥ 1.

📐 Key manipulation: 4 = 3 + 1, allowing expression in terms of the inductive hypothesis.

EXERCISE: Use mathematical induction to show that the product of any two consecutive positive integers is divisible by 2.

SOLUTION: Let n and n + 1 be two consecutive integers. We need to prove that n(n+1) is divisible by 2.

1. Basis Step: For n = 1, n(n+1) = 1·(1+1) = 1·2 = 2, which is divisible by 2.

2. Inductive Step: Suppose the statement is true for n = k, i.e., k(k+1) is divisible by 2, for some k ∈ Z⁺. Then k(k+1) = 2·q, q ∈ Z⁺. We must show that (k+1)(k+2) is divisible by 2. Consider (k+1)(k+2) = (k+1)k + (k+1)2 = 2q + 2(k+1) = 2(q + k + 1). Hence (k+1)(k+2) is divisible by 2. Accordingly, by mathematical induction, the product of any two consecutive positive integers is divisible by 2.

📌 Example: For n = 3, product = 3·4 = 12 = 2·6, divisible by 2.

EXERCISE: Prove by mathematical induction n³ - n is divisible by 6, for each integer n ≥ 2.

SOLUTION:

1. Basis Step: For n = 2, n³ - n = 2³ - 2 = 8 - 2 = 6 = 1·6, which is divisible by 6. Therefore, the statement is true for n = 2.

2. Inductive Step: Suppose the statement is true for n = k, i.e., k³ - k is divisible by 6, for all integers k ≥ 2. Then k³ - k = 6·q for some q ∈ Z. We need to prove that (k+1)³ - (k+1) is divisible by 6. Now (k+1)³ - (k+1) = (k³ + 3k³ + 3k + 1) - (k+1) = k³ + 3k³ + 2k = (k³ - k) + (3k³ + 2k + k) = (k³ - k) + 3k³ + 3k = 6·q + 3k(k+1).

Since k is an integer, k(k+1) is the product of two consecutive integers and is therefore even. Let k(k+1) = 2r, r ∈ Z.

Now equation becomes: (k+1)³ - (k+1) = 6·q + 3·2r = 6q + 6r = 6(q + r), q, r ∈ Z. ⇒ (k+1)³ - (k+1) is divisible by 6. Hence, by mathematical induction, n³ - n is divisible by 6 for each integer n ≥ 2.

🔑 Key insight: The proof uses the previously proven result that the product of two consecutive integers is divisible by 2.

EXERCISE: Prove by mathematical induction. For any integer n ≥ 1, xⁿ - yⁿ is divisible by x - y, where x and y are any two integers with x ≠ y.

SOLUTION:

1. Basis Step: For n = 1, xⁿ - yⁿ = x¹ - y¹ = x - y, which is divisible by x - y. So, the statement is true for n = 1.

2. Inductive Step: Suppose the statement is true for n = k, i.e., xᵏ - yᵏ is divisible by x - y. We need to prove that xᵏ⁺¹ - yᵏ⁺¹ is divisible by x - y. Now xᵏ⁺¹ - yᵏ⁺¹ = xᵏ·x - yᵏ·y = xᵏ·x - x·yᵏ + x·yᵏ - yᵏ·y (introducing x·yᵏ) = (xᵏ - yᵏ)·x + yᵏ·(x - y). The first term (xᵏ - yᵏ) is divisible by x - y by inductive hypothesis. The second term contains a factor (x - y), so it is also divisible by x - y. Thus xᵏ⁺¹ - yᵏ⁺¹ is divisible by x - y. Hence, by mathematical induction, xⁿ - yⁿ is divisible by x - y for any integer n ≥ 1.

📐 Formula: xᵏ⁺¹ - yᵏ⁺¹ = (xᵏ - yᵏ)·x + yᵏ·(x - y)

💡 Why this matters: This is a fundamental algebraic identity used in factoring differences of powers.

PROVING AN INEQUALITY: Use mathematical induction to prove that for all integers n ≥ 3, 2n + 1 < 2ⁿ

SOLUTION:

1. Basis Step: For n = 3, L.H.S = 2(3) + 1 = 6 + 1 = 7. R.H.S = 2³ = 8. Since 7 < 8, the statement is true for n = 3.

2. Inductive Step: Suppose the statement is true for n = k, i.e., 2k + 1 < 2ᵏ, k ≥ 3. We need to show it's true for n = k+1: 2(k+1) + 1 < 2ᵏ⁺¹. Consider L.H.S = 2(k+1) + 1 = 2k + 2 + 1 = (2k + 1) + 2 < 2ᵏ + 2 (using (1)). Since 2 < 2ᵏ for k ≥ 3, we have 2ᵏ + 2 < 2ᵏ + 2ᵏ = 2·2ᵏ = 2ᵏ⁺¹. Thus 2(k+1) + 1 < 2ᵏ⁺¹ (proved).

EXERCISE: Show by mathematical induction 1 + nx ≤ (1+x)ⁿ for all real numbers x > -1 and integers n ≥ 2

SOLUTION:

1. Basis Step: For n = 2, L.H.S = 1 + 2x. R.H.S = (1 + x)² = 1 + 2x + x² > 1 + 2x (since x² > 0). ⇒ Statement is true for n = 2.

2. Inductive Step: Suppose the statement is true for n = k, i.e., for k ≥ 2, 1 + kx ≤ (1+x)ᵏ. We want to show: 1 + (k+1)x ≤ (1+x)ᵏ⁺¹. Since x > -1, therefore 1 + x > 0. Multiplying both sides of the inductive hypothesis by (1+x) gives: (1+x)(1+x)ᵏ ≥ (1+x)(1+kx) = 1 + kx + x + kx² = 1 + (k+1)x + kx². Since x > -1, x² ≥ 0, and k ≥ 2 ⇒ kx² ≥ 0, we have (1+x)(1+x)ᵏ ≥ 1 + (k+1)x. Thus 1 + (k+1)x ≤ (1+x)ᵏ⁺¹. Hence, by mathematical induction, the inequality is true.

🔑 Definition — Bernoulli's Inequality: For all real numbers x > -1 and integers n ≥ 2, 1 + nx ≤ (1+x)ⁿ.

PROVING A PROPERTY OF A SEQUENCE: Define a sequence a₁, a₂, a₃, ... as follows: a₁ = 2, aₖ = 5aₖ₋₁ for all integers k ≥ 2. Use mathematical induction to show that the terms of the sequence satisfy the formula aₙ = 2·5ⁿ⁻¹ for all integers n ≥ 1.

SOLUTION:

1. Basis Step: For n = 1, the formula gives a₁ = 2·5¹⁻¹ = 2·5⁰ = 2·1 = 2, which confirms the definition of the sequence. Hence, the formula is true for n = 1.

2. Inductive Step: Suppose the formula is true for n = k, i.e., aₖ = 2·5ᵏ⁻¹ for some integer k ≥ 1. We show the statement is also true for n = k+1: aₖ₊₁ = 2·5ᵏ⁺¹⁻¹ = 2·5ᵏ. Now aₖ₊₁ = 5·aₖ₊₁₋₁ (by definition) = 5·aₖ = 5·(2·5ᵏ⁻¹) = 2·(5·5ᵏ⁻¹) = 2·5ᵏ⁺¹⁻¹ = 2·5ᵏ, which was required.

📌 Example: For a geometric sequence with a₁ = 2 and common ratio 5, a₃ = 2·5² = 50. Verification: a₁ = 2, a₂ = 5·2 = 10, a₃ = 5·10 = 50.

EXERCISE: A sequence d₁, d₂, d₃, ... is defined by letting d₁ = 2 and dₖ = dₖ₋₁/k for all integers k ≥ 2. Show that dₙ = 2/n! for all integers n ≥ 1, using mathematical induction.

SOLUTION:

1. Basis Step: For n = 1, the formula gives d₁ = 2/1! = 2/1 = 2, which agrees with the definition of the sequence.

2. Inductive Step: Suppose the formula is true for n = k, i.e., dₖ = 2/k! for some integer k ≥ 1. We must show that dₖ₊₁ = 2/(k+1)!. Now, by the definition of the sequence, dₖ₊₁ = d₍ₖ₊₁₎₋₁/(k+1) = dₖ/(k+1) = (2/k!)/(k+1) = 2/((k+1)k!) = 2/(k+1)!. Hence the formula is also true for n = k+1. Accordingly, the given formula defines all the terms of the sequence recursively.

📐 Formula: dₙ = 2/n! for all n ≥ 1

EXERCISE: Prove by mathematical induction that 1 + 1/4 + 1/9 + ⋯ + 1/n² < 2 - 1/n whenever n is a positive integer greater than 1.

SOLUTION:

1. Basis Step: For n = 2, L.H.S = 1 + 1/4 = 5/4 = 1.25. R.H.S = 2 - 1/2 = 3/2 = 1.5. Clearly LHS < RHS. Hence the statement is true for n = 2.

2. Inductive Step: Suppose the statement is true for some integer k > 1, i.e., 1 + 1/4 + 1/9 + ⋯ + 1/k² < 2 - 1/k. We need to show the statement is true for n = k+1: 1 + 1/4 + 1/9 + ⋯ + 1/(k+1)² < 2 - 1/(k+1).

Consider LHS for k+1 = (1 + 1/4 + ⋯ + 1/k²) + 1/(k+1)² < (2 - 1/k) + 1/(k+1)² = 2 - (1/k - 1/(k+1)²).

We need to prove: 2 - (1/k - 1/(k+1)²) ≤ 2 - 1/(k+1), or equivalently: 1/k - 1/(k+1)² ≥ 1/(k+1), or 1/k - 1/(k+1) ≥ 1/(k+1)².

Now 1/k - 1/(k+1) = (k+1 - k)/k(k+1) = 1/k(k+1) > 1/(k+1)², proving the inequality.

⭐ Key Takeaways

The core technique for proving divisibility by induction involves showing the base case is true, then assuming the statement holds for n=k to rewrite (k+1)³ - (k+1) in terms of k³-k plus additional multiples of the divisor. For inequalities, the inductive step often requires bounding expressions using the inductive hypothesis combined with simple inequalities like 2 < 2ᵏ for k≥3. For recursively defined sequences, the inductive proof confirms that the closed-form formula satisfies both the base condition and the recurrence relation, with the inductive hypothesis used to replace aₖ with its formulaic expression. A powerful technique for proving xⁿ-yⁿ is divisible by x-y involves introducing the term x·yᵏ to factor the expression into (xᵏ-yᵏ)·x + yᵏ·(x-y).

🧠 Quick Revision Questions

1. State the definition of divisibility and express "d divides n" symbolically.

2. Show the key algebraic manipulation used to prove n³-n is divisible by 3 using the inductive hypothesis.

3. In proving 2²ⁿ-1 is divisible by 3, explain why 2²ᵏ·4 can be rewritten as 2²ᵏ·3 + 2²ᵏ and why this is helpful.

4. How do you prove that the product of two consecutive integers is even, and why is this result needed in the proof that n³-n is divisible by 6?

5. Write the expression xᵏ⁺¹ - yᵏ⁺¹ in terms of (xᵏ - yᵏ) and (x - y), and explain why this proves divisibility by x - y.

📘 Lecture 25 — Methods of Proof

📖 Overview: This lecture introduces fundamental methods of proof used in mathematics and computer science. It focuses on direct proof and disproof by counterexample, explaining how to prove implications (p → q) by showing that if p is true, then q must also be true, and how to disprove false statements with a single counterexample.

🗂️ Topics Covered

The lecture covers the introduction to methods of proof, including direct proof, indirect proof (proof by contraposition and proof by contradiction). It defines basic mathematical concepts like even, odd, prime, composite, rational numbers, divisibility, and perfect squares. Several exercises demonstrate direct proof techniques for properties of integers, rational numbers, and divisibility. Finally, the lecture explains disproof by counterexample with multiple examples.

📝 Lecture Summary

METHODS OF PROOF

Many theorems in mathematics are implications, p → q. The techniques of proving implications give rise to different methods of proofs. A direct proof proves p → q by showing that if p is true, then q must also be true, showing that the combination p true and q false never occurs. Other methods include proof by contraposition (p → q ≡ ~q → ~p) and proof by contradiction (p → q ≡ (p ∧ ~q) → c).

SOME BASICS:

1. An integer n is even if, and only if, n = 2k for some integer k.
2. An integer n is odd if, and only if, n = 2k + 1 for some integer k.
3. An integer n is prime if, and only if, n > 1 and for all positive integers r and s, if n = r·s, then r = 1 or s = 1.
4. An integer n > 1 is composite if, and only if, n = r·s for some positive integers r and s with r ≠ 1 and s ≠ 1.
5. A real number r is rational if, and only if, r = a/b for some integers a and b with b ≠ 0.
6. If n and d are integers and d ≠ 0, then d divides n, written d | n if, and only if, n = d·k for some integers k.
7. An integer n is called a perfect square if, and only if, n = k² for some integer k.

EXERCISE: Prove that the sum of two odd integers is even.

🔑 Definition — odd integer: an integer that can be written as 2k + 1 for some integer k. Proof: Let m and n be two odd integers. Then m = 2k + 1 for some k ∈ Z and n = 2l + 1 for some l ∈ Z. Now m + n = (2k + 1) + (2l + 1) = 2k + 2l + 2 = 2(k + l + 1) = 2r where r = (k + l + 1) ∈ Z. Hence m + n is even.

EXERCISE: Prove that if n is any even integer, then (-1)ⁿ = 1

Proof: Suppose n is an even integer. Then n = 2k for some integer k. Now (-1)ⁿ = (-1)²ᵏ = [(-1)²]ᵏ = (1)ᵏ = 1 (proved).

EXERCISE: Prove that the product of an even integer and an odd integer is even.

Proof: Suppose m is an even integer and n is an odd integer. Then m = 2k for some integer k and n = 2l + 1 for some integer l. Now m·n = 2k·(2l + 1) = 2·k(2l + 1) = 2·r where r = k(2l + 1) is an integer. Hence m·n is even.

EXERCISE: Prove that the square of an even integer is even.

Proof: Suppose n is an even integer. Then n = 2k. Now square of n = n² = (2·k)² = 4k² = 2·(2k²) = 2·p where p = 2k² ∈ Z. Hence, n² is even.

EXERCISE: Prove that if n is an odd integer, then n³ + n is even.

Proof: Let n be an odd integer, then n = 2k + 1 for some k ∈ Z. Now n³ + n = n(n² + 1) = (2k + 1)((2k+1)² + 1) = (2k + 1)(4k² + 4k + 1 + 1) = (2k + 1)(4k² + 4k + 2) = (2k + 1)·2·(2k² + 2k + 1) = 2·(2k + 1)(2k² + 2k + 1) = an even integer.

EXERCISE: Prove that, if the sum of any two integers is even, then so is their difference.

Proof: Suppose m and n are integers so that m + n is even. Then m + n = 2k for some integer k ⇒ m = 2k - n. Now m - n = (2k - n) - n = 2k - 2n = 2(k - n) = 2r where r = k - n is an integer. Hence m - n is even.

EXERCISE: Prove that the sum of any two rational numbers is rational.

🔑 Definition — rational number: a real number that can be expressed as a/b for some integers a and b with b ≠ 0. Proof: Suppose r and s are rational numbers. Then r = a/b and s = c/d for some integers a, b, c, d with b ≠ 0 and d ≠ 0. Now r + s = a/b + c/d = (ad + bc)/bd = p/q. Hence r + s is rational, where p = ad + bc ∈ Z and q = bd ∈ Z and q ≠ 0.

EXERCISE: Given any two distinct rational numbers r and s with r < s. Prove that there is a rational number x such that r < x < s.

Proof: Given two distinct rational numbers r and s such that r < s. Adding r to both sides: 2r < r + s ⇒ r < (r + s)/2. Adding s to both sides: r + s < 2s ⇒ (r + s)/2 < s. Combining: r < (r + s)/2 < s. Since the sum of two rationals is rational, r + s is rational. Also the quotient of a rational by a non-zero rational is rational, therefore (r + s)/2 is rational. Hence, we have found a rational number x = (r + s)/2 such that r < x < s.

EXERCISE: Prove that for all integers a, b and c, if a|b and b|c then a|c.

🔑 Definition — divisibility: For integers n and d with d ≠ 0, d divides n (d | n) if n = d·k for some integer k. Proof: Suppose a|b and b|c where a, b, c ∈ Z. Then b = a·r and c = b·s for some integers r and s. Now c = b·s = (a·r)·s = a·(r·s) = a·k where k = r·s ∈ Z, so a | c by definition of divisibility.

EXERCISE: Prove that for all integers a, b and c if a|b and a|c then a|(b+c)

Proof: Suppose a|b and a|c where a, b, c ∈ Z. By definition of divides, b = a·r and c = a·s for some r, s ∈ Z. Now b + c = a·r + a·s = a·(r+s) = a·k where k = (r + s) ∈ Z. Hence a|(b + c) by definition of divides.

EXERCISE: Prove that the sum of any three consecutive integers is divisible by 3.

Proof: Let n, n + 1 and n + 2 be three consecutive integers. Now n + (n + 1) + (n + 2) = 3n + 3 = 3(n + 1) = 3·k where k = (n+1) ∈ Z. Hence, the sum of three consecutive integers is divisible by 3.

EXERCISE: Prove the statement: There is an integer n > 5 such that 2ⁿ - 1 is prime

Proof: Let n = 7, then 2ⁿ - 1 = 2⁷ - 1 = 128 - 1 = 127, and we know that 127 is prime.

EXERCISE: Prove the statement: There are real numbers a and b such that √(a+b) = √a + √b

Proof: Squaring both sides gives a + b = a + b + 2√(ab) ⇒ 0 = 2√(ab) ⇒ 0 = √(ab) ⇒ 0 = ab ⇒ either a = 0 or b = 0. Hence if we let a = 0 and b = 3, then R.H.S = √0 + √3 = √3 and L.H.S = √(0+3) = √3. The given condition is satisfied.

PROOF BY COUNTER EXAMPLE:

Disproof by counterexample is used to show a universal statement is false by finding a single instance where it fails. Example: Disprove: For all real numbers a and b, if a < b then a² < b². Counterexample: Suppose a = -5 and b = -2. Clearly -5 < -2, but a² = 25 and b² = 4, and 25 > 4. This disproves the statement.

EXERCISE: Prove or give counter example to disprove: For all integers n, n² - n + 11 is a prime number.

Disproof: The statement is not true. For n = 11, n² - n + 11 = (11)² - 11 + 11 = (11)² = 121, which is obviously not a prime number.

EXERCISE: Prove or disprove that the product of any two irrational numbers is an irrational number.

Disproof: We know that √2 is an irrational number. Now √2·√2 = (√2)² = 2 = 2/1, which is a rational number. Hence the statement is disproved.

EXERCISE: Find a counter example to the proposition: For every prime number n, n + 2 is prime.

Disproof: Let the prime number n be 7, then n + 2 = 7 + 2 = 9, which is not prime.

⭐ Key Takeaways

The most critical concepts from this lecture are: understanding the definition and use of direct proof for proving implications p → q by assuming p is true and showing q must follow. You must memorize the definitions of even, odd, prime, composite, rational numbers, and divisibility as they form the foundation for constructing proofs. The technique of disproof by counterexample requires finding just one instance where a universal statement fails. Key proof patterns to remember include: even numbers expressed as 2k, odd numbers as 2k+1, and rational numbers as a/b. The transitivity property of divisibility (if a|b and b|c then a|c) and the addition property (if a|b and a|c then a|(b+c)) are essential results.

🧠 Quick Revision Questions

1. What is the definition of an even integer? An odd integer?
2. How do you prove the sum of two odd integers is even using direct proof?
3. What is a counterexample to disprove the statement: "For all real numbers a and b, if a < b then a² < b²"?
4. Prove that for all integers a, b, c: if a|b and b|c then a|c.
5. Give a counterexample showing that the product of two irrational numbers is not always irrational.

📘 Lecture 26 — Proof by Contradiction

📖 Overview: This lecture introduces proof by contradiction (reductio ad absurdum), a powerful method where a statement is proven true by showing its negation leads to a logical impossibility. It also covers proof by contraposition, which leverages the logical equivalence between an implication and its contrapositive. These methods are fundamental for proving many theorems in mathematics, including results about integers, prime numbers, and irrational numbers.

🗂️ Topics Covered

The lecture begins by defining proof by contradiction and its logical basis in the negation of an implication (p ∧ ~q → c). It then works through numerous examples: proving there is no greatest integer, showing that if n² is even then n is even, and demonstrating that if n³+5 is odd then n is even. The method is also applied to prove that the sum of a rational and irrational number is irrational, that √2 and 6−7√2 are irrational, and that the set of prime numbers is infinite. The lecture concludes with an introduction to proof by contraposition, with examples including the parity of n² and 3n+2, and a conditional statement about divisibility by 5 and 25.

📝 Lecture Summary

PROOF BY CONTRADICTION

A proof by contradiction is based on the fact that either a statement is true or it is false but not both. Hence the supposition, that the statement to be proved is false, leads logically to a contradiction, impossibility or absurdity, then the supposition must be false. Accordingly, the given statement must be true. This method of proof is also known as reductio ad absurdum because it relies on reducing a given assumption to an absurdity.

Many theorems in mathematics are conditional statements (p→q). The negation of the implication p→q is: ~(p→q) ≡ ~(~p ∨ q) ≡ ~(~p) ∧ (~q) (DeMorgan’s Law) ≡ p ∧ ~q Clearly if the implication is true, then its negation must be false, i.e., leads to a contradiction. Hence ~(p→q) ≡ (p ∧ ~q) → c, where c is a contradiction.

Thus to prove an implication p → q by contradiction method, we suppose that the condition p and the negation of the conclusion q, i.e., (p ∧ ~q) is true and ultimately arrive at a contradiction.

The method of proof by contradiction may be summarized as follows:

1. Suppose the statement to be proved is false.
2. Show that this supposition leads logically to a contradiction.
3. Conclude that the statement to be proved is true.

THEOREM: There is no greatest integer.

PROOF: Suppose there is a greatest integer N. Then n ≤ N for every integer n. Let M = N + 1. Now M is an integer since it is a sum of integers. Also M > N since M = N + 1. Thus M is an integer that is greater than the greatest integer, which is a contradiction. Hence our supposition is not true and so there is no greatest integer.

EXERCISE: “If n² is an even integer then n is an even integer.”

PROOF: Suppose n² is an even integer and n is not even, so that n is odd. Hence n = 2k + 1 for some integer k. Now n² = (2k + 1)² = 4k² + 4k + 1 = 2·(2k² + 2k) + 1 = 2r + 1 where r = (2k² + 2k) ∈ Z. This shows that n² is odd, which is a contradiction to our supposition that n² is even. Hence the given statement is true.

EXERCISE: Prove that if n is an integer and n³ + 5 is odd, then n is even.

SOLUTION: Suppose that n³ + 5 is odd and n is not even (odd). Since n is odd and the product of two odd numbers is odd, it follows that n² is odd and n³ = n²·n is odd. Further, since the difference of two odd numbers is even, it follows that 5 = (n³ + 5) − n³ is even. But this is a contradiction. Therefore, the supposition that n³ + 5 and n are both odd is wrong and so the given statement is true.

EXERCISE: If n and m are odd integers, then n + m is an even integer.

SOLUTION: Suppose n and m are odd and n + m is not even (odd i.e., by taking contradiction). Now n = 2p + 1 for some integer p and m = 2q + 1 for some integer q. Hence n + m = (2p + 1) + (2q + 1) = 2p + 2q + 2 = 2·(p + q + 1) which is even, contradicting the assumption that n + m is odd.

THEOREM: The sum of any rational number and any irrational number is irrational.

PROOF: We suppose that the negation of the statement is true. That is, we suppose that there is a rational number r and an irrational number s such that r + s is rational. By definition of rational, r = a/b and r + s = c/d for some integers a, b, c and d with b≠0 and d≠0. Using these, we get: a/b + s = c/d ⇒ s = c/d − a/b ⇒ s = (bc − ad)/(bd) (bd ≠ 0) Now bc−ad and bd are both integers, since products and difference of integers are integers. Hence s is a quotient of two integers bc−ad and bd with bd ≠ 0. So by definition of rational, s is rational. This contradicts the supposition that s is irrational. Hence the supposition is false and the theorem is true.

EXERCISE: Prove that √2 is irrational.

PROOF: Suppose √2 is rational. Then there are integers m and n with no common factors so that √2 = m/n. Squaring both sides gives 2 = m²/n², or m² = 2n². This implies that m² is even (by definition of even). It follows that m is even. Hence m = 2k for some integer k. Substituting this, we get (2k)² = 2n² ⇒ 4k² = 2n² ⇒ n² = 2k². This implies that n² is even, and so n is even. But we also know that m is even. Hence both m and n have a common factor 2. But this contradicts the supposition that m and n have no common factors. Hence our supposition is false and so the theorem is true.

EXERCISE: Prove that 6 − 7√2 is irrational.

PROOF: Suppose 6 − 7√2 is rational. Then by definition of rational, 6 − 7√2 = a/b for some integers a and b with b≠0. Now consider: 7√2 = 6 − a/b ⇒ 7√2 = (6b − a)/b ⇒ √2 = (6b − a)/(7b). Since a and b are integers, so are 6b−a and 7b and 7b≠0; hence √2 is a quotient of the two integers 6b−a and 7b with 7b≠0. Accordingly, √2 is rational. This contradicts the fact that √2 is irrational. Hence our supposition is false and so 6 − 7√2 is irrational.

EXERCISE: Prove that for any integer a and any prime number p, if p|a, then p ∤ (a + 1).

PROOF: Suppose there exists an integer a and a prime number p such that p|a and p|(a+1). Then by definition of divisibility there exist integers r and s so that a = p·r and a + 1 = p·s. It follows that: 1 = (a + 1) − a = p·s − p·r = p·(s−r) where s−r ∈ Z This implies p | 1. But the only integer divisors of 1 are 1 and −1 and since p is prime p>1. This is a contradiction. Hence the supposition is false, and the given statement is true.

EXERCISE: Prove that √2 + √3 is irrational.

SOLUTION: Suppose √2 + √3 is rational. Then there exists integers a and b with b≠0 such that √2 + √3 = a/b. Squaring both sides, we get: 2 + 3 + 2√6 = a²/b² ⇒ 2√6 = a²/b² − 5 ⇒ 2√6 = (a² − 5b²)/b² ⇒ √6 = (a² − 5b²)/(2b²) Since a and b are integers, so are a² − 5b² and 2b² with 2b²≠0. Hence √6 is the quotient of two integers a² − 5b² and 2b². Accordingly, √6 is rational. But this is a contradiction, since √6 is not rational. Hence our supposition is false and so √2 + √3 is irrational.

💡 Why this matters: The sum of two irrational numbers need not be irrational in general, for example (6 − 7√2) + (6 + 7√2) = 12 which is rational.

THEOREM: The set of prime numbers is infinite.

PROOF: Suppose the set of prime numbers is finite. Then all the prime numbers can be listed, say, in ascending order: p₁ = 2, p₂ = 3, p₃ = 5, p₄ = 7, ..., pₙ. Consider the integer N = p₁·p₂·p₃·...·pₙ + 1. Then N > 1. Since any integer greater than 1 is divisible by some prime number p, therefore p | N. Also since p is prime, p must equal one of the prime numbers p₁, p₂, p₃, ..., pₙ. Thus p | (p₁·p₂·p₃·...·pₙ). But then p ∤ (p₁·p₂·p₃·...·pₙ + 1). So p ∤ N. Thus p | N and p ∤ N, which is a contradiction. Hence the supposition is false and the theorem is true.

PROOF BY CONTRAPOSITION

A proof by contraposition is based on the logical equivalence between a statement and its contrapositive. Therefore, the implication p→q can be proved by showing that its contrapositive ~q → ~p is true. The contrapositive is usually proved directly.

The method of proof by contrapositive may be summarized as:

1. Express the statement in the form if p then q.
2. Rewrite this statement in the contrapositive form if not q then not p.
3. Prove the contrapositive by a direct proof.

EXERCISE: Prove that for all integers n, if n² is even then n is even.

PROOF: The contrapositive of the given statement is: “if n is not even (odd) then n² is not even (odd).” We prove this contrapositive statement directly. Suppose n is odd. Then n = 2k + 1 for some k ∈ Z. Now n² = (2k+1)² = 4k² + 4k + 1 = 2·(2k² + 2k) + 1 = 2·r + 1 where r = 2k² + 2k ∈ Z. Hence n² is odd. Thus the contrapositive statement is true and so the given statement is true.

EXERCISE: Prove that if 3n + 2 is odd, then n is odd.

PROOF: The contrapositive of the given conditional statement is “if n is even then 3n + 2 is even.” Suppose n is even, then n = 2k for some k ∈ Z. Now 3n + 2 = 3(2k) + 2 = 2·(3k + 1) = 2·r where r = (3k + 1) ∈ Z. Hence 3n + 2 is even. We conclude that the given statement is true since its contrapositive is true.

EXERCISE: Prove that if n is an integer and n³ + 5 is odd, then n is even.

PROOF: Suppose n is an odd integer. Since a product of two odd integers is odd, therefore n² = n·n is odd; and n³ = n²·n is odd. Since a sum of two odd integers is even, therefore n³ + 5 is even. Thus we have proved that if n is odd then n³ + 5 is even. Since this is the contrapositive of the given conditional statement, the given statement is true.

EXERCISE: Prove that if n² is not divisible by 25, then n is not divisible by 5.

SOLUTION: The contrapositive statement is: “if n is divisible by 5, then n² is divisible by 25.” Suppose n is divisible by 5. Then by definition of divisibility, n = 5·k for some integer k. Squaring both sides: n² = 25·k² where k² ∈ Z. Therefore n² is divisible by 25.

EXERCISE: Prove that if |x| > 1 then x > 1 or x < -1 for all x ∈ R.

PROOF: The contrapositive statement is: if x ≤ 1 and x ≥ -1 then |x| ≤ 1 for x ∈ R. Suppose that x ≤ 1 and x ≥ -1 ⇒ x ≤ 1 and x ≥ -1 ⇒ -1 ≤ x ≤ 1 and so |x| ≤ 1.

EXERCISE: For all integers m and n, if m + n is even then m and n are both even or m and n are both odd.

PROOF: The contrapositive statement is: “For all integers m and n, if m and n are not both even and m and n are not both odd, then m + n is not even.” Or more simply, “For all integers m and n, if one of m and n is even and the other is odd, then m + n is odd.” Suppose m is even and n is odd. Then m = 2p for some integer p and n = 2q + 1 for some integer q. Now m + n = (2p) + (2q + 1) = 2·(p+q) + 1 = 2·r + 1 where r = p+q is an integer. Hence m + n is odd. Similarly, taking m as odd and n even, we again arrive at the result that m + n is odd. Thus, the contrapositive statement is true. Since an implication is logically equivalent to its contrapositive, the given implication is true.

⭐ Key Takeaways

The most critical concepts from this lecture are the logical structure of proof by contradiction—assuming the negation leads to a contradiction—and the logical equivalence between an implication and its contrapositive. Students must master the specific technique of assuming p ∧ ~q and deriving a contradiction to prove p→q, and the method of proving the contrapositive directly as an alternative strategy. The classic proofs—that √2 is irrational, that there is no greatest integer, that the set of primes is infinite, and that the sum of a rational and irrational is irrational—are essential templates that demonstrate how to set up and execute these methods. A common pitfall to avoid is confusing contrapositive with converse or inverse, and students must remember that proof by contradiction and contrapositive are distinct, equally valid approaches.

🧠 Quick Revision Questions

1. What is the logical form of the negation of an implication p→q, and how is it used in a proof by contradiction?
2. Write a complete proof by contradiction showing that √2 is irrational, explaining why m and n must have no common factors.
3. State the contrapositive of the statement "If n² is even, then n is even" and prove it directly.
4. Prove by contradiction that there is no greatest integer, explaining where the contradiction arises.
5. Why does the proof that the set of primes is infinite require constructing the number N = p₁·p₂·...·pₙ + 1?

📘 Lecture 27 — Algorithm

📖 Overview: This lecture formally defines the concept of an algorithm and provides the complete specification structure used to describe algorithms. It introduces the Division Algorithm as a concrete example and explains how to prove algorithm correctness using pre-conditions, post-conditions, and the loop invariant theorem.

🗂️ Topics Covered

The lecture covers the formal definition of an algorithm and the standard information included when describing algorithms. It presents the Division Algorithm based on the Quotient-Remainder Theorem, demonstrates tracing the algorithm's execution, defines predicates and their domains, and explains pre-conditions and post-conditions. The lecture concludes with a detailed explanation of loop invariants and the Loop Invariant Theorem with its four required properties for proving loop correctness.

📝 Lecture Summary

ALGORITHM

The word "algorithm" refers to a step-by-step method for performing some action. A computer program is a set of instructions executed step-by-step for performing some specific task, but the term algorithm is more general since a program refers to a particular programming language.

INFORMATION ABOUT ALGORITHM

When describing algorithms formally, the following information is generally included:

1. The name of the algorithm, together with a list of input and output variables.
2. A brief description of how the algorithm works.
3. The input variable names, labeled by data type.
4. The statements that make the body of the algorithm, with explanatory comments.
5. The output variable names, labeled by data type.
6. An end statement.

THE DIVISION ALGORITHM

THEOREM (Quotient-Remainder Theorem): Given any integer n and a positive integer d, there exist unique integers q and r such that n = d · q + r and 0 ≤ r < d.

📌 Example:

• n = 54, d = 4: 54 = 4 · 13 + 2; hence q = 13, r = 2
• n = -54, d = 4: -54 = 4 · (-14) + 2; hence q = -14, r = 2
• n = 54, d = 70: 54 = 70 · 0 + 54; hence q = 0, r = 54

ALGORITHM (DIVISION): {Given a nonnegative integer a and a positive integer d, the aim of the algorithm is to find integers q and r that satisfy the conditions a = d · q + r and 0 ≤ r < d. This is done by subtracting d repeatedly from a until the result is less than d but is still nonnegative. The total number of d's that are subtracted is the quotient q. The quantity a - d · q equals the remainder r.}

Input: a {a nonnegative integer}, d {a positive integer} Algorithm body: r := a, q := 0 {Repeatedly subtract d from r until a number less than d is obtained. Add 1 to d each time d is subtracted.}

while (r ≥ d) r := r - d q := q + 1 end while

Output: q, r end Algorithm (Division)

TRACING THE DIVISION ALGORITHM

📌 Example: Trace the Division Algorithm on input variables a = 54 and d = 11.

The loop stops when r = 10, which is less than d = 11. The final values are q = 4 and r = 10. Since 54 = 11 · 4 + 10 and 0 ≤ 10 < 11, the result satisfies the theorem.

PREDICATE

A predicate is a sentence that contains a finite number of variables and becomes a statement when specific values are substituted for the variables. The domain of a predicate variable is the set of all values that may be substituted in place of the variable.

Consider the sentence "Aslam is a student at the Virtual University." Let P stand for "is a student at the Virtual University" and Q stand for "is a student at." The sentences "x is a student at the Virtual University" and "x is a student at y" are symbolized as P(x) and Q(x, y), where x and y are predicate variables that take values in appropriate sets.

PRE-CONDITIONS AND POST-CONDITIONS

The predicate describing the initial state is called the pre-condition of the algorithm and the predicate describing the final state is called the post-condition of the algorithm.

📌 Example 1: Algorithm to compute a product of two nonnegative integers

• Pre-condition: The input variables m and n are nonnegative integers.
• Post-condition: The output variable p equals m · n.

📌 Example 2: Algorithm to find the quotient and remainder of the division of one positive integer by another

• Pre-condition: The input variables a and b are positive integers.
• Post-condition: The output variables q and r are positive integers such that a = b · q + r and 0 ≤ r < b.

📌 Example 3: Algorithm to sort a one-dimensional array of real numbers

• Pre-condition: The input variable A[1], A[2], ..., A[n] is a one-dimensional array of real numbers.
• Post-condition: The output variable B[1], B[2], ..., B[n] is a one-dimensional array of real numbers with the same elements as A[1], A[2], ..., A[n] but with the property that B[i] ≤ B[j] whenever i ≤ j.

THE DIVISION ALGORITHM WITH PRE AND POST CONDITIONS: [pre-condition: a is a nonnegative integer and d is a positive integer, r = a, and q = 0] while (r ≥ d) 1. r := r - d 2. q := q + 1 end while [post-condition: q and r are nonnegative integers with the property that a = q · d + r and 0 ≤ r < d.]

LOOP INVARIANTS

Definition: A loop is defined as correct with respect to its pre- and post-conditions if, and only if, whenever the algorithm variables satisfy the pre-condition for the loop and the loop is executed, then the algorithm variables satisfy the post-condition of the loop.

The method of loop invariants is used to prove correctness of a loop with respect to certain pre and post-conditions. It is based on the principle of mathematical induction.

LOOP INVARIANT THEOREM

THEOREM: Let a while loop with guard G be given, together with pre- and post-conditions that are predicates in the algorithm variables. Also let a predicate I(n), called the loop invariant, be given. If the following four properties are true, then the loop is correct with respect to its pre- and post-conditions:

I. Basis Property: The pre-condition for the loop implies that I(0) is true before the first iteration of the loop.

II. Inductive Property: If the guard G and the loop invariant I(k) are both true for an integer k ≥ 0 before an iteration of the loop, then I(k + 1) is true after iteration of the loop.

III. Eventual Falsity of Guard: After a finite number of iterations of the loop, the guard becomes false.

IV. Correctness of the Post-Condition: If N is the least number of iterations after which G is false and I(N) is true, then the values of the algorithm variables will be as specified in the post-condition of the loop.

PROOF: Let I(n) be a predicate that satisfies properties I-IV of the loop invariant theorem. Properties I and II establish that for all integers n ≥ 0, if the while loop iterates n times, then I(n) is true. Property III indicates that the guard G becomes false after a finite number N of iterations. Property IV concludes that the values of the algorithm variables are as specified by the post-condition of the loop.

💡 Why this matters: The loop invariant theorem provides a rigorous mathematical framework for proving that algorithms work correctly before they are implemented. By establishing these four properties, programmers can verify that loops produce exactly the intended output for all valid inputs, eliminating the need for exhaustive testing.

⭐ Key Takeaways

The loop invariant theorem is the central tool for proving algorithm correctness and requires establishing four properties: the basis property (invariant holds before loop starts), the inductive property (if invariant and guard hold before an iteration, invariant holds after), eventual falsity of guard (loop terminates), and correctness of post-condition (when loop ends, the results match specifications). Pre-conditions describe what must be true before an algorithm runs, while post-conditions describe what must be true after it completes. The Division Algorithm demonstrates both the concept of tracing execution step-by-step and the application of pre/post conditions in a concrete setting.

🧠 Quick Revision Questions

1. What is the Quotient-Remainder Theorem and what does it guarantee about the existence and uniqueness of q and r?
2. What are the four properties that must be established by the Loop Invariant Theorem for a loop to be correct?
3. In the Division Algorithm, what is the role of the variable q and how does its value change as the algorithm executes?
4. What is the difference between an algorithm and a program?
5. For the Division Algorithm's proof of correctness, what would be an appropriate loop invariant I(k)?

📘 Lecture 28 — Division Algorithm

📖 Overview: This lecture focuses on proving the correctness of three fundamental algorithms using loop invariants: a loop to compute a product, the division algorithm for integer division with remainder, and the Euclidean algorithm for finding the greatest common divisor (gcd). Understanding these proofs is essential for establishing that algorithms reliably produce correct outputs for all valid inputs.

🗂️ Topics Covered

The lecture begins by proving the correctness of a simple loop that computes the product of a real number and a nonnegative integer using basis, inductive, and eventual falsity properties. It then proves the correctness of the division algorithm, which computes quotient and remainder for integer division. Finally, it introduces the Euclidean algorithm for computing the greatest common divisor of two integers, including a hand-calculation example, supporting lemma, and a formal proof of the algorithm's correctness using the loop invariant technique.

📝 Lecture Summary

CORRECTNESS OF: LOOP TO COMPUTE A PRODUCT

This section proves the correctness of a while loop that computes the product m · x where m is a nonnegative integer and x is a real number. The algorithm initializes i = 0 and product = 0, then repeatedly adds x to product and increments i until i = m.

The proof uses the loop invariant I(n): i = n and product = n · x.

I. Basis Property: I(0) holds before the first iteration because i = 0 and product = 0 · x = 0.

II. Inductive Property: Assuming I(k) is true (i.e., i = k and product = k · x) and the guard G: i ≠ m is true, after one iteration we have product_new = product_old + x = k·x + x = (k+1)·x and i_new = k + 1. Thus I(k+1) is true.

III. Eventual Falsity of Guard: The guard i ≠ m becomes false after exactly m iterations because i starts at 0 and increments by 1 each time.

IV. Correctness of the Post-Condition: When the loop terminates after N = m iterations, I(m) is true, meaning i = m and product = m · x, exactly matching the post-condition.

THE DIVISION ALGORITHM

This section proves the correctness of an algorithm that computes integer division: given a nonnegative integer a and a positive integer d, it produces quotient q and remainder r such that a = q·d + r and 0 ≤ r < d. The algorithm initializes r = a and q = 0, then repeatedly subtracts d from r and increments q while r ≥ d.

The proof uses the loop invariant I(n): r = a - n·d and n = q.

🔑 Definition — Loop Invariant: A property that is true before the first iteration of a loop and remains true after each iteration.

I. Basis Property: I(0) is true because initially r = a = a - 0·d and q = 0.

II. Inductive Property: Assuming I(k): r = a - k·d ≥ 0 and k = q and the guard r ≥ d is true, after one iteration: r_new = r - d = a - k·d - d = a - (k+1)·d and q_new = k+1. Since r ≥ d, we have r_new ≥ 0, so I(k+1) is true.

III. Eventual Falsity of Guard: The guard r ≥ d becomes false after a finite number of iterations because r decreases by d each time and starts at a finite value a.

IV. Correctness of the Post-Condition: When the loop terminates, the guard is false (r < d) and I(N) is true (r = a - N·d and N = q). Therefore a = q·d + r and 0 ≤ r < d, matching the post-condition.

📐 Formula: Division Algorithm: a = q·d + r where 0 ≤ r < d

💡 Why this matters: The division algorithm is fundamental to number theory and computer arithmetic, forming the basis for many operations including modular arithmetic and the Euclidean algorithm.

THE EUCLIDEAN ALGORITHM

This section introduces the Euclidean algorithm, an efficient method for computing the greatest common divisor (gcd) of two integers. The gcd of two integers a and b is the largest integer that divides both.

🔑 Definition — Greatest Common Divisor (gcd): The largest integer that divides both a and b. For example, gcd(12, 30) = 6.

Hand calculation example: Find gcd(330, 156)

The algorithm performs repeated division:

1. Divide 330 by 156: 330 = 156·2 + 18
2. Divide 156 by 18: 156 = 18·8 + 12
3. Divide 18 by 12: 18 = 12·1 + 6
4. Divide 12 by 6: 12 = 6·2 + 0

The last nonzero remainder is 6, so gcd(330, 156) = 6.

LEMMA: If a and b are any integers with b ≠ 0 and q and r are nonnegative integers such that a = q·b + r, then gcd(a, b) = gcd(b, r).

The formal algorithm initializes a = A, b = B, r = B (where A > B ≥ 0), then repeatedly replaces (a, b) with (b, a mod b) until b = 0. The loop invariant is I(n): gcd(a, b) = gcd(A, B) and 0 ≤ b < a.

I. Basis Property: I(0) is true because gcd(a, b) = gcd(A, B) by initialization and 0 ≤ b < a from the precondition.

II. Inductive Property: Assuming I(k) and the guard b ≠ 0 are true, we have gcd(a_old, b_old) = gcd(A, B). After r_new = a_old mod b_old, we have a_old = b_old·q + r_new with 0 ≤ r_new < b_old. By the lemma, gcd(a_old, b_old) = gcd(b_old, r_new) = gcd(A, B). After updating a_new = b_old and b_new = r_new, we get gcd(a_new, b_new) = gcd(A, B) and 0 ≤ b_new < a_new, so I(k+1) is true.

III. Eventual Falsity of Guard: The guard b ≠ 0 becomes false after a finite number of iterations because b is replaced by a mod b, which is always smaller than b and nonnegative.

IV. Correctness of the Post-Condition: When the loop terminates, b = 0 and I(N) is true: gcd(a, b) = gcd(A, B). Since gcd(a, 0) = a, we have a = gcd(A, B), matching the post-condition.

📌 Example: Using the Euclidean algorithm to find gcd(330, 156):

• Step 1: 330 ÷ 156 gives quotient 2, remainder 18 → gcd(330, 156) = gcd(156, 18)
• Step 2: 156 ÷ 18 gives quotient 8, remainder 12 → gcd(156, 18) = gcd(18, 12)
• Step 3: 18 ÷ 12 gives quotient 1, remainder 6 → gcd(18, 12) = gcd(12, 6)
• Step 4: 12 ÷ 6 gives quotient 2, remainder 0 → gcd(12, 6) = gcd(6, 0) = 6

⭐ Key Takeaways

The most critical concept from this lecture is the loop invariant technique for proving algorithm correctness, which requires establishing four properties: basis (invariant holds initially), induction (invariant preserved through iterations), eventual falsity of guard (loop terminates), and post-condition correctness. For the division algorithm, remember that the loop invariant r = a - n·d along with the guard r ≥ d guarantees the post-condition a = q·d + r with 0 ≤ r < d. For the Euclidean algorithm, the key lemma gcd(a, b) = gcd(b, a mod b) allows repeated reduction of the problem until reaching gcd(d, 0) = d. The hand-calculation method using repeated division until a zero remainder is the practical implementation of this proof.

🧠 Quick Revision Questions

1. What are the four properties that must be proved to establish the correctness of a while loop using the loop invariant technique?
2. In the division algorithm proof, what is the loop invariant and how does it lead to the post-condition a = q·d + r with 0 ≤ r < d?
3. State the lemma that justifies the Euclidean algorithm's correctness: if a = q·b + r, then what is the relationship between gcd(a,b) and gcd(b,r)?
4. Using the Euclidean algorithm, find gcd(84, 30) showing all steps.
5. In the Euclidean algorithm proof, why must the guard b ≠ 0 eventually become false?

📘 Lecture 29 — Combinatorics

📖 Overview: This lecture introduces the fundamental principles of counting in combinatorics: the sum rule and product rule. These rules form the foundation for solving counting problems in computer science, probability, and algorithm analysis.

🗂️ Topics Covered

The lecture covers combinatorics as the mathematics of counting and arranging objects, the sum rule for counting mutually exclusive events, the product rule for counting sequential events, and applications including license plate combinations, bit strings, nested loop iterations, and variable naming conventions.

📝 Lecture Summary

COMBINATORICS

Combinatorics is the mathematics of counting and arranging objects. Counting objects with certain properties (enumeration) is required to solve many different types of problems.

For example, counting is used to:

1. Determine number of ordered or unordered arrangement of objects
2. Generate all the arrangements of a specified kind which is important in computer simulations
3. Compute probabilities of events
4. Analyze the chance of winning games, lotteries etc.
5. Determine the complexity of algorithms

THE SUM RULE

If one event can occur in n₁ ways, a second event can occur in n₂ (different) ways, then the total number of ways in which exactly one of the events (i.e., first or second) can occur is n₁ + n₂.

📌 Example: Suppose there are 7 different optional courses in Computer Science and 3 different optional courses in Mathematics. Then there are 7 + 3 = 10 choices for a student who wants to take one optional course.

📌 Example: A student can choose a computer project from one of three lists containing 23, 15 and 19 possible projects. The student can choose from the first list in 23 ways, from the second in 15 ways, and from the third in 19 ways. Hence, there are 23 + 15 + 19 = 57 projects to choose from.

🔑 Generalized Sum Rule: If one event can occur in n₁ ways, a second event can occur in n₂ ways, a third event can occur in n₃ ways, etc., then there are n₁ + n₂ + n₃ + ... ways in which exactly one of the events can occur.

🔑 Sum Rule in Terms of Sets: If A₁, A₂, ..., Aₘ are finite disjoint sets, then the number of elements in the union of these sets is the sum of the number of elements in them. If n(Aᵢ) denotes the number of elements in set Aᵢ for i = 1, 2, ..., m, then n(A₁ ∪ A₂ ∪ ... ∪ Aₘ) = n(A₁) + n(A₂) + ... + n(Aₘ) where Aᵢ ∩ Aⱼ = ∅ if i ≠ j.

THE PRODUCT RULE

If one event can occur in n₁ ways and if for each of these n₁ ways, a second event can occur in n₂ ways, then the total number of ways in which both events occur is n₁ · n₂.

📌 Example: Suppose there are 7 different optional courses in Computer Science and 3 different optional courses in Mathematics. A student who wants to take one optional course of each subject has 7 × 3 = 21 choices.

📌 Example: The chairs of an auditorium are to be labeled with two characters, a letter followed by a digit. The procedure involves Assigning one of the 26 letters and Assigning one of the 10 digits. By product rule, there are 26 × 10 = 260 different ways a chair can be labeled.

🔑 Generalized Product Rule: If some event can occur in n₁ different ways, and following this event, a second event can occur in n₂ different ways, and following this second event, a third event can occur in n₃ different ways, etc., then the number of ways all events can occur in the order indicated is n₁ · n₂ · n₃ · ...

🔑 Product Rule in Terms of Sets: If A₁, A₂, ..., Aₘ are finite sets, then the number of elements in the Cartesian product of these sets is the product of the number of elements in each set. n(A₁ × A₂ × ... × Aₘ) = n(A₁) · n(A₂) · ... · n(Aₘ)

📌 Example: An organization consisting of 15 members needs to elect a president, treasurer, and secretary (no person holds more than one position). The president can be elected in 15 ways; following this, the treasurer in 14 ways; following this, the secretary in 13 ways. Thus, n = 15 × 14 × 13 = 2730 different ways.

📌 Example: There are 4 bus lines between A and B, and 3 bus lines between B and C. (a) Travel from A to C via B: 4 × 3 = 12 ways (b) Round trip (A→B→C→B→A): 4 × 3 × 3 × 4 = 144 ways (c) Round trip without reusing a bus line: 4 × 3 × 2 × 3 = 72 ways (since only 2 ways from C→B and 3 ways from B→A remain)

📌 Example: A bit string is a sequence of 0's and 1's. For length 4, each bit can be chosen in 2 ways, so 2 × 2 × 2 × 2 = 2⁴ = 16 different bit strings.

📌 Example: Bit strings of length 8: (i) Begin with 1: First bit fixed (1 way), remaining 7 bits each 2 ways → 1 × 2⁷ = 128 (ii) Begin and end with 1: First and last fixed (1 way each), remaining 6 bits each 2 ways → 1 × 2⁶ × 1 = 64

📌 Example: License plates with three letters followed by three digits: (a) Total: 26 × 26 × 26 × 10 × 10 × 10 = 17,576,000 (b) Begin with A and end with 0: 1 × 26 × 26 × 10 × 10 × 1 = 67,600 (c) Begin with PQR: 1 × 1 × 1 × 10 × 10 × 10 = 1,000 (d) All letters and digits distinct: 26 × 25 × 24 × 10 × 9 × 8 = 11,232,000 (e) Begin with AB and all distinct: 1 × 1 × 24 × 10 × 9 × 8 = 17,280

📌 Example: Variable names are either a letter or a letter followed by a digit. Names of length 1: 26 ways. Names of length 2: 26 × 10 = 260 ways. By sum rule: 26 + 260 = 286 possible variable names.

📌 Example: Bit strings from one through four digits: 2 + 2² + 2³ + 2⁴ = 2 + 4 + 8 + 16 = 30. From five through eight digits: 2⁵ + 2⁶ + 2⁷ + 2⁸ = 480.

📌 Example: Three-digit integers divisible by 5 end in 0 or 5. Case I (end in 0): 9 choices for hundreds digit (1-9), 10 for tens digit (0-9), 1 for units digit = 9 × 10 × 1 = 90 Case II (end in 5): 9 × 10 × 1 = 90 By sum rule: 90 + 90 = 180 three-digit integers divisible by 5.

📌 Example: Access code of 1-3 letters (repetition allowed): 26¹ + 26² + 26³ = 26 + 676 + 17,576 = 18,278.

NUMBER OF ITERATIONS OF A NESTED LOOP

📌 Example: Outer loop i = 1 to 4 (4 iterations), inner loop j = 1 to 3 (3 iterations per outer iteration). By product rule: 4 × 3 = 12 total inner loop iterations.

📌 Example: Outer loop i = 5 to 50 (50 - 5 + 1 = 46 iterations), inner loop j = 10 to 20 (20 - 10 + 1 = 11 iterations per outer iteration). By product rule: 46 × 11 = 506.

📌 Example: Outer loop i = 1 to 4, inner loop j = 1 to i. The inner loop iterates: 1, 2, 3, and 4 times respectively. By sum rule: 1 + 2 + 3 + 4 = 10 total iterations.

💡 Why this matters: When inner loop bounds depend on the outer loop variable, the total iterations cannot be found by simple multiplication — we must sum the individual counts.

⭐ Key Takeaways

The sum rule and product rule are the two fundamental counting principles in combinatorics. The sum rule applies when events are mutually exclusive (you choose exactly one), while the product rule applies when events occur in sequence (you choose one from each category). The sum rule generalizes to any finite number of disjoint sets where n(A₁ ∪ A₂ ∪ ... ∪ Aₘ) = n(A₁) + n(A₂) + ... + n(Aₘ). The product rule generalizes to any finite number of sequential events where n(A₁ × A₂ × ... × Aₘ) = n(A₁) · n(A₂) · ... · n(Aₘ). These rules combine to solve complex counting problems like license plate combinations, bit strings, and nested loop iterations, where the number of loop iterations can be computed using product rule for fixed bounds or sum rule for variable bounds.

🧠 Quick Revision Questions

1. How many different bit strings of length 6 are there?
2. A restaurant offers 4 appetizers and 7 main courses. How many different meals consisting of one appetizer and one main course are possible?
3. How many three-letter code words are possible using the English alphabet if letters can be repeated?
4. For a nested loop where the outer loop runs from i = 1 to 5 and the inner loop runs from j = 1 to i, what is the total number of iterations of the inner loop?
5. How many 4-digit numbers are there if the first digit cannot be 0?

📘 Lecture 32 — K-Combinations

📖 Overview: This lecture extends the concept of combinations to allow repetitions, introducing k-selections (also called k-combinations with repetition). It then covers ordered and unordered partitions of sets and permutations with repetitions (multinomial coefficients). These concepts are essential for solving complex counting problems where order may or may not matter, and where elements can be repeated or grouped.

🗂️ Topics Covered

This lecture begins with k-selections, defining them as unordered choices with repetition allowed, and presenting the formula C(k+n-1, k). It then provides a summary table comparing k-sample, k-permutation, k-combination, and k-selection. Next, it introduces ordered and unordered partitions of finite sets, with theorems and examples for dividing n elements into cells of specified sizes. Finally, it covers generalized permutations (permutations with repetitions), using multinomial coefficients to count arrangements of n elements where some are alike. Several exercises apply these concepts to real-world problems like distributing batteries, dividing students into groups, and arranging letters in words.

📝 Lecture Summary

K-SELECTIONS

k-selections are similar to k-combinations in that the order in which the elements are selected does not matter, but in this case repetitions can occur.

🔑 Definition — k-selection: A k-selection of a set of n elements is a choice of k elements taken from a set of n elements such that the order of elements does not matter and elements can be repeated.

Remark: k-selections are also called k-combinations with repetition allowed or multisets of size k. With k-selections of a set of n elements, repetition of elements is allowed, so k need not to be less than or equal to n.

Theorem: The number of k-selections that can be selected from a set of n elements is C(k+n-1, k) or ( \binom{k+n-1}{k} ).

📐 Formula: ( \binom{k+n-1}{k} ) → This counts the number of ways to choose k items from n types when order doesn't matter and repetition is allowed.

📌 Example: A camera shop stocks ten different types of batteries. (a) How many ways can a total inventory of 30 batteries be distributed among the ten different types?

• Here k = 30, n = 10.
• Required number = C(30 + 10 – 1, 30) = C(39, 30) = ( \frac{39!}{(39-30)!30!} = 211,915,132 )

(b) Assuming one type is A76, how many ways can 30 batteries be distributed if the inventory must include at least four A76 batteries?

• Reserve 4 A76 batteries, leaving k = 26 batteries to distribute among n = 10 types.
• Required number = C(26 + 10 – 1, 26) = C(35, 26) = ( \frac{35!}{(35-26)!26!} = 70,607,460 )

WHICH FORMULA TO USE?

The lecture provides a summary table:

ORDERED AND UNORDERED PARTITIONS

An unordered partition of a finite set S is a collection [A₁, A₂, ..., Aₖ] of disjoint (nonempty) subsets of S (called cells) whose union is S. The partition is ordered if the order of the cells in the list counts.

📌 Example: Let S = {1, 2, 3, ..., 7}. The collections P₁ = [{1,2}, {3,4,5}, {6,7}] and P₂ = [{6,7}, {3,4,5}, {1,2}] determine the same partition of S but are distinct ordered partitions.

📌 Example: Suppose a box B contains seven marbles numbered 1 through 7. Find the number m of ways of drawing from B firstly two marbles, then three marbles and lastly the remaining two marbles.

• Order matters (the order of drawing is specified), so we count ordered partitions.
• m = C(7,2) × C(5,3) × C(2,2)
• = ( \frac{7!}{2!5!} \times \frac{5!}{2!3!} \times \frac{2!}{2!0!} )
• = ( \frac{7!}{2!3!2!} = 210 )

Theorem: Let S contain n elements and let n₁, n₂, ..., nₖ be positive integers with n₁ + n₂ + ... + nₖ = n. Then there exist ( \frac{n!}{n_1! n_2! n_3! \cdots n_k!} ) different ordered partitions of S of the form [A₁, A₂, ..., Aₖ], where A₁ contains n₁ elements, A₂ contains n₂ elements, ..., Aₖ contains nₖ elements.

Remark: To find the number of unordered partitions, we have to count the ordered partitions and then divide it by a suitable number to erase the order in partitions.

📌 Example: Find the number m of ways that nine toys can be divided among four children if the youngest child is to receive three toys and each of the others two toys.

• This is ordered (children are distinct), with cells of sizes 3, 2, 2, 2.
• m = ( \frac{9!}{3!2!2!2!} = 2520 )

📌 Example: How many ways can 12 students be divided into 3 groups with 4 students in each group so that: (i) one group studies English, one History, and one Mathematics.

• Groups are labeled by subject, so ordered partitions.
• Number = ( \frac{12!}{4!4!4!} = 34,650 )

(ii) all the groups study Mathematics.

• Groups are unlabeled (same subject), so unordered partitions.
• Each unordered partition {G₁, G₂, G₃} can be arranged in 3! ways as an ordered partition.
• Number = ( \frac{12!}{4!4!4!} \times \frac{1}{3!} )

📌 Example: How many ways can 8 students be divided into two teams containing: (i) five and three students respectively.

• Teams have different sizes, so each unordered partition gives only one ordered partition.
• Number = ( \frac{8!}{5!3!} = 56 )

(ii) four students each.

• Teams are unlabeled and equal size.
• Ordered partitions = ( \frac{8!}{4!4!} = 70 ). Since each unordered partition determines 2! = 2 ordered partitions, number = 70/2 = 35.

📌 Example: Find the number m of ways that a class X with ten students can be partitioned into four teams A₁, A₂, B₁ and B₂ where A₁ and A₂ contain two students each and B₁ and B₂ contain three students each.

• Ordered partitions = ( \frac{10!}{2!2!3!3!} = 25,200 )
• Each unordered partition [A₁, A₂, B₁, B₂] determines 2!·2! = 4 ordered partitions.
• m = 25,200 / 4 = 6,300

📌 Example: Suppose 20 people are divided into 6 (numbered) committees so that 3 people each serve on C₁ and C₂, 4 people each on C₃ and C₄, 2 people on C₅, and 4 people on C₆. How many possible arrangements?

• Committees are labeled, so ordered partitions.
• Number = ( \frac{20!}{3!3!4!4!2!4!} = 2,444,321,880,000 )

📌 Example: If 20 people are divided into teams of size 3, 3, 4, 4, 2, 4, find the number of possible arrangements.

• Now teams (cells) are unlabeled.
• Since we have two teams of size 3 (swap gives 2! ways) and three teams of size 4 (swap gives 3! ways), we divide by 3!2! to remove order.
• Number = ( \frac{20!}{3!3!4!4!2!4!} \times \frac{1}{3!2!} = 203,693,490,000 )

GENERALIZED PERMUTATION or PERMUTATIONS WITH REPETITIONS

The number of permutations of n elements of which n₁ are alike, n₂ are alike, ..., nₖ are alike is ( \frac{n!}{n_1! n_2! \cdots n_k!} ).

Remark: The number ( \frac{n!}{n_1! n_2! \cdots n_k!} ) is often called a multinomial coefficient, and is denoted by the symbol ( \binom{n}{n_1, n_2, \cdots, n_k} ).

📌 Example: Find the number of distinct permutations that can be formed using the letters of the word "BENZENE".

• 7 letters: three E's (alike) and two N's (alike).
• Number = ( \frac{7!}{3!2!} = 420 )

📌 Example: How many different signals each consisting of six flags hung in a vertical line can be formed from four identical red flags and two identical blue flags?

• 6 elements: 4 alike and 2 alike.
• Number = ( \frac{6!}{4!2!} = 15 )

📌 Example: (i) Find the number of "words" that can be formed from the letters of the word ELEVEN.

• 6 letters: three E's.
• Number = ( \frac{6!}{3!} = 120 )

(ii) Find, if the words are to begin with L.

• First letter fixed as L, remaining 5 letters with three E's.
• Number = ( \frac{5!}{3!} = 20 )

(iii) Find, if the words are to begin and end in E.

• First and last fixed as E, remaining 4 distinct letters.
• Number = 4! = 24

(iv) Find, if the words are to begin with E and end in N.

• First fixed as E, last fixed as N, remaining 4 letters with two E's.
• Number = ( \frac{4!}{2!} = 12 )

📌 Example: (i) Find the number of permutations from all the letters of the word BASEBALL.

• 8 letters: two B's, two A's, two L's.
• Number = ( \frac{8!}{2!2!2!} = 5,040 )

(ii) Find, if the two B's are to be next to each other.

• Treat two B's as one letter: 7 letters with two A's and two L's.
• Number = ( \frac{7!}{2!2!} = 1,260 )

(iii) Find, if the words are to begin and end in a vowel.

• Vowels are A and E. Three cases: both A, A then E, E then A (3 possibilities).
• For each case, 6 positions left with two B's and two L's.
• Number = ( 3 \times \frac{6!}{2!2!} = 3 \times 180 = 540 )

⭐ Key Takeaways

• A k-selection counts unordered selections with repetition allowed, using the formula ( \binom{k+n-1}{k} ). This is distinct from k-combinations (no repetition), k-permutations (ordered, no repetition), and k-samples (ordered, repetition allowed). For ordered partitions of n elements into cells of specified sizes, use the multinomial coefficient ( \frac{n!}{n_1! n_2! \cdots n_k!} ). For unordered partitions, you must divide by the factorial of the number of cells of the same size to account for order.
• Permutations with repetitions (generalized permutations) also use the multinomial coefficient formula to count distinct arrangements when some elements are identical. Memorize the formula ( \frac{n!}{n_1! n_2! \cdots n_k!} ) for both ordered partitions and permutations with repetitions, and be able to distinguish between ordered and unordered partitions based on whether the groups/cells are labeled.

🧠 Quick Revision Questions

1. What is the formula for the number of k-selections from a set of n elements, and what does it mean?
2. When dividing 10 students into two unlabeled groups of 5 each, why is the number of ways NOT ( \frac{10!}{5!5!} )?
3. How many distinct permutations can be formed from the letters of the word "MISSISSIPPI"?
4. In the battery inventory problem, why is the number of ways to distribute 30 batteries among 10 types given by C(30+10-1, 30)?
5. What is the difference between an ordered partition and an unordered partition of a set?

📘 Lecture 33 — Tree Diagram

📖 Overview: This lecture introduces the tree diagram as a systematic tool for listing all logical possibilities in a sequence of events where each event has a finite number of outcomes. It then presents the inclusion-exclusion principle for counting elements in unions of sets, a fundamental counting technique used in probability and combinatorics.

🗂️ Topics Covered

The lecture begins with tree diagrams, explaining their structure and demonstrating their use with examples such as permutations, product sets, tournament outcomes, bit strings without consecutive 1s, and officer selection with constraints. It then shifts to the inclusion-exclusion principle, starting with the basic formula for two sets, followed by multiple exercises applying the principle to problems involving overlapping sets, complements, and differences.

📝 Lecture Summary

TREE DIAGRAM

A tree diagram is a useful tool to list all the logical possibilities of a sequence of events where each event can occur in a finite number of ways. A tree consists of a root, a number of branches leaving the root, and possible additional branches leaving the end points of other branches. To use trees in counting problems, we use a branch to represent each possible choice. The possible outcomes are represented by the leaves (end points of branches). A tree is normally constructed from left to right.

🔑 Definition — Tree Diagram: A diagram consisting of a root, branches, and leaves used to enumerate all possible outcomes of a sequence of events.

📌 Example: Find the permutations of {a, b, c}. The number of permutations of 3 elements is P(3, 3) = 3!/(3-3)! = 3! = 6. The tree diagram shows branches from the root for a, b, c. From a, branches go to b and c; from b, branches go to a and c; from c, branches go to a and b. This yields the six permutations: abc, acb, bac, bca, cab, cba.

📌 Example: Find the product set A × B × C, where A = {1,2}, B = {a,b,c}, and C = {3,4} by constructing the appropriate tree diagram. The tree starts from the root with branches for 1 and 2. From 1, branches go to a, b, c. From each of these, branches go to 3 and 4. Similarly for 2. This yields 12 elements: (1,a,3), (1,a,4), (1,b,3), (1,b,4), (1,c,3), (1,c,4), (2,a,3), (2,a,4), (2,b,3), (2,b,4), (2,c,3), (2,c,4).

📌 Example: Teams A and B play in a tournament. The team that first wins two games wins the tournament. Find the number of possible ways the tournament can occur. The tree shows the first game results in A or B. From A, the second game: if A wins again (AA → tournament over) or B wins (AB → third game needed). Similarly from B. The tournament can occur in 6 ways: AA, ABA, ABB, BAA, BAB, BB.

📌 Example: How many bit strings of length four do not have two consecutive 1’s? The tree diagram displays all bit strings of length four without two consecutive 1’s. The first bit can be 0 or 1. If first bit is 0, second can be 0 or 1. If first bit is 1, second can only be 0. Continuing this pattern yields 8 bit strings: 0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010.

📌 Example: Three officers — a president, a treasurer, and a secretary — are to be chosen from among four possible: A, B, C, and D. Suppose that A cannot be president and either C or D must be secretary. How many ways can the officers be chosen? The possibility tree starts with the president selection. Since A cannot be president, the president can be B, C, or D. From each president, branches show possible treasurers (remaining people). From each treasurer, branches show possible secretaries (either C or D must be chosen). There are only eight ways possible to choose the offices under given conditions.

THE INCLUSION-EXCLUSION PRINCIPLE

1. If A and B are disjoint finite sets, then n(A ∪ B) = n(A) + n(B).
2. If A and B are finite sets (not necessarily disjoint), then n(A ∪ B) = n(A) + n(B) - n(A ∩ B).

💡 Why this matters: Statement 1 follows from the sum rule. Statement 2 corrects for double-counting: elements in A ∩ B are counted twice (once in n(A) and once in n(B)), so we subtract n(A ∩ B) once to get the correct count for n(A ∪ B).

🔑 Definition — Inclusion-Exclusion Principle (Two Sets): For any finite sets A and B, n(A ∪ B) = n(A) + n(B) - n(A ∩ B).

📌 Example: There are 15 girl students and 25 boy students in a class. How many students are there in total? Since the sets of boy and girl students are disjoint, n(G ∪ B) = n(G) + n(B) = 15 + 25 = 40.

📌 Example: Among 200 people, 150 either swim or jog or both. If 85 swim and 60 swim and jog, how many jog? n(S ∪ J) = n(S) + n(J) - n(S ∩ J) ⇒ 150 = 85 + n(J) - 60 ⇒ n(J) = 150 - 85 + 60 = 125. Hence 125 people jog.

📌 Example: Suppose A and B are finite sets. Show that n(A\B) = n(A) - n(A ∩ B). Set A may be written as the union of two disjoint sets A\B and A ∩ B. Hence, by the inclusion-exclusion principle (for disjoint sets): n(A) = n(A\B) + n(A ∩ B) ⇒ n(A\B) = n(A) - n(A ∩ B).

🔑 Definition — Complement: n(A') = n(U\A) = n(U) - n(U ∩ A) = n(U) - n(A).

📌 Example: Let A and B be subsets of U with n(A) = 10, n(B) = 15, n(A') = 12, and n(A ∩ B) = 8. Find n(A ∪ B'). n(A ∪ B') = n(U \ (B \ A)) = n(U) - n(B\A). First, n(U) = n(A) + n(A') = 10 + 12 = 22. Then, n(B\A) = n(B) - n(A ∩ B) = 15 - 8 = 7. Therefore, n(A ∪ B') = 22 - 7 = 15.

📌 Example: Let A and B be subsets of U with n(U) = 100, n(A) = 50, n(B) = 60, and n((A ∪ B)') = 20. Find n(A ∩ B). n((A ∪ B)') = n(U) - n(A ∪ B) ⇒ 20 = 100 - n(A ∪ B) ⇒ n(A ∪ B) = 80. By inclusion-exclusion: n(A ∪ B) = n(A) + n(B) - n(A ∩ B) ⇒ 80 = 50 + 60 - n(A ∩ B) ⇒ n(A ∩ B) = 50 + 60 - 80 = 30.

📌 Example: Suppose 18 people read English newspaper (E) or Urdu newspaper (U) or both. Given 5 people read only English newspaper and 7 read both, find the number “r” of people who read only Urdu newspaper. n(E ∪ U) = n(E\U) + n(E ∩ U) + n(U\E) ⇒ 18 = 5 + 7 + r ⇒ r = 18 - 5 - 7 = 6.

📌 Example: Fifty people are interviewed. 20 like Chinese food (C), 32 like fast food (F), and 12 like neither. How many like Chinese but not fast food? n(C ∪ F) = n(C\F) + n(F). First, n((C ∪ F)') = n(U) - n(C ∪ F) ⇒ 12 = 50 - n(C ∪ F) ⇒ n(C ∪ F) = 38. Then, 38 = n(C\F) + 32 ⇒ n(C\F) = 38 - 32 = 6.

⭐ Key Takeaways

Tree diagrams are essential for visual enumeration of all possible outcomes in sequential events. They are especially useful when constraints limit certain branches. The inclusion-exclusion principle is fundamental: for two sets, always subtract the intersection to avoid double-counting when sets overlap. The relationship between set difference and intersection (n(A\B) = n(A) - n(A ∩ B)) is a key formula derived from the principle. When working with complements, always first find the total n(U) from the union of a set and its complement. For problems involving "only" one category, break the union into its three disjoint parts: only A, both A and B, and only B.

🧠 Quick Revision Questions

1. In constructing a tree diagram for finding bit strings of length four without two consecutive 1's, what restriction applies to the second bit if the first bit is 1?
2. What is the inclusion-exclusion formula for n(A ∪ B) when A and B are finite sets?
3. If n(U) = 50, n(A) = 25, n(B) = 30, and n(A' ∩ B') = 10, what is n(A ∪ B)?
4. How do you express n(A\B) in terms of n(A) and n(A ∩ B)?
5. In the officer selection example, why were there only 8 possible ways even though there were 4 candidates?

📘 Lecture 34 — Inclusion-Exclusion Principle

📖 Overview: This lecture introduces the inclusion-exclusion principle for counting elements in unions of sets, extending it to three and four sets. It also introduces the pigeonhole principle, a fundamental counting argument used to guarantee the existence of repetitions or patterns. These principles are essential for solving combinatorial problems in probability, computer science, and everyday reasoning.

🗂️ Topics Covered

The lecture covers the inclusion-exclusion principle for two, three, and four sets with worked examples, a revision of functions, the pigeonhole principle with its generalized form, and the definitions of floor and ceiling functions. Several exercises demonstrate how to apply both principles to find minimum numbers needed to guarantee a certain outcome.

📝 Lecture Summary

Inclusion-Exclusion Principle

The inclusion-exclusion principle is a counting technique used to find the number of elements in the union of two or more sets. For two sets A and B, it accounts for elements counted twice (the intersection) by subtracting it once. The principle can be extended to three and four sets.

🔑 Definition — Inclusion-Exclusion Principle for Two Sets: For finite sets A and B, the number of elements in the union of A and B is given by: n(A ∪ B) = n(A) + n(B) - n(A ∩ B).

📐 Formula: n(A ∪ B) = n(A) + n(B) - n(A ∩ B) → This formula adds the elements in each set and subtracts the elements counted twice (those in both sets).

📌 Example: How many integers from 1 through 1000 are multiples of 3 or 5? Let A = multiples of 3, B = multiples of 5. We compute:

• n(A) = ⌊1000/3⌋ = 333
• n(B) = ⌊1000/5⌋ = 200
• n(A ∩ B) = ⌊1000/15⌋ = 66 (multiples of both 3 and 5, i.e., multiples of 15)
• Therefore, n(A ∪ B) = 333 + 200 - 66 = 467.

Example (continued): How many integers from 1 through 1000 are neither multiples of 3 nor 5? This is the complement of A ∪ B. Since the universal set U has 1000 elements: n((A ∪ B)') = n(U) - n(A ∪ B) = 1000 - 467 = 533.

💡 Why this matters: The complement approach (neither...nor) is a common application of the inclusion-exclusion principle.

Inclusion-Exclusion Principle for 3 and 4 Sets

The principle generalizes to more than two sets, alternating between adding and subtracting the sizes of intersections of increasing numbers of sets.

📐 Formula for Three Sets: n(A ∪ B ∪ C) = n(A) + n(B) + n(C) - n(A ∩ B) - n(B ∩ C) - n(A ∩ C) + n(A ∩ B ∩ C).

📐 Formula for Four Sets: n(A ∪ B ∪ C ∪ D) = n(A) + n(B) + n(C) + n(D) - n(A ∩ B) - n(A ∩ C) - n(A ∩ D) - n(B ∩ C) - n(B ∩ D) - n(C ∩ D) + n(A ∩ B ∩ C) + n(A ∩ B ∩ D) + n(A ∩ C ∩ D) + n(B ∩ C ∩ D) - n(A ∩ B ∩ C ∩ D).

📌 Example: A survey of 100 college students: 8 owned a car (C), 20 a motorcycle (M), 48 a bicycle (B), 38 owned none of these, and no student owned both a car and a motorcycle (n(C ∩ M) = 0). How many students owned a bicycle and either a car or a motorcycle (i.e., n(B ∩ C) + n(B ∩ M))?

• First, find n(C ∪ M ∪ B) = n(U) - n((C ∪ M ∪ B)') = 100 - 38 = 62.
• Apply the three-set formula: 62 = 8 + 20 + 48 - 0 - n(C ∩ B) - n(M ∩ B) + n(C ∩ M ∩ B).
• Given no student has a car and a motorcycle, the triple intersection n(C ∩ M ∩ B) = 0.
• Therefore: 62 = 76 - n(C ∩ B) - n(M ∩ B), so n(C ∩ B) + n(M ∩ B) = 76 - 62 = 14. Thus, 14 students owned a bicycle and either a car or a motorcycle.

Revision of Functions

A function from set A to set B is a relation where each element of A has exactly one image in B. A relation is not a function if any element of the domain has no image or more than one image.

Pigeonhole Principle

The pigeonhole principle is a simple but powerful counting argument. The classic formulation involves pigeons and holes.

🔑 Definition — Pigeonhole Principle: A function from a set of k + 1 or more elements to a set of k elements must have at least two elements in the domain that have the same image in the co-domain. If k+1 or more pigeons fly into k pigeonholes, at least one pigeonhole contains two or more pigeons.

📌 Examples:

• Among any 367 people, at least two have the same birthday (only 366 possible birthdays).
• In any set of 27 English words, at least two begin with the same letter (26 letters).

📌 Example: What is the minimum number of students to guarantee two are born in the same month? There are 12 months (pigeonholes). By the principle, any 13 (= 12 + 1) or more students guarantees at least two in the same month.

📌 Example: Given any 7 integers, must two have the same remainder when divided by 6? Possible remainders are {0, 1, 2, 3, 4, 5} (6 pigeonholes). With 7 (= 6 + 1) integers, by the pigeonhole principle, at least two will have the same remainder.

📌 Example: How many integers from 1 to 100 must be picked to guarantee one divisible by 5? There are 20 integers divisible by 5 and 80 that are not. To be sure of getting a multiple of 5, you must pick 80 + 1 = 81 integers (pigeonhole principle).

📌 Example: Let A = {1, 2, ..., 10}. Choose 6 integers from A. Must two have a sum of 11? Partition A into 5 subsets (pigeonholes): {1,10}, {2,9}, {3,8}, {4,7}, {5,6}, each summing to 11. Choosing 6 (= 5 + 1) integers guarantees two from the same subset, whose sum is 11.

Generalized Pigeonhole Principle

The principle can be extended to guarantee more than two elements sharing a property.

🔑 Definition — Generalized Pigeonhole Principle: A function from a set of n·k + 1 or more elements to a set of n elements must have at least k + 1 elements in the domain that have the same image in the co-domain. If n·k+1 or more pigeons fly into n pigeonholes, at least one pigeonhole contains k+1 or more pigeons.

📌 Example: A laundry bag has red, white, and blue socks. Find the minimum number to choose to guarantee 2 pairs (4 socks) of the same colour. Here, n = 3 colours (pigeonholes), and we want k+1 = 4, so k = 3. Thus, the minimum is n·k + 1 = 3·3 + 1 = 10 socks.

Floor and Ceiling Functions

These functions round a real number to the nearest integer.

🔑 Definition — Floor of x: Denoted ⌊x⌋, it is the largest integer smaller than or equal to x.

🔑 Definition — Ceiling of x: Denoted ⌈x⌉, it is the smallest integer greater than or equal to x.

📌 Example: Compute floor and ceiling for:

• 25/4 = 6.25: ⌊25/4⌋ = 6, ⌈25/4⌉ = 7
• 0.999: ⌊0.999⌋ = 0, ⌈0.999⌉ = 1
• -2.01: ⌊-2.01⌋ = -3, ⌈-2.01⌉ = -2 (since -3 < -2.01 and -2 > -2.01).

📌 Example: Find the smallest integer N such that ⌈N/7⌉ = 5. The smallest N is N = 7·(5 - 1) + 1 = 7·4 + 1 = 29.

📌 Example: Find the smallest integer N such that ⌈N/9⌉ = 6. The smallest N is N = 9·(6 - 1) + 1 = 9·5 + 1 = 46.

Alternative Form of the Pigeonhole Principle

This form uses the ceiling function.

🔑 Definition — Ceiling Form of the Pigeonhole Principle: If N pigeons fly into k pigeonholes, then at least one pigeonhole must contain ⌈N/k⌉ or more pigeons.

📌 Example: Among 100 people, at least ⌈100/12⌉ = ⌈8.333...⌉ = 9 were born in the same month.

📌 Example: Minimum number of students in a class to guarantee at least 6 receive the same grade (A, B, C, D, F = 5 grades)? We need the smallest N such that ⌈N/5⌉ = 6. The smallest N is N = 5(6-1) + 1 = 5·5 + 1 = 26.

⭐ Key Takeaways

The inclusion-exclusion principle is a cornerstone of counting that effectively handles overlapping sets by systematically adding and subtracting intersections of increasing size; for two sets it's n(A∪B) = n(A) + n(B) - n(A∩B). The pigeonhole principle, in its various forms, is a powerful tool for proving the existence of repetitions or guaranteed outcomes: k+1 items placed into k categories guarantees at least one category with at least two items. The generalized pigeonhole principle (using n·k+1 items for n categories to guarantee k+1 in one category) and its ceiling form (⌈N/k⌉ gives the minimum guaranteed in one hole) extend its applicability to more complex problems. Finally, ceiling and floor functions are used to precisely express the minimum number of items needed to guarantee a desired count in the generalized principle.

🧠 Quick Revision Questions

1. How many elements in the union of three sets A, B, and C if n(A)=5, n(B)=6, n(C)=7, n(A∩B)=2, n(B∩C)=3, n(A∩C)=1, and n(A∩B∩C)=1?
2. If you have 10 pigeons and 4 pigeonholes, what is the minimum number of pigeons guaranteed in at least one hole, according to the ceiling form of the pigeonhole principle?
3. State the generalized pigeonhole principle in your own words.
4. What is the smallest positive integer N such that ⌈N/3⌉ = 10?
5. Out of 30 students in a class, what is the minimum number that must share the same birth month, and which form of the pigeonhole principle allows you to determine this?

📘 Lecture 35 — Probability

📖 Overview: This lecture introduces the fundamental concepts of probability theory, beginning with its historical origins in gambling analysis. It defines key terms like experiment, sample space, and event, and explains how to calculate probabilities for equally likely outcomes. The lecture provides numerous examples involving dice, cards, lotteries, and defective items, and concludes with the concept of complementary events.

🗂️ Topics Covered

The lecture covers the introduction to probability theory and its historical development, definitions of experiment, sample space, and event with examples using dice. It then presents the formal definition of probability for equally likely outcomes, followed by numerous worked examples including drawing balls from urns, card problems, lottery probabilities, and poker hands. The final section introduces the complement of an event and the theorem P(Eᶜ) = 1 – P(E), with applications to defective items problems.

📝 Lecture Summary

INTRODUCTION TO PROBABILITY

Combinatorics and probability theory share common origins. The theory of probability was first developed in the seventeenth century when certain gambling games were analyzed by the French mathematician Blaise Pascal. It was in these studies that Pascal discovered various properties of the binomial coefficients. In the eighteenth century, the French mathematician Laplace, who also studied gambling, gave the definition of probability as the number of successful outcomes divided by the number of total outcomes.

DEFINITIONS

An experiment is a procedure that yields a given set of possible outcomes. The sample space of the experiment is the set of possible outcomes. An event is a subset of the sample space.

🔑 Definition — Experiment: a procedure that yields a given set of possible outcomes. 🔑 Definition — Sample Space: the set of all possible outcomes of an experiment. 🔑 Definition — Event: a subset of the sample space.

📌 Example: When a die is tossed, the sample space S = {1, 2, 3, 4, 5, 6}. Let E₁ be the event that a 6 occurs, E₂ be the event that an even number occurs, E₃ be the event that an odd number occurs, E₄ be the event that a prime number occurs, E₅ be the event that a number less than 5 occurs, and E₆ be the event that a number greater than 6 occurs. Then E₁ = {6}, E₂ = {2, 4, 6}, E₃ = {1, 3, 5}, E₄ = {2, 3, 5}, E₅ = {1, 2, 3, 4}, E₆ = Ф.

📌 Example: When a pair of dice is tossed, the sample space S has 36 outcomes: S = {(1,1), (1,2), ... , (6,6)}. Let E be the event in which the sum of the numbers is ten. Then E = {(4,6), (5,5), (6,4)}.

DEFINITION OF PROBABILITY

Let S be a finite sample space such that all the outcomes are equally likely to occur. The probability of an event E, which is a subset of sample space S, is:

📐 Formula: P(E) = number of outcomes in E / number of total outcomes in S = n(E) / n(S)

Since φ ⊆ E ⊆ S, therefore 0 ≤ n(E) ≤ n(S). It follows that the probability of an event is always between 0 and 1.

💡 Why this matters: Since n(φ) = 0 and n(S) = 1, the probability of any event is always between 0 and 1, inclusive.

📌 Example: What is the probability of getting a number greater than 4 when a die is tossed? Solution: Sample space S = {1,2,3,4,5,6}. Let E be the event that a number greater than 4 occurs. Then E = {5,6}. Hence, P(E) = n(E)/n(S) = 2/6 = 1/3.

📌 Example: What is the probability of getting a total of eight or nine when a pair of dice is tossed? Solution: When a pair of dice is tossed, sample space S has 36 outcomes. Let E be the event that the sum is eight or nine. Then E = {(2,6), (3,5), (4,4), (5,3), (6,2), (3,6), (4,5), (5,4), (6,3)}. Hence, P(E) = n(E)/n(S) = 9/36 = 1/4.

📌 Example: An urn contains four red and five blue balls. What is the probability that a ball chosen from the urn is blue? Solution: Total number of possible outcomes = 4 + 5 = 9. The total number of favorable outcomes for blue = 5. The probability that a ball chosen is blue = 5/9.

📌 Example: Two cards are drawn at random from an ordinary pack of 52 cards. Find the probability p that (i) both are spades, (ii) one is a spade and one is a heart. Solution: There are C(52,2) = 1326 ways to draw 2 cards from 52 cards. (i) There are C(13,2) = 78 ways to draw 2 spades from 13 spades; hence p = 78/1326 = 1/17. (ii) Since there are 13 spades and 13 hearts, there are C(13,1) × C(13,1) = 13 × 13 = 169 ways to draw a spade and a heart; hence p = 169/1326 = 13/102.

📌 Example: In a lottery, players win the first prize when they pick three digits that match, in the correct order, three digits kept secret. A second prize is won if only two digits match. What is the probability of winning (a) the first prize, (b) the second prize? Solution: Using the product rule, there are 10³ = 1000 ways to choose three digits. (a) There is only one way to choose all three digits correctly. Hence the probability that a player wins the first prize is 1/1000 = 0.001. (b) There are three possible cases: (i) The first digit is incorrect and the other two digits are correct, (ii) The second digit is incorrect and the other two digits are correct, (iii) The third digit is incorrect and the other digits are correct. For the first digit incorrect, there are nine choices for the first digit to be incorrect, and one each for the other two digits to be correct. Hence, there are nine ways for each case. So there are 9 + 9 + 9 = 27 ways to choose three digits with two of the three digits correct. The probability that a player wins the second prize is 27/1000 = 0.027.

📌 Example: What is the probability that a hand of five cards contains four cards of one kind? Solution: (i) The number of ways to pick one kind = C(13,1). The number of ways to pick the four of this kind out of the four of this kind in the deck = C(4,4). The number of ways to pick the fifth card from the remaining 48 cards = C(48,1). Hence, the number of hands of five cards with four cards of one kind = C(13,1) × C(4,4) × C(48,1) = 13 × 1 × 48 = 624. (ii) The total number of different hands of five cards = C(52,5) = 2,598,960. Probability = 624/2,598,960 ≈ 0.0024.

📌 Example: Find the probability that a hand of five cards contains three cards of one kind and two of another kind. Solution: (i) The number of ways to pick two kinds = C(13,2). The number of ways to pick three out of four of the first kind = C(4,3). The number of ways to pick two out of four of the second kind = C(4,2). Hence, the number of hands with three cards of one kind and two of another kind = C(13,2) × C(4,3) × C(4,2). (ii) The total number of different hands of five cards = C(52,5) = 2,598,960. Probability = 3744/2,598,960 ≈ 0.0014.

📌 Example: What is the probability that a randomly chosen positive two-digit number is a multiple of 6? Solution: 1. There are ⌊99/6⌋ = 16 positive integers from 1 to 99 that are divisible by 6. Out of these, 16 – 1 = 15 are two-digit numbers (as 6 is a multiple of 6 but not a two-digit number). 2. There are 99 – 9 = 90 positive two-digit numbers in all. Hence, the probability = 15/90 = 1/6 ≈ 0.166667.

COMPLEMENT OF AN EVENT

Let E be an event in a sample space S, the complement of E is the event that occurs if E does not occur. It is denoted by Eᶜ. Note that Eᶜ = S\E.

🔑 Definition — Complement of an event E: the event that occurs if E does not occur, denoted Eᶜ = S\E.

📌 Example: Let E be the event that an even number occurs when a die is tossed. Then Eᶜ is the event that an odd number occurs.

THEOREM: Let E be an event in a sample space S. The probability of the complementary event Eᶜ of E is given by:

📐 Formula: P(Eᶜ) = 1 – P(E)

📌 Example: Let 2 items be chosen at random from a lot containing 12 items of which 4 are defective. What is the probability that (i) none of the items chosen are defective, (ii) at least one item is defective? Solution: The number of ways 2 items can be chosen from 12 items = C(12,2) = 66. (i) Let A be the event that none of the items chosen are defective. The number of favorable outcomes for A = the number of ways 2 items can be chosen from 8 non-defective items = C(8,2) = 28. Hence, P(A) = 28/66 = 14/33. (ii) Let B be the event that at least one item chosen is defective. Then clearly B = Aᶜ. It follows that P(B) = P(Aᶜ) = 1 – P(A) = 1 – 14/33 = 19/33.

📌 Example: Three light bulbs are chosen at random from 15 bulbs of which 5 are defective. Find the probability p that (i) none is defective, (ii) exactly one is defective, (iii) at least one is defective. Solution: There are C(15,3) = 455 ways to choose 3 bulbs from the 15 bulbs. (i) Since there are 15 – 5 = 10 non-defective bulbs, there are C(10,3) = 120 ways to choose 3 non-defective bulbs. Thus p = 120/455 = 24/91. (ii) There are 5 defective bulbs and C(10,2) = 45 different pairs of non-defective bulbs; hence there are C(5,1) × C(10,2) = 5 × 45 = 225 ways to choose 3 bulbs of which one is defective. Thus p = 225/455 = 45/91. (iii) The event that at least one is defective is the complement of the event that none are defective which has probability 24/91. Hence p(at least one is defective) = 1 – 24/91 = 67/91.

⭐ Key Takeaways

The probability of an event is the ratio of favorable outcomes to total equally likely outcomes, always between 0 and 1. The sample space is the set of all possible outcomes, and events are subsets of the sample space. Combinatorics (combinations and the product rule) is essential for counting favorable and total outcomes in probability problems. The complement of an event E (Eᶜ) represents the event that E does not occur, and its probability is 1 – P(E), which is particularly useful for "at least one" problems. Understanding how to identify equally likely outcomes and apply the basic probability formula P(E) = n(E)/n(S) is fundamental to solving all probability problems in this lecture.

🧠 Quick Revision Questions

1. What is the sample space when a single die is tossed, and what is the probability of rolling a number greater than 4?
2. Two cards are drawn from a standard 52-card deck. What is the probability that both are spades?
3. In a three-digit lottery where digits are chosen in correct order, what is the probability of winning the first prize? The second prize (exactly two digits match)?
4. What is the formula for the probability of the complement of an event E, and how would you use it to find the probability of drawing at least one defective item from a batch?
5. A hand of five cards is drawn from a standard deck. What is the probability that the hand contains four cards of one kind (e.g., four aces)?

📘 Lecture 36 — Laws of Probability VU

📖 Overview: This lecture covers the fundamental addition laws of probability, focusing on both the simple addition law for mutually exclusive events and the general addition law for non-disjoint events. It provides extensive examples and exercises to demonstrate these concepts, including applications to dice rolls, card draws, and survey data.

🗂️ Topics Covered

The lecture covers the addition law for disjoint (mutually exclusive) events with its proof and examples, the general addition law for any two events with proof and multiple exercises, the probability of sub-events theorem, and the extension of the addition law to three events. Key applications include problems involving balls in bags, dice throws, card draws, class demographics, integer divisibility, and class attendance.

📝 Lecture Summary

ADDITION LAW OF PROBABILITY

THEOREM: If A and B are two disjoint (mutually exclusive) events of a sample space S, then P(A ∪ B) = P(A) + P(B). In words, the probability of the happening of an event A or an event B or both is equal to the sum of the probabilities of event A and event B provided the events have nothing in common.

PROOF: By the inclusion-exclusion principle for mutually disjoint sets, n(A ∪ B) = n(A) + n(B). Dividing both sides by n(S), we get n(A ∪ B)/n(S) = n(A)/n(S) + n(B)/n(S) ⇒ P(A ∪ B) = P(A) + P(B).

🔑 Definition — Disjoint (Mutually Exclusive) Events: Events that have no outcomes in common; they cannot occur simultaneously.

📌 Example: Suppose a die is rolled. Let A be the event that 1 appears and B be the event that some even number appears on the die. Then S = {1, 2, 3, 4, 5, 6}, A = {1} and B = {2, 4, 6}. Clearly A and B are disjoint events and P(A) = 1/6, P(B) = 3/6. Hence the probability that a 1 appears or some even number appears is P(A ∪ B) = 1/6 + 3/6 = 4/6 = 2/3.

📌 Example (Exercise): A bag contains 6 white, 5 black and 4 red balls. Find the probability of getting a white or a black ball in a single draw. Total balls = 6 + 5 + 4 = 15. Let A be getting a white and B be getting a black ball. Events are disjoint. P(A) = 6/15, P(B) = 5/15. P(A ∪ B) = 6/15 + 5/15 = 11/15.

📌 Example (Exercise): A pair of dice is thrown. Find the probability of getting a total of 5 or 11. Sample space has 36 outcomes. Let A be a total of 5: A = {(1,4), (2,3), (3,2), (4,1)} and B be a total of 11: B = {(5,6), (6,5)}. Events are disjoint. P(A ∪ B) = 4/36 + 2/36 = 6/36 = 1/6.

📌 Example (Exercise): For any two events A and B of a sample space S, prove that P(A\B) = P(A ∩ B') = P(A) - P(A ∩ B). Proof: The event A can be written as the union of two disjoint events A\B and A ∩ B. i.e., A = (A\B) ∪ (A ∩ B). Hence, by addition law of probability: P(A) = P(A\B) + P(A ∩ B) ⇒ P(A\B) = P(A) - P(A ∩ B).

🔑 Definition — Event A\B (A minus B): The event that A occurs but B does not occur, also written as A ∩ B'.

GENERAL ADDITION LAW OF PROBABILITY

THEOREM: If A and B are any two events of a sample space S, then P(A ∪ B) = P(A) + P(B) - P(A ∩ B).

PROOF: The event A ∪ B may be written as the union of two disjoint events A\B and B. i.e., A ∪ B = (A\B) ∪ B. Hence, by addition law of probability (for disjoint events): P(A ∪ B) = P(A\B) + P(B) = [P(A) - P(A ∩ B)] + P(B) = P(A) + P(B) - P(A ∩ B). (proved)

REMARK: By inclusion-exclusion principle: n(A ∪ B) = n(A) + n(B) - n(A ∩ B). Dividing both sides by n(S) and denoting the ratios as respective probabilities gives the generalized addition law.

📌 Example (Exercise): Let A and B be events in a sample space S, with P(A) = 0.65, P(B) = 0.30 and P(A ∩ B) = 0.15. Determine: (a) P(A ∩ B') = P(A) - P(A ∩ B) = 0.65 - 0.15 = 0.50 (b) P(A ∪ B) = P(A) + P(B) - P(A ∩ B) = 0.65 + 0.30 - 0.15 = 0.80 (c) P(A' ∩ B') = P((A ∪ B)') = 1 - P(A ∪ B) = 1 - 0.80 = 0.20

📌 Example (Exercise): Let A, B, C and D be events which form a partition of a sample space S. If P(A) = P(B), P(C) = 2P(A) and P(D) = 2P(C). Determine each of the following probabilities. (a) P(A): Since they form a partition, S = A ∪ B ∪ C ∪ D and are pairwise disjoint. 1 = P(A) + P(A) + 2P(A) + 2(2P(A)) = 8P(A) ⇒ P(A) = 1/8 (b) P(A ∪ B) = P(A) + P(B) = 1/8 + 1/8 = 1/4 (c) P(A ∪ C ∪ D) = P(A) + P(C) + P(D) = 1/8 + 2(1/8) + 2(2/8) = 1/8 + 2/8 + 4/8 = 7/8

🔑 Definition — Partition of a Sample Space: A collection of events that are pairwise disjoint (mutually exclusive) and whose union equals the entire sample space.

📌 Example (Exercise): A card is drawn from a well-shuffled pack of playing cards. What is the probability that it is either a spade or an ace? Let A be drawing a spade and B be drawing an ace. A and B are not disjoint. A ∩ B is the ace of spades. P(A) = 13/52, P(B) = 4/52, P(A ∩ B) = 1/52. P(A ∪ B) = 13/52 + 4/52 - 1/52 = 16/52 = 4/13.

📌 Example (Exercise): A class contains 10 boys and 20 girls of which half the boys and half the girls have brown eyes. Find the probability that a student chosen at random is a boy or has brown eyes. Let A be that a boy is chosen and B be that a student with brown eyes is chosen. P(A) = 10/30, P(B) = (5+10)/30 = 15/30, P(A∩B) = 5/30. P(A∪B) = 10/30 + 15/30 - 5/30 = 20/30 = 2/3.

📌 Example (Exercise): An integer is chosen at random from the first 100 positive integers. What is the probability that the integer chosen is divisible by 6 or by 8? Let A be divisible by 6 and B be divisible by 8. A∩B is divisible by LCM(6,8)=24. n(A) = floor(100/6) = 16, n(B) = floor(100/8) = 12, n(A∩B) = floor(100/24) = 4. P(A∪B) = 16/100 + 12/100 - 4/100 = 24/100 = 6/25.

📌 Example (Exercise): A student attends mathematics class with probability 0.7, skips accounting class with probability 0.4, and attends both with probability 0.5. Find: (1) P(attends at least one class) and (2) P(attends exactly one class). (1) P(A) = 0.7, P(B) = 1 - 0.4 = 0.6, P(A∩B) = 0.5. P(A∪B) = 0.7 + 0.6 - 0.5 = 0.8. (2) P(exactly one) = P(A∩B') + P(A'∩B) = [0.7-0.5] + [0.6-0.5] = 0.2 + 0.1 = 0.3.

PROBABILITY OF SUB EVENT

THEOREM: If A and B are two events such that A ⊆ B, then P(A) ≤ P(B).

PROOF: Suppose A ⊆ B. The event B may be written as the union of disjoint events B∩A and B∩A'. But B∩A = A (as A ⊆ B). So B = A ∪ (B∩A'). ∴ P(B) = P(A) + P(B∩A'). Since P(B∩A') ≥ 0, P(B) ≥ P(A) or P(A) ≤ P(B).

📌 Example (Exercise): Let A and B be subsets of a sample space S with P(A) = 0.7 and P(B) = 0.5. What are the maximum and minimum possible values of P(A∪B)? By addition law: P(A∪B) = 0.7 + 0.5 - P(A∩B) = 1.2 - P(A∩B). Max P(A∪B) = 1, for which P(A∩B) = 0.2. Since A∩B ⊆ B, P(A∩B) ≤ P(B) = 0.5. For min P(A∪B), take max P(A∩B) = 0.5. Hence min P(A∪B) = 1.2 - 0.5 = 0.7.

ADDITION LAW OF PROBABILITY FOR THREE EVENTS

If A, B and C are any three events, then P(A ∪ B ∪ C) = P(A) + P(B) + P(C) - P(A∩B) - P(A∩C) - P(B∩C) + P(A∩B∩C).

REMARK: If A, B, C are mutually disjoint events, then P(A ∪ B ∪ C) = P(A) + P(B) + P(C).

📌 Example (Exercise): Three newspapers A, B, C are published in a city. Survey: 20% read A, 16% read B, 14% read C, 8% read both A and B, 5% read both A and C, 4% read both B and C, 2% read all three. Find probability that a person reads none of the papers. P(A) = 0.2, P(B) = 0.16, P(C) = 0.14, P(A∩B) = 0.08, P(A∩C) = 0.05, P(B∩C) = 0.04, P(A∩B∩C) = 0.02. P(A∪B∪C) = 0.2 + 0.16 + 0.14 - 0.08 - 0.05 - 0.04 + 0.02 = 0.35 P(reads none) = 1 - P(A∪B∪C) = 1 - 0.35 = 0.65 = 65%

📌 Example (Exercise): Let A, B and C be events in sample space S, with A∪B∪C = S, A∩(B∪C) = ∅, P(A) = 0.2, P(B) = 0.5, P(C) = 0.7. Find P(A^C), P(B∪C), P(B∩C). P(A^C) = 1 - 0.2 = 0.8. Since A and B∪C are disjoint, P(A∪(B∪C)) = P(A) + P(B∪C). But A∪B∪C = S, so 1 = 0.2 + P(B∪C) ⇒ P(B∪C) = 0.8. By addition law: 0.8 = 0.5 + 0.7 - P(B∩C) ⇒ P(B∩C) = 0.4.

💡 Why this matters: The addition laws are foundational for calculating probabilities of combined events, which is essential for risk assessment, decision-making, and data analysis in fields such as finance, insurance, and scientific research.

⭐ Key Takeaways

The addition law for disjoint events states P(A∪B) = P(A) + P(B), while the general addition law for any two events states P(A∪B) = P(A) + P(B) - P(A∩B). The subtraction of P(A∩B) in the general law corrects for double-counting when events overlap. For three events, the formula extends to include all pairwise intersections and adds back the triple intersection. The sub-event theorem shows that if A ⊆ B, then P(A) ≤ P(B). Understanding when events are mutually exclusive versus non-exclusive is critical for applying the correct formula.

🧠 Quick Revision Questions

1. State the addition law for disjoint events and give a simple example.
2. What is the general addition law for any two events, and why must P(A∩B) be subtracted?
3. If P(A) = 0.6, P(B) = 0.4, and P(A∩B) = 0.2, what is P(A∪B)?
4. Prove that if A ⊆ B, then P(A) ≤ P(B).
5. Write out the addition law for three events A, B, and C.

📘 Lecture 37 — Conditional Probability

📖 Overview: This lecture introduces the fundamental concept of conditional probability, which measures the probability of an event occurring given that another event has already occurred. It covers the multiplication theorem for computing joint probabilities and the concept of independent events, which are essential for understanding relationships between events in probability theory.

🗂️ Topics Covered

The lecture covers conditional probability definition and formula, the multiplication theorem for two and multiple events, and the concept of independent events. Examples include dice tossing, ball selection from urns, family with two children, defective items inspection, bit strings, and target shooting problems. Exercises demonstrate calculations of conditional probabilities including complements and mutually exclusive events.

📝 Lecture Summary

CONDITIONAL PROBABILITY

Conditional probability measures the likelihood of an event occurring given that another event has already occurred. When additional information becomes available, the sample space is reduced to only those outcomes that satisfy the given condition.

🔑 Definition — Conditional Probability: Let E and F be two events in the sample space of an experiment with P(F) ≠ 0. The conditional probability of E given F, denoted by P(E|F), is defined as:

📐 Formula: P(E|F) = P(E ∩ F) / P(F) → The probability that E occurs, knowing that F has already occurred, equals the probability that both occur divided by the probability of the given event F.

📌 Example: When a die is tossed, the probability of getting a 2 is 1/6. If we know an even number appears (2,4,6), the probability that the number is 2 becomes 1/3, since only one of three even numbers is 2.

📌 Example: An urn contains 3 red, 2 blue, and 4 white balls. P(red) = 3/9. If we know the selected ball is not white (so only 5 balls: 3 red + 2 blue), then P(red|not white) = 3/5.

📌 Example: Let P(B) = 1/4 and P(A∩B) = 1/6. Then P(A|B) = (1/6)/(1/4) = 4/6 = 2/3.

📌 Example: Let P(A) = 1/2, P(B) = 1/3, P(A∩B) = 1/4. Then:

• P(A|B) = (1/4)/(1/3) = 3/4
• P(B|A) = (1/4)/(1/2) = 1/2
• P(A∪B) = 1/2 + 1/3 - 1/4 = 7/12
• P(A^c|B^c) = P(A^c ∩ B^c)/P(B^c) = [1 - P(A∪B)]/[1 - P(B)] = (1 - 7/12)/(1 - 1/3) = (5/12)/(2/3) = 5/8

📌 Example: Find P(B|A) if A is a subset of B. When A ⊆ B, then B ∩ A = A, so P(B|A) = P(A)/P(A) = 1.

📌 Example: Find P(B|A) if A and B are mutually exclusive. When A and B are mutually exclusive, B ∩ A = ∅, so P(B|A) = 0/P(A) = 0.

📌 Example: An urn contains 3 red balls (marked 1,2,3), 1 blue ball (marked 4), and 4 white balls (marked 5,6,7,8). Total = 8 balls.

• P(red) = 3/8
• P(even number) = 4/8 (numbers 2,4,6,8)
• P(red|even) = P(red ∩ even)/P(even) = (1/8)/(4/8) = 1/4 (only ball 2 is red and even)
• P(even|red) = P(red ∩ even)/P(red) = (1/8)/(3/8) = 1/3

📌 Example: A pair of dice is tossed. If the sum is 7, find the probability that one of the dice is 2. Let E = {at least one 2 appears}, F = {sum is 7} = {(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)}. E∩F = {(2,5),(5,2)}. P(F) = 6/36, P(E∩F) = 2/36. P(E|F) = (2/36)/(6/36) = 1/3.

💡 Why this matters: Conditional probability allows us to update probabilities when new information becomes available. The key insight is that the denominator is always the probability of the condition event.

📌 Example: A family has two children. One child, a boy, comes into the room. Sample space: S = {bb, bg, gb, gg} where first letter is younger, second is elder.

• (i) If the other child is known to be elder (so younger is the boy we saw): Let A = {both boys} = {bb}, B = {younger is a boy} = {bb, bg}. P(A|B) = (1/4)/(2/4) = 1/2.
• (ii) If nothing is known about the other child: Let C = {one child is a boy} = {bb, bg, gb}. P(A|C) = (1/4)/(3/4) = 1/3.

MULTIPLICATION THEOREM

The multiplication theorem provides a formula for computing the probability of the intersection of two or more events using conditional probabilities.

🔑 Definition — Multiplication Theorem: Let E and F be two events. Then P(E∩F) = P(F)P(E|F) or P(E∩F) = P(E)P(F|E).

For n events E₁, E₂, ..., Eₙ: P(E₁∩E₂∩...∩Eₙ) = P(E₁)P(E₂|E₁)P(E₃|E₁∩E₂)...P(Eₙ|E₁∩E₂∩...∩Eₙ₋₁)

📌 Example: A lot contains 12 items, 4 are defective. Three items are drawn at random one after another. Find P(all three are non-defective). Let A₁ = {first non-defective}, A₂ = {second non-defective}, A₃ = {third non-defective}. P(A₁) = 8/12, P(A₂|A₁) = 7/11, P(A₃|A₁∩A₂) = 6/10. P(A₁∩A₂∩A₃) = (8/12)(7/11)(6/10) = 336/1320 = 14/55.

INDEPENDENCE

Two events are independent if the occurrence of one does not affect the probability of the other.

🔑 Definition — Independent Events: An event A is said to be independent of event B if P(A|B) = P(A). Equivalently, A and B are independent if and only if P(A∩B) = P(A)P(B).

If A and B are independent, then P(B|A) = P(A∩B)/P(A) = P(A)P(B)/P(A) = P(B).

📌 Example: Random bit string of length 4. A = {begins with 1}, B = {contains an even number of 0s}. P(A) = 8/16 = 1/2, P(B) = 8/16 = 1/2. A∩B = {1001, 1010, 1100, 1111}, P(A∩B) = 4/16 = 1/4. Since P(A∩B) = 1/4 = (1/2)(1/2) = P(A)P(B), A and B are independent.

📌 Example: A fair coin tossed three times. A = {first toss heads}, B = {second toss heads}, C = {exactly two heads in a row}. S = {HHH, HHT, HTH, HTT, THH, THT, TTH, TTT} A = {HHH, HHT, HTH, HTT}, P(A) = 1/2 B = {HHH, HHT, THH, THT}, P(B) = 1/2 C = {HHT, THH}, P(C) = 1/4 A∩B = {HHH, HHT}, P(A∩B) = 2/8 = 1/4 = P(A)P(B) → A and B are independent A∩C = {HHT}, P(A∩C) = 1/8 = P(A)P(C) → A and C are independent B∩C = {HHT, THH}, P(B∩C) = 2/8 = 1/4 ≠ P(B)P(C) = 1/8 → B and C are dependent

📌 Example: P(A hits target) = 1/3, P(B hits target) = 2/5. They shoot independently. P(target is hit) = P(A∪B) = P(A) + P(B) - P(A∩B) = P(A) + P(B) - P(A)P(B) (due to independence) = 1/3 + 2/5 - (1/3)(2/5) = 1/3 + 2/5 - 2/15 = 5/15 + 6/15 - 2/15 = 9/15 = 3/5.

⭐ Key Takeaways

Conditional probability P(E|F) = P(E∩F)/P(F) fundamentally changes the sample space to only outcomes satisfying condition F. The multiplication theorem P(E∩F) = P(F)P(E|F) allows computation of joint probabilities from conditional ones. Two events are independent if and only if P(A∩B) = P(A)P(B), which is equivalent to P(A|B) = P(A). Independence does not mean mutually exclusive — in fact, mutually exclusive events with positive probabilities are always dependent (P(A∩B)=0 while P(A)P(B)>0). Pairwise independence does not guarantee mutual independence among three or more events.

🧠 Quick Revision Questions

1. What is the formula for conditional probability P(E|F) and why must P(F) ≠ 0?
2. If A ⊆ B, what is P(B|A) and why?
3. A lot has 10 items with 3 defective. Three items are drawn without replacement. What is the probability all three are defective? (Use multiplication theorem.)
4. How can you determine whether two events A and B are independent? State both equivalent conditions.
5. If P(A) = 0.4, P(B) = 0.5, and P(A∩B) = 0.2, are A and B independent? Calculate P(A|B) and P(B|A) to verify.

📘 Lecture 38 — Random Variable

📖 Overview: This lecture introduces the concept of a random variable as a function that assigns numerical values to outcomes of a random experiment. It covers how to construct probability distributions, compute expectations (means), and calculate variance and standard deviation to measure dispersion. Understanding random variables is fundamental to probability and statistics, as they form the basis for modeling real-world uncertainties.

🗂️ Topics Covered

The lecture covers the definition of a random variable with examples (tossing dice, sampling defective items), the construction of probability distribution functions from sample spaces, the computation of expectation (mean) of a random variable with multiple worked examples (coin tossing, weighted coins), and finally the calculation of variance and standard deviation as measures of spread, including a detailed example involving the maximum of two dice.

📝 Lecture Summary

RANDOM VARIABLE

A random variable X is a rule that assigns a numerical value to each outcome in a sample space S. It is a function which maps each outcome of the sample space into the set of real numbers. We let X(S) denote the set of numbers assigned, referred to as the range space.

🔑 Definition — Random Variable: A function from the sample space S to the set of real numbers R, where X(S) is the range of X.

Remark: A random variable is also called a chance variable or a stochastic variable (not simply a variable, because it is a function). Random variables are usually denoted by capital letters such as X, Y, Z; values taken are represented by corresponding small letters.

📌 Example: A pair of fair dice is tossed. Sample space S consists of 36 ordered pairs.

• Let X assign to each point the sum of the numbers: X(S) = {2,3,4,5,6,7,8,9,10,11,12}
• Let Y assign the maximum of the two numbers: Y(S) = {1,2,3,4,5,6}

PROBABILITY DISTRIBUTION OF A RANDOM VARIABLE

Let X(S) = {x₁, x₂, ..., xₙ} be the range space of a random variable X. Define a function f on X(S) as: f(xᵢ) = P(X = xᵢ) = sum of probabilities of points in S whose image is xᵢ. This function f is called the probability distribution or the probability function of X.

🔑 Definition — Probability Distribution: A function f that assigns to each value xᵢ the probability P(X = xᵢ), satisfying: (i) f(xᵢ) ≥ 0 and (ii) Σ f(xᵢ) = 1 for i = 1 to n.

📌 Example: A pair of fair dice is tossed. Let X assign the sum of numbers. Distribution of X:

• f(2) = P(X=2) = 1/36
• f(3) = P(X=3) = 2/36
• f(4) = P(X=4) = 3/36
• f(5) = P(X=5) = 4/36
• f(6) = P(X=6) = 5/36
• f(7) = P(X=7) = 6/36
• f(8) = P(X=8) = 5/36
• f(9) = P(X=9) = 4/36
• f(10) = P(X=10) = 3/36
• f(11) = P(X=11) = 2/36
• f(12) = P(X=12) = 1/36

📌 Example: A box contains 12 items, 3 defective. Sample of 3 items selected. X = number of defective items in sample. Total samples = C(12,3) = 220.

• P(X=0) = [C(3,0)×C(9,3)]/220 = 84/220
• P(X=1) = [C(3,1)×C(9,2)]/220 = 108/220
• P(X=2) = [C(3,2)×C(9,1)]/220 = 27/220
• P(X=3) = [C(3,3)×C(9,0)]/220 = 1/220

EXPECTATION OF A RANDOM VARIABLE

The mean (μ) or expectation of X [written E(X)] is defined by: μ = E(X) = x₁f(x₁) + x₂f(x₂) + ... + xₙf(xₙ) = Σ xᵢ f(xᵢ) for i = 1 to n.

📐 Formula: E(X) = Σ xᵢ f(xᵢ) → Sum of each value multiplied by its probability.

📌 Example: Expectation of number of heads when three fair coins are tossed. Sample space: S = {TTT, TTH, THT, HTT, THH, HTH, HHT, HHH} Distribution: x = {0,1,2,3} with probabilities {1/8, 3/8, 3/8, 1/8} E(X) = 0(1/8) + 1(3/8) + 2(3/8) + 3(1/8) = 12/8 = 1.5

📌 Example: A player tosses two fair coins. Wins Rs.1 if one head, Rs.2 if two heads, loses Rs.5 if no heads. Expected value of game? P(Two heads) = 1/4, P(One head) = 1/2, P(No heads) = 1/4 E = 2(1/4) + 1(1/2) + (-5)(1/4) = 0.5 + 0.5 - 1.25 = -0.25 Since expected value is negative, the game is unfavorable to the player.

📌 Example: Weighted coin with P(H)=3/4, P(T)=1/4 tossed three times. X = number of heads. Distribution: P(0)=1/64, P(1)=9/64, P(2)=27/64, P(3)=27/64 E(X) = 0(1/64) + 1(9/64) + 2(27/64) + 3(27/64) = 144/64 = 2.25

VARIANCE AND STANDARD DEVIATION OF A RANDOM VARIABLE

The variance of X measures the "spread" or "dispersion" of X from the mean μ.

🔑 Definition — Variance: Var(X) = σ² = Σ (xᵢ - μ)² f(xᵢ) for i = 1 to n = E((X - μ)²) = E(X²) - μ²

The standard deviation of X, denoted σₓ, is the non-negative square root of Var(X): σₓ = √Var(X)

📐 Formula: σ² = E(X²) - μ² (convenient form for computation)

📌 Example: Find μ, σ², and σ for distribution: xᵢ: 1, 3, 4, 5 with f(xᵢ): 0.4, 0.1, 0.2, 0.3 μ = E(X) = 1(0.4) + 3(0.1) + 4(0.2) + 5(0.3) = 0.4 + 0.3 + 0.8 + 1.5 = 3.0 E(X²) = 1²(0.4) + 3²(0.1) + 4²(0.2) + 5²(0.3) = 0.4 + 0.9 + 3.2 + 7.5 = 12.0 σ² = 12.0 - (3.0)² = 3.0 σ = √3.0 ≈ 1.7

📌 Example: Pair of fair dice thrown. X = maximum of two numbers. Distribution: f(1)=1/36, f(2)=3/36, f(3)=5/36, f(4)=7/36, f(5)=9/36, f(6)=11/36 μ = 1(1/36) + 2(3/36) + 3(5/36) + 4(7/36) + 5(9/36) + 6(11/36) = 161/36 ≈ 4.5 E(X²) = 1²(1/36) + 2²(3/36) + 3²(5/36) + 4²(7/36) + 5²(9/36) + 6²(11/36) = 791/36 ≈ 22.0 σ² = 22.0 - (4.5)² = 17.5 σₓ = √17.5 ≈ 1.3

💡 Why this matters: Variance and standard deviation quantify how much a random variable's values deviate from the mean, which is crucial for risk assessment, quality control, and understanding uncertainty in predictions.

⭐ Key Takeaways

A random variable is a function that assigns numerical values to sample space outcomes, not just a simple variable. Its probability distribution satisfies non-negativity and sums to one. The expectation E(X) = Σ xᵢ f(xᵢ) represents the weighted average or long-run average value. Variance σ² = E(X²) - μ² measures dispersion around the mean, while standard deviation σ = √σ² provides the same measure in original units. These concepts are essential for analyzing and interpreting probabilistic systems.

🧠 Quick Revision Questions

1. What is a random variable and how is it different from an ordinary variable?
2. What two conditions must a probability distribution f(xᵢ) always satisfy?
3. How do you compute the expectation E(X) from a probability distribution table?
4. What is the formula for variance in terms of E(X²) and the mean μ?
5. In the dice example, why does f(7) have the highest probability (6/36) among all sums?

📘 Lecture 39 — Introduction to Graphs

📖 Overview: This lecture introduces graph theory, a fundamental mathematical structure used extensively in computer science. It covers basic graph terminology, types of graphs (simple, complete, regular, bipartite), and the Handshaking Theorem, which relates the sum of vertex degrees to the number of edges. Understanding these concepts is crucial for modeling networks, relationships, and structures in computing.

🗂️ Topics Covered

The lecture begins with a formal definition of a graph as vertices and edges, then explains essential terminology like endpoints, loops, adjacent vertices, isolated vertices, and parallel edges. It covers how to draw graphs from given vertex/edge sets and defines a simple graph. The degree of a vertex is introduced, leading to the Handshaking Theorem and its corollary. Finally, special types of graphs are explored: complete graphs (Kₙ), regular graphs, bipartite graphs, and complete bipartite graphs (Kₘ,ₙ), with the labeling procedure to determine bipartiteness.

📝 Lecture Summary

INTRODUCTION TO GRAPHS

Graph theory plays an important role in several areas of computer science such as switching theory and logical design, artificial intelligence, formal languages, computer graphics, operating systems, compiler writing, and information organization and retrieval.

A graph is a non-empty set of points called vertices and a set of line segments joining pairs of vertices called edges. Formally, a graph G consists of two finite sets: (i) A set V=V(G) of vertices (or points or nodes) (ii) A set E=E(G) of edges; where each edge corresponds to a pair of vertices.

SOME TERMINOLOGY

1. An edge connects either one or two vertices called its endpoints (edge e₁ connects vertices v₁ and v₂ described as {v₁, v₂}).
2. An edge with just one endpoint is called a loop. Thus a loop is an edge that connects a vertex to itself.
3. Two vertices that are connected by an edge are called adjacent; and a vertex that is an endpoint of a loop is said to be adjacent to itself.
4. An edge is said to be incident on each of its endpoints.
5. A vertex on which no edges are incident is called isolated.
6. Two distinct edges with the same set of end points are said to be parallel.

📌 Example: For a graph with vertex set {v₁, v₂, v₃, v₄} and edge set {e₁, e₂, e₃}, where e₁ connects {v₁, v₂}, e₂ connects {v₁, v₃}, and e₃ connects {v₃} (a loop), we find: (i) v₁ is incident with edges e₁, e₂ and e₇; (ii) vertices adjacent to v₃ are v₁ and v₂; (iii) loops are e₁ and e₃; (iv) only edges e₄ and e₅ are parallel; (v) the only isolated vertex is v₄.

SIMPLE GRAPH

A simple graph is a graph that does not have any loop or parallel edges.

📌 Example: Draw all simple graphs with the four vertices {u, v, w, x} and two edges, one of which is {u, v}. There are C(4,2) = 6 ways of choosing two vertices from 4 vertices. These edges may be listed as: {u,v}, {u,w}, {u,x}, {v,w}, {v,x}, {w,x}. One edge is specified to be {u,v}, so any of the remaining five may be chosen to be the second edge, resulting in 5 possible graphs.

DEGREE OF A VERTEX

Let G be a graph and v a vertex of G. The degree of v, denoted deg(v), equals the number of edges that are incident on v, with an edge that is a loop counted twice.

🔑 Definition — Degree: The degree of a vertex is the number of edges incident on it, counting loops twice.

Note: (i) The total degree of G is the sum of the degrees of all the vertices of G. (ii) The degree of a loop is counted twice.

📌 Example: For a graph with vertices v₁ (isolated), v₂, and v₃ (with a loop): deg(v₁) = 0, deg(v₂) = 2, deg(v₃) = 4. Total degree of G = 0 + 2 + 4 = 6, which equals twice the number of edges (3).

THE HANDSHAKING THEOREM

If G is any graph, then the sum of the degrees of all the vertices of G equals twice the number of edges of G. Specifically, if the vertices of G are v₁, v₂, ..., vₙ, then: total degree of G = deg(v₁) + deg(v₂) + ... + deg(vₙ) = 2 · (the number of edges of G)

📐 Formula: Σ deg(vᵢ) = 2|E|

PROOF: Each edge “e” of G connects its end points vᵢ and vⱼ. This edge contributes 1 to the degree of vᵢ and 1 to the degree of vⱼ. If “e” is a loop, then it is counted twice. Accordingly, each edge contributes 2 to the total degree of G.

COROLLARY: The total degree of G is an even number.

📌 Example: A graph with four vertices of degrees 1, 2, 3 and 3 has total degree = 9 (odd), which is not possible since total degree must be even.

📌 Example: A graph with vertices of degrees 1, 1, 4, 4 and 6 has total degree = 16. Using the Handshaking Theorem, 16 = 2·(number of edges), so number of edges = 8.

📌 Example: In a group of 15 people, is it possible for each person to have exactly 3 friends? Such a graph would have 15 vertices each of degree 3, for a total degree of 45 (odd), which is not possible. Hence, it is not possible.

COMPLETE GRAPH

A complete graph on n vertices is a simple graph in which each vertex is connected to every other vertex and is denoted by Kₙ.

The following are complete graphs K₁, K₂, K₃, K₄ and K₅.

📌 Example: For the complete graph Kₙ: (i) deg(v) = n - 1 for every v in Kₙ. (ii) Total degree in Kₙ = n(n - 1). (iii) Number of edges in Kₙ = C(n, 2) = n(n-1)/2.

REGULAR GRAPH

A graph G is regular of degree k or k-regular if every vertex of G has degree k. In other words, a graph is regular if every vertex has the same degree.

Remark: The complete graph Kₙ is (n-1) regular.

📌 Example: Draw two 3-regular graphs with six vertices. Possible examples include cycles and other configurations where each of the six vertices has exactly 3 incident edges.

BIPARTITE GRAPH

A bipartite graph G is a simple graph whose vertex set can be partitioned into two mutually disjoint non empty subsets A and B such that the vertices in A may be connected to vertices in B, but no vertices in A are connected to vertices in A and no vertices in B are connected to vertices in B.

DETERMINING BIPARTITE GRAPHS: The following labeling procedure determines whether a graph is bipartite or not:

1. Label any vertex a
2. Label all vertices adjacent to a with the label b.
3. Label all vertices that are adjacent to a vertex just labeled b with label a.
4. Repeat steps 2 and 3 until all vertices got a distinct label (a bipartite graph) or there is a conflict i.e., a vertex is labeled with a and b (not a bipartite graph).

📌 Example: If the labeling procedure results in a vertex being labeled both a and b, the graph is not bipartite. If each vertex gets a distinct label, the graph is bipartite.

COMPLETE BIPARTITE GRAPH

A complete bipartite graph on (m+n) vertices denoted Kₘ,ₙ is a simple graph whose vertex set can be partitioned into two mutually disjoint non empty subsets A and B containing m and n vertices respectively, such that each vertex in set A is connected (adjacent) to every vertex in set B, but the vertices within a set are not connected.

Examples include K₂,₃ and K₃,₃.

⭐ Key Takeaways

The Handshaking Theorem is the most critical concept: the sum of all vertex degrees must always equal twice the number of edges, making the total degree an even number. Understanding the distinction between a simple graph (no loops or parallel edges) and graphs that allow such features is essential. The degree of a loop is counted twice, which is a common exam point. For complete graphs Kₙ, every vertex has degree (n-1) and there are n(n-1)/2 edges. The labeling procedure (a/b labeling) is a practical method to test if a graph is bipartite — a conflict indicates non-bipartiteness.

🧠 Quick Revision Questions

1. What is a loop in a graph, and how is its degree counted?
2. State the Handshaking Theorem and explain why the total degree of any graph must be even.
3. How many edges does a complete graph K₇ have?
4. What is the labeling procedure to determine if a graph is bipartite?
5. Explain why no simple graph can exist with four vertices of degrees 1, 2, 3, and 4.

📘 Lecture 40 — Paths and Circuits

📖 Overview: This lecture introduces fundamental concepts of graph theory by examining walks, paths, circuits, and their properties. It begins with the classic Königsberg bridges problem and progresses to Euler and Hamiltonian circuits, which are essential for understanding network connectivity and traversal problems in computer science and mathematics.

🗂️ Topics Covered

This lecture covers the definitions and distinctions between walks, closed walks, circuits, simple circuits, paths, and simple paths. It introduces the concept of graph connectedness and presents Euler circuits and Euler's theorem relating vertex degrees to circuit existence. The lecture concludes with Hamiltonian circuits and a proposition for identifying them based on subgraph properties.

📝 Lecture Summary

PATHS AND CIRCUITS — KONIGSBERG BRIDGES PROBLEM

The lecture begins with the famous Königsberg bridges problem: Is it possible for a person to take a walk around town, starting and ending at the same location and crossing each of the seven bridges exactly once? This is equivalent to asking whether one can trace the graph (starting and ending at the same point) without lifting the pencil from the paper, where vertices A, B, C, D represent land masses and edges represent bridges.

DEFINITIONS:

Let G be a graph and let v and w be vertices in graph G.

1. WALK A walk from v to w is a finite alternating sequence of adjacent vertices and edges of G. A walk has the form v₀ e₁ v₁ e₂ ... vₙ₋₁ eₙ vₙ where v₀=v, vₙ=w, and for all i=1,2...n, vᵢ₋₁ and vᵢ are endpoints of eᵢ. The trivial walk from v to v consists of the single vertex v.

2. CLOSED WALK A closed walk is a walk that starts and ends at the same vertex.

3. CIRCUIT A circuit is a closed walk that does not contain a repeated edge. Thus a circuit is a walk of the form v₀ e₁ v₁ e₂ ... vₙ₋₁ eₙ vₙ where v₀ = vₙ and all the eᵢ's are distinct.

4. SIMPLE CIRCUIT A simple circuit is a circuit that does not have any other repeated vertex except the first and last. Thus a simple circuit is a walk of the form v₀ e₁ v₁ e₂ ... vₙ₋₁ eₙ vₙ where all the eᵢ's are distinct and all the vⱼ's are distinct except that v₀ = vₙ.

5. PATH A path from v to w is a walk from v to w that does not contain a repeated edge. Thus a path is a walk of the form v = v₀ e₁ v₁ e₂ ... vₙ₋₁ eₙ vₙ = w where all the eᵢ's are distinct.

6. SIMPLE PATH A simple path from v to w is a path that does not contain a repeated vertex. Thus a simple path is a walk of the form v = v₀ e₁ v₁ e₂ ... vₙ₋₁ eₙ vₙ = w where all the eᵢ's are distinct and all the vⱼ's are also distinct.

🔑 Definition — Summary Table:

EXERCISE — Determining Walk Types

In the given graph (with vertices v₀ through v₅ and edges e₁ through e₁₀), determine whether the following walks are paths, simple paths, closed walks, circuits, simple circuits, or just walks.

(a) v₁ e₂ v₂ e₃ v₃ e₄ v₄ e₅ v₂ e₂ v₁ e₁ v₀ This starts at vertex v₁, goes to v₂ along edge e₂, moves continuously, and ends going from v₁ to v₀ along e₁. Vertex v₂ and edge e₂ are repeated twice, and the walk starts and ends at different points. Hence this is just a walk.

(b) v₁ v₂ v₃ v₄ v₅ v₂ Vertex v₂ is repeated twice. No edge is repeated, so this is a path.

(c) v₄ v₂ v₃ v₄ v₅ v₂ v₄ Vertices v₂ and v₄ are repeated, and the graph starts and ends at the same point v₄. The edge e₅ connecting v₂ and v₄ is repeated, so this is a closed walk.

(d) v₂ v₁ v₅ v₂ v₃ v₄ v₂ Vertex v₂ is repeated, and the graph starts and ends at the same vertex v₂. No edge is repeated, hence this is a circuit.

(e) v₀ v₅ v₂ v₃ v₄ v₂ v₁ Vertex v₂ is repeated and no edge is repeated, so this is a path.

(f) v₅ v₄ v₂ v₁ Neither any vertex nor any edge is repeated, so this is a simple path.

CONNECTEDNESS

Let G be a graph. Two vertices v and w of G are connected if, and only if, there is a walk from v to w. The graph G is connected if, and only if, given any two vertices v and w in G, there is a walk from v to w. Symbolically: G is connected ⇔ ∀ vertices v, w ∈ V(G), ∃ a walk from v to w.

EULER CIRCUITS

🔑 Definition — Euler circuit: An Euler circuit for G is a circuit that contains every vertex and every edge of G. That is, an Euler circuit for G is a sequence of adjacent vertices and edges in G that starts and ends at the same vertex, uses every vertex of G at least once, and uses every edge of G exactly once.

📐 Theorem: A graph G has an Euler circuit if, and only if, G is connected and every vertex of G has an even degree.

KONIGSBERG BRIDGES PROBLEM — Euler Solution

For the Königsberg bridges graph: deg(A)=3, deg(B)=3, deg(C)=3, and deg(D)=5. Since all vertices have odd degree, there is no possibility of an Euler circuit.

📌 Example: Determine whether the following graph has an Euler circuit: Graph with vertices v₀-v₉: deg(v₁)=5 (odd degree), so this graph does not have an Euler circuit.

📌 Example: Determine whether the following graph (with vertices a through i) has an Euler circuit: deg(a)=2, deg(b)=4, deg(c)=4, deg(d)=4, deg(e)=2, deg(f)=4, deg(g)=4, deg(h)=4, deg(i)=4 Since every vertex has even degree and the graph is connected, it has an Euler circuit. One such circuit is: a b c d e f g d f i h c g h b i a

EULER PATH

🔑 Definition — Euler path: Let G be a graph and let v and w be two vertices of G. An Euler path from v to w is a sequence of adjacent edges and vertices that starts at v, ends at w, passes through every vertex of G at least once, and traverses every edge of G exactly once.

📐 Corollary: Let G be a graph and let v and w be two vertices of G. There is an Euler path from v to w if, and only if, G is connected, v and w have odd degree, and all other vertices of G have even degree.

HAMILTONIAN CIRCUITS

🔑 Definition — Hamiltonian circuit: Given a graph G, a Hamiltonian circuit for G is a simple circuit that includes every vertex of G. That is, a Hamiltonian circuit for G is a sequence of adjacent vertices and distinct edges in which every vertex of G appears exactly once.

📌 Example: Find Hamiltonian Circuit for a graph with vertices a-g: The Hamiltonian Circuit is: a b d e f c g h a Another Hamiltonian Circuit for the same graph: a b c d e f g h a

📐 Proposition: If a graph G has a Hamiltonian circuit then G has a subgraph H with the following properties:

1. H contains every vertex of G
2. H is connected
3. H has the same number of edges as vertices
4. Every vertex of H has degree 2

📌 Example: Show that the following graph does not have a Hamiltonian circuit: Graph with vertices a-g: deg(c)=5. If we remove 3 edges from vertex c then deg(b)<2, deg(g)<2 or deg(f)<2, deg(d)<2. This means the graph does not satisfy the desired properties, so the graph does not have a Hamiltonian circuit.

💡 Why this matters: Euler circuits focus on traversing every edge exactly once, while Hamiltonian circuits focus on visiting every vertex exactly once. These are different problems with different solution criteria, and both have important applications in route planning, network design, and the famous Traveling Salesman Problem.

⭐ Key Takeaways

A walk allows repeated edges and vertices; a circuit is a closed walk with distinct edges; a simple circuit has only the first/last vertex repeated; a path forbids repeated edges; a simple path forbids both repeated edges and vertices. For Euler circuits, a graph must be connected and all vertices must have even degree. For Euler paths between two vertices, those two vertices must have odd degree and all others even. Hamiltonian circuits require visiting every vertex exactly once, and a necessary condition is the existence of a connected subgraph where every vertex has degree 2 with the same number of edges as vertices.

🧠 Quick Revision Questions

1. What are the six types of walks defined in this lecture, and what distinguishes a simple path from a path?
2. State Euler's theorem for the existence of an Euler circuit in a graph.
3. What condition must be satisfied for a graph to have an Euler path between two specific vertices?
4. What is the difference between an Euler circuit and a Hamiltonian circuit?
5. List the four properties of the subgraph H that must exist if a graph G has a Hamiltonian circuit.

📘 Lecture 41 — Matrix Representation of Graphs

📖 Overview: This lecture introduces matrix representations of graphs, focusing on adjacency and incidence matrices as algebraic tools for analyzing graph structures. It covers fundamental matrix concepts, operations like multiplication and transposition, and demonstrates how matrices can encode graph properties and count walks of various lengths.

🗂️ Topics Covered

This lecture begins with fundamental matrix concepts including definitions, square matrices, transpose, symmetric matrices, and matrix multiplication with worked examples. It then defines the adjacency matrix of undirected graphs, directed graphs (digraphs), and proves a theorem relating powers of the adjacency matrix to the number of walks of a given length. Finally, it introduces the incidence matrix of a simple graph.

📝 Lecture Summary

MATRIX

An m × n matrix A over a set S is a rectangular array of elements of S arranged into m rows and n columns. Briefly written as: A = [aᵢⱼ]ₘₓₙ

🔑 Definition — Matrix: A rectangular array of elements arranged in rows and columns. The size is given as m × n (rows × columns).

📐 Notation: aᵢⱼ refers to the element at the i-th row and j-th column.

📌 Example:

A = [4  -2   0   6]
    [2  -3   1   9]
    [0   7   5  -1]

This is a 3 × 4 matrix. a₁₁ = 4, a₁₂ = -2, a₂₃ = 1, etc.

SQUARE MATRIX

A matrix for which the number of rows and columns are equal is called a square matrix. A square matrix of order n × n has a main diagonal consisting of all entries a₁₁, a₂₂, a₃₃, ..., aᵢᵢ, ..., aₙₙ.

🔑 Definition — Square matrix: A matrix where m = n (same number of rows and columns). The entries a₁₁, a₂₂, ..., aₙₙ form the main diagonal.

TRANSPOSE OF A MATRIX

The transpose of a matrix A of size m × n, denoted by Aᵗ, is of size n × m, obtained by writing the rows of A, in order, as columns.

🔑 Definition — Transpose of a matrix: To find Aᵗ, write the rows of A as columns.

📌 Example: If A = [4 -2 0 6; 2 -3 1 9; 0 7 5 -1] (3×4 matrix), then Aᵗ = [4 2 0; -2 -3 7; 0 1 5; 6 9 -1] (4×3 matrix)

SYMMETRIC MATRIX

A square matrix A = [aᵢⱼ] of size n × n is called symmetric if, and only if, Aᵗ = A, i.e., for all i, j = 1, 2, ..., n, aᵢⱼ = aⱼᵢ.

🔑 Definition — Symmetric matrix: A square matrix equal to its own transpose.

📌 Example:

B = [4   2   0]
    [2  -3   1]
    [0   1   5]

Since Bᵗ = B, B is symmetric. Note that A = [1 3; 5 2] is not symmetric because Aᵗ = [1 5; 3 2] ≠ A.

MATRIX MULTIPLICATION

Suppose A is an m × p matrix and B is a p × n matrix. Then the product AB is the m × n matrix whose ij-th entry is obtained by multiplying the elements of the i-th row of A by the corresponding elements of the j-th column of B and then adding: cᵢⱼ = aᵢ₁b₁ⱼ + aᵢ₂b₂ⱼ + ... + aᵢₚbₚⱼ = Σₖ₌₁ᵖ aᵢₖbₖⱼ

🔑 Definition — Matrix multiplication: For AB to be defined, the number of columns of A must equal the number of rows of B.

📌 Example: Find AB where A = [1 3; 2 -1] and B = [2 0 -4; 3 -2 6]. AB = [(1)(2)+(3)(3) (1)(0)+(3)(-2) (1)(-4)+(3)(6); (2)(2)+(-1)(3) (2)(0)+(-1)(-2) (2)(-4)+(-1)(6)] AB = [11 -6 14; 1 2 -14] (2×3 matrix). BA is not defined because B has 3 columns and A has 2 rows (3 ≠ 2).

ADJACENCY MATRIX OF A GRAPH

Let G be a graph with ordered vertices v₁, v₂, ..., vₙ. The adjacency matrix of G is the matrix A = [aᵢⱼ] over the set of non-negative integers such that aᵢⱼ = the number of edges connecting vᵢ and vⱼ for all i, j = 1, 2, ..., n.

Alternatively: aᵢⱼ = 1 if {vᵢ, vⱼ} is an edge of G, and 0 otherwise.

🔑 Definition — Adjacency matrix: A symmetric matrix where entry (i,j) counts the edges between vertices vᵢ and vⱼ.

📌 Example: A graph with vertices v₁, v₂, v₃, v₄ where edges include a loop at v₂ and parallel edges (multiple edges between two vertices):

A = [0  0  1  1]
    [0  2  0  0]
    [1  0  0  0]
    [1  0  0  0]

Nonzero entries along the main diagonal (a₂₂ = 2) indicate loops. Entries larger than 1 correspond to parallel edges. A is symmetric.

📌 Example: Find a graph with adjacency matrix:

A = [0  2  0]
    [2  1  0]
    [0  0  1]

The graph has 3 vertices: v₁, v₂, v₃. There are two parallel edges between v₁ and v₂ (a₁₂ = a₂₁ = 2), a loop at v₂ (a₂₂ = 1), and a loop at v₃ (a₃₃ = 1).

ADJACENCY MATRIX OF A DIRECTED GRAPH

A directed graph (digraph) consists of a set V(G) of vertices and a set D(G) of directed edges, where each edge is associated with an ordered pair (v, w) called its end points, represented by an arrow from v to w.

The adjacency matrix of a digraph with ordered vertices v₁, v₂, ..., vₙ is the matrix A = [aᵢⱼ] such that aᵢⱼ = the number of arrows from vᵢ to vⱼ.

🔑 Definition — Adjacency matrix of a digraph: Entry (i,j) counts the number of directed edges from vᵢ to vⱼ.

📌 Example: A digraph with vertices v₁, v₂, v₃, v₄:

A = [1  0  1  0]
    [0  0  1  0]
    [1  0  0  1]
    [0  1  0  0]

This shows loops at v₁ and v₃, an arrow from v₁ to v₃, from v₂ to v₃, from v₃ to v₁ and v₄, and from v₄ to v₂.

💡 Why this matters: Unlike undirected graphs, the adjacency matrix of a digraph is not necessarily symmetric.

THEOREM: Walks and Powers of the Adjacency Matrix

If G is a graph with vertices v₁, v₂, ..., vₘ and A is the adjacency matrix of G, then for each positive integer n, the ij-th entry of Aⁿ = the number of walks of length n from vᵢ to vⱼ.

🔑 Definition — Walk: A sequence of vertices and edges where each edge is incident with the vertices before and after it. Length equals the number of edges.

📐 Theorem: (Aⁿ)ᵢⱼ = number of walks of length n from vᵢ to vⱼ.

📌 Problem: Let A = [1 1 2; 1 0 1; 2 1 0] be the adjacency matrix of a graph G with vertices v₁, v₂, v₃. (a) Find the number of walks of length 2 from v₂ to v₃. A² = A × A = [1 1 2; 1 0 1; 2 1 0] × [1 1 2; 1 0 1; 2 1 0] = [6 3 3; 3 2 2; 3 2 5] Entry (2,3) = 2. So there are 2 walks of length 2 from v₂ to v₃.

(b) Find the number of walks of length 3 from v₁ to v₃. A³ = A × A² = [1 1 2; 1 0 1; 2 1 0] × [6 3 3; 3 2 2; 3 2 5] = [15 9 15; 9 5 8; 15 8 8] Entry (1,3) = 15. So there are 15 walks of length 3 from v₁ to v₃.

By visual inspection of the graph (edges: v₁-v₁ loop, v₁-v₂, v₁-v₃ twice, v₂-v₃, v₂-v₃ twice? — based on A): The two walks of length 2 from v₂ to v₃ are: (i) v₂ e₂ v₁ e₃ v₃, (ii) v₂ e₂ v₁ e₄ v₃.

INCIDENCE MATRIX OF A SIMPLE GRAPH

Let G be a graph with vertices v₁, v₂, ..., vₙ and edges e₁, e₂, ..., eₘ. The incidence matrix of G is the matrix M = [mᵢⱼ] of size n × m defined by: mᵢⱼ = 1 if the vertex vᵢ is incident on the edge eⱼ, and 0 otherwise.

🔑 Definition — Incidence matrix: Rows represent vertices, columns represent edges. Entry is 1 if the vertex is an endpoint of the edge.

📌 Example: A graph with vertices v₁, v₂, v₃ and edges e₁, e₂, e₃, e₄, e₅:

M = [1  0  1  0  0]
    [0  0  0  1  1]
    [0  0  1  1  1]
    [1  1  0  0  0]

• Multiple edges are represented by columns with identical entries (e₄ and e₅).
• Loops are represented using a column with exactly one entry equal to 1 (e₂ is a loop at v₄).

⭐ Key Takeaways

The adjacency matrix is a powerful algebraic representation of graphs, encoding edge connections in a format suitable for computation. For undirected graphs, the adjacency matrix is always symmetric, with diagonal entries indicating loops. The critical theorem states that the (i,j) entry of Aⁿ gives the exact number of walks of length n from vertex vᵢ to vertex vⱼ, enabling walk counting through matrix multiplication. Directed graphs require asymmetric adjacency matrices where entries count arrows from row vertex to column vertex. The incidence matrix provides an alternative representation where columns correspond to edges and rows to vertices.

🧠 Quick Revision Questions

1. What condition must be satisfied for matrix multiplication AB to be defined?
2. If A is the adjacency matrix of an undirected graph, what property must A satisfy?
3. What does the entry (i,j) of Aⁿ represent, where A is the adjacency matrix of a graph?
4. In the incidence matrix of a simple graph, how are loops and multiple edges represented?
5. For a directed graph, how does the adjacency matrix differ from that of an undirected graph?

📘 Lecture 42 — Isomorphism of graphs

📖 Overview: This lecture introduces the concept of graph isomorphism, which determines when two graphs that look different are actually structurally identical. It covers the formal definition, isomorphic invariants, degree sequences, and provides multiple exercises to practice determining whether pairs of graphs are isomorphic or not.

🗂️ Topics Covered

The lecture begins by comparing two graphs with different vertex and edge labelings, then formally defines isomorphic graphs as having one-to-one correspondences between vertices and edges that preserve edge-endpoint relationships. It discusses isomorphism as an equivalence relation (reflexive, symmetric, transitive) and introduces isomorphic invariants — properties that must be preserved for graphs to be isomorphic. The concept of degree sequence is explained, followed by the specific case of isomorphism for simple graphs. The remainder of the lecture consists of several exercises determining if given graph pairs are isomorphic, with detailed reasoning.

📝 Lecture Summary

ISOMORPHISM OF GRAPHS

Two graphs that are the same except for the labeling of their vertices are not considered different. If there is a one-to-one correspondence between the vertices of G and G’, and also a one-to-one correspondence between the edges of G and G’, then the graphs may be isomorphic.

🔑 Definition — Isomorphic Graphs: Let G and G’ be graphs with vertex sets V(G) and V(G’) and edge sets E(G) and E(G’), respectively. G is isomorphic to G’ if, and only if, there exist one-to-one correspondences g: V(G)→V(G’) and h: E(G)→E(G’) that preserve the edge-endpoint functions of G and G’ in the sense that for all v ∈ V(G) and e ∈ E(G): v is an endpoint of e ⇔ g(v) is an endpoint of h(e).

💡 Why this matters: This definition ensures the two graphs have identical structure; only the names of vertices and edges differ.

EQUIVALENCE RELATION

Graph isomorphism is an equivalence relation on the set of graphs.

1. Reflexive: A graph is isomorphic to itself.
2. Symmetric: If G is isomorphic to G’, then G’ is isomorphic to G.
3. Transitive: If G is isomorphic to G’ and G’ is isomorphic to G’’, then G is isomorphic to G’’.

ISOMORPHIC INVARIANT

A property P is called an isomorphic invariant if, and only if, given any graphs G and G’, if G has property P and G’ is isomorphic to G, then G’ has property P.

THEOREM OF ISOMORPHIC INVARIANT

Each of the following properties is an invariant for graph isomorphism, where n, m and k are all non-negative integers, if the graph:

1. has n vertices.
2. has m edges.
3. has a vertex of degree k.
4. has m vertices of degree k.
5. has a circuit of length k.
6. has a simple circuit of length k.
7. has m simple circuits of length k.
8. is connected.
9. has an Euler circuit.
10. has a Hamiltonian circuit.

DEGREE SEQUENCE

The degree sequence of a graph is the list of the degrees of its vertices in non-increasing order.

📌 Example: Find the degree sequence of the graph with vertices a, b, c, d, e where: Degree of a = 2, Degree of b = 3, Degree of c = 1, Degree of d = 2, Degree of e = 0. Solution: By definition, degrees must be in decreasing (non-increasing) order. Therefore, the degree sequence is: 3, 2, 2, 1, 0.

GRAPH ISOMORPHISM FOR SIMPLE GRAPHS

If G and G’ are simple graphs (graphs which have no loops or parallel edges), then G is isomorphic to G’ if, and only if, there exists a one-to-one correspondence g from V(G) to V(G’) that preserves the edge-endpoint functions. For all vertices u and v of G: {u, v} is an edge in G ⇔ {g(u), g(v)} is an edge in G’. Equivalently, u and v are adjacent in G ⇔ g(u) and g(v) are adjacent in G’.

Note: There is no efficient method for checking whether two graphs are isomorphic. Despite that, there is a simple condition: two graphs are isomorphic if they have the same number of vertices and the same number of edges, and vertices should have the same degree.

EXERCISE 1

Determine whether graph G and G’ are isomorphic. G has vertices a,b,c,d,e and edges; G’ has vertices n,m,o,p,q and edges.

Solution: Both graphs have the same number of vertices. But graph G has 7 edges and graph G’ has only 6 edges. Therefore, the two graphs are not isomorphic.

EXERCISE 2

Determine whether graph G and G’ are isomorphic.

Solution: Both graphs have 5 vertices and 7 edges. The vertex q of G’ has degree 5. However, G does not have any vertex of degree 5. Hence, the two graphs are not isomorphic.

EXERCISE 3

Determine whether graph G and G’ are isomorphic. G has vertices a,b,c,d,e,f; G’ has vertices u,v,w,x,y,z.

Solution: Both graphs have the same number of vertices and edges, and all vertices have degree 2. However, G’ is a connected graph but G is not connected (it has two components: eca and bdf). Therefore, the two graphs are non-isomorphic.

EXERCISE 4

Determine whether graph G and G’ are isomorphic.

Solution: Both graphs have 6 vertices. G has two simple circuits of length 3: abca and defd. G’ does not have any simple circuit of length 3 (it has a simple circuit uxwv of length 4). Therefore, the two graphs are non-isomorphic.

Note: A simple circuit is a circuit that does not have any other repeated vertex except the first and last.

EXERCISE 5

Determine whether graph G and G’ are isomorphic. Both have vertices a,b,c,d and e,f,g,h respectively.

Solution: Both graphs have 8 vertices and 12 edges, and are regular graphs (each vertex has degree 3). G has two simple circuits of length 5: abcfea and cdhgfc. G’ does not have any simple circuit of length 5 (it has simple circuits tyxut, vwxuv of length 4). Therefore, the two graphs are non-isomorphic.

EXERCISE 6 (Proving Isomorphism)

Determine whether graph G and G’ are isomorphic. G has vertices a,b,c,d,e,f; G’ has vertices u,v,w,x,y,z.

Solution: All isomorphism invariants seem true. G has four vertices of degree 2 and two vertices of degree 3, same for G’. Both have circuits of length 4. A one-to-one correspondence is defined:

• a↦u, b↦v, c↦w, d↦x, e↦y, f↦z

The edge-preserving property is verified:

• {a,b}→{u,v}, {b,c}→{v,y}, {c,d}→{y,x}, {d,e}→{x,w}, {e,f}→{w,z}, {a,f}→{u,z}, {c,f}→{y,z}

Thus, the graphs are isomorphic.

Alternative Solution: A different mapping can also be defined: a↦u, b↦v, c↦w, d↦x, e↦y, f↦z with the same verification.

EXERCISE 7 (Proving Isomorphism)

Determine whether graph G and G’ are isomorphic. G has vertices a,b,c,d,e,f,g,h; G’ has vertices s,t,u,v,w,x,y,z.

Solution: All isomorphism invariants seem true. Define function f: V(G)→V(G’) as:

• a↦s, b↦t, c↦u, d↦v, e↦w, f↦z, g↦y, h↦x

The edge-preserving property is verified:

• {a,b}→{s,t}, {b,c}→{t,u}, {c,d}→{u,v}, {a,d}→{s,v}, {a,f}→{s,z}, {b,g}→{t,y}, {c,h}→{u,x}, {d,e}→{v,w}, {e,f}→{w,z}, {f,g}→{z,y}, {g,h}→{y,x}, {h,e}→{x,w}

Therefore, the graphs are isomorphic.

EXERCISE 8

Find all non-isomorphic simple graphs with three vertices.

Solution: There are four non-isomorphic simple graphs with three vertices.

EXERCISE 9

Find all non-isomorphic simple connected graphs with three vertices.

Solution: There are two non-isomorphic connected simple graphs with three vertices.

EXERCISE 10

Find all non-isomorphic simple connected graphs with four vertices.

Solution: There are six simple connected graphs with four vertices.

⭐ Key Takeaways

The most critical concepts from this lecture are: (1) Two graphs are isomorphic if there exist one-to-one correspondences between their vertices and edges that preserve edge-endpoint relationships, meaning they have identical structure. (2) Isomorphic invariants like number of vertices, number of edges, degree sequence, connectivity, and existence of circuits of specific lengths must all match for graphs to be isomorphic. (3) If any invariant differs, the graphs cannot be isomorphic — this provides a quick way to disprove isomorphism. (4) For simple graphs, isomorphism reduces to a bijection between vertex sets that preserves adjacency. (5) Proving graphs are isomorphic requires explicitly defining a mapping and verifying it preserves all edge-endpoint relationships.

🧠 Quick Revision Questions

1. What is the formal definition of graph isomorphism?
2. List at least five isomorphic invariants that must be preserved for two graphs to be isomorphic.
3. How do you compute the degree sequence of a graph, and why is it useful for checking isomorphism?
4. What distinguishes the isomorphism condition for simple graphs versus general graphs?
5. If two graphs have the same number of vertices, same number of edges, and same degree sequence, are they necessarily isomorphic? Explain with a counterexample from the lecture.

📘 Lecture 43 — Planar Graphs

📖 Overview: This lecture introduces planar graphs—graphs that can be drawn on a flat surface without crossing edges—and explores their fundamental properties. It also covers graph coloring, the chromatic number, and the famous Four Color Theorem, demonstrating practical applications such as map coloring and chemical storage problems.

🗂️ Topics Covered

Planar graphs definition and examples including K₄ and Q₃; Euler's Formula relating faces, edges, and vertices; proofs that K₃,₃ and K₅ are non-planar; graph coloring definitions; the Four Color Theorem; application of graph coloring to chemical storage problems.

📝 Lecture Summary

PLANAR GRAPHS

A planar graph is a graph that can be drawn in the plane without any edge crossed (crossing means the intersection of lines). Such a drawing is called a plane drawing of the graph. A graph is planar if its crossing number is "0".

📌 Example: K₄ — The complete graph on 4 vertices can be drawn with crossed edges, but it can also be redrawn with no crossed edges, so K₄ is planar.

💡 Why this matters: Planarity determines which graphs can be represented without overlapping edges, which is essential for circuit design, map drawing, and network visualization.

Note: Complete graphs are planar only for n ≤ 4.

📌 Example: The 3-cube (Q₃) has 8 vertices and 12 edges. Although the common representation includes many edge crossings, a plane drawing with no crossing is possible.

📌 Exercise: A bipartite graph K₃ (with circuit afcebda) can be redrawn so that no edges cross, proving it is planar.

THEOREM: Show that K₃,₃ is not planar

Proof: K₃,₃ is a complete bipartite graph with vertices partitioned into two sets of three vertices each. When redrawing, after placing edges a-z, c-x, and b-y, the edge ay can be drawn without crossing. However, edge bz cannot be drawn without crossings. Similarly, if ay is drawn inside and bz drawn outside, the same problem occurs. Therefore, K₃,₃ is non-planar.

THEOREM: Show that K₅ is non-planar

Proof: K₅ is a complete graph on 5 vertices where every vertex connects to every other vertex. When redrawing K₅, edges wy and zx still contain lines that cross each other. Therefore, K₅ is non-planar.

FACES AND REGIONS

A plane drawing of a planar graph divides the plane into regions, including an unbounded region, called faces. The unbounded region is called the infinite face.

📌 Example: In a graph with 6 faces, 7 vertices, and 10 edges, f₆ is the unbounded region or infinite face because f₆ is outside of the graph.

📌 Example: In a graph with 8 faces, 9 vertices, and 14 edges, f₅ is the infinite face.

EULER'S FORMULA

🔑 Definition — Euler's Formula: Let G be a connected planar simple graph with e edges and v vertices. Let f be the number of faces in a plane drawing of G. Then:

📐 Formula: f = e – v + 2

📌 Example: Suppose a connected planar simple graph has 30 edges and 20 faces. Using Euler's Formula: 20 = 30 – v + 2 v = 30 – 20 + 2 = 12 Therefore, the graph has 12 vertices.

GRAPH COLORING

Graph coloring addresses problems like map coloring where adjacent regions cannot have the same color. The goal is to determine the least number of colors needed.

📌 Example 1: In one map, 4 colors are necessary but 3 colors are not enough. 📌 Example 2: In another map, 3 colors are necessary but 2 colors are not enough.

HOW TO DRAW A GRAPH FROM A MAP

1. Each map in the plane can be represented by a graph.
2. Each region is represented by a vertex.
3. If regions share a common border, an edge connects the two vertices.
4. Two regions that touch at only one point are not adjacent.

DEFINITIONS

🔑 Definition — Coloring of a simple graph: The assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color.

🔑 Definition — Chromatic number of a graph: The least (minimum) number of colors needed for a coloring of the graph.

📌 Example: For graph G, vertices a, b, and c are adjacent to each other so they receive different colors (red, blue, green). Vertex d is colored red (adjacent to blue and green), e is green (adjacent to blue and red), f is blue (adjacent to red and green), and g is red (adjacent to green and blue). The chromatic number of G is 3.

📌 Example: For graph H, using the same process, the chromatic number is 4.

THE FOUR COLOR THEOREM

🔑 Definition — Four Color Theorem: The chromatic number of a simple planar graph is no greater than four.

APPLICATION OF GRAPH COLORING

📌 Example: A chemist needs to store five chemicals a, b, c, d, and e. Some chemicals react violently and must be kept in separate areas. The table shows asterisks (*) for pairs that must be separated.

We draw a graph where vertices correspond to the five chemicals, with two vertices adjacent whenever the corresponding chemicals must be kept apart. The chromatic number of this graph is 4, so four areas are needed for storage.

⭐ Key Takeaways

Euler's Formula (f = e – v + 2) is essential for connecting the number of faces, edges, and vertices in connected planar graphs. K₃,₃ and K₅ are the two fundamental non-planar graphs that every student must recognize. The chromatic number of a planar graph never exceeds 4 according to the Four Color Theorem, and graph coloring assigns colors to vertices such that adjacent vertices never share the same color. The practical application of graph coloring extends from map coloring to real-world problems like chemical storage separation.

🧠 Quick Revision Questions

1. What is Euler's Formula for a connected planar simple graph, and how many vertices does a graph have if it has 30 edges and 20 faces?
2. Why are K₃,₃ and K₅ considered non-planar graphs?
3. What is the chromatic number of a graph, and what does the Four Color Theorem state about planar graphs?
4. How do you draw a graph from a map, and why do regions touching at only one point not count as adjacent?
5. In the chemical storage application, how many areas were needed for five chemicals and why?

📘 Lecture 44 — Trees

📖 Overview: This lecture introduces trees as a fundamental data structure in graph theory and computer science. It defines trees, explores their properties, and covers special types like rooted trees and binary trees, along with their applications in problem-solving and data representation.

🗂️ Topics Covered

The lecture covers the definition and application areas of trees, special trees including trivial trees, empty trees, and forests, properties of trees with exercises on non-isomorphic trees, definitions of terminal and internal vertices, rooted trees with level and height concepts, binary trees and full binary trees with theorems, exercises on tree specifications, and representation of algebraic expressions using binary trees.

📝 Lecture Summary

TREES

APPLICATION AREAS: Trees are used to solve problems in a wide variety of disciplines. In computer science trees are employed to:

1. construct efficient algorithms for locating items in a list.
2. construct networks with the least expensive set of telephone lines linking distributed computers.
3. construct efficient codes for storing and transmitting data.
4. model procedures that are carried out using a sequence of decisions, which are valuable in the study of sorting algorithms.

🔑 Definition — Tree: A tree is a connected graph that does not contain any non-trivial circuit (i.e., it is circuit-free). A trivial circuit is one that consists of a single vertex.

📌 Example: Examples of trees are provided in the lecture text. Examples of non-trees include graphs with a circuit, disconnected graphs, and graphs with a circuit (including loops).

SOME SPECIAL TREES

1. TRIVIAL TREE: A graph that consists of a single vertex is called a trivial tree or degenerate tree.

2. EMPTY TREE: A tree that does not have any vertices or edges is called an empty tree.

3. FOREST: A graph is called a forest if, and only if, it is circuit-free. OR "Any non-connected graph that contains no circuit is called a forest." Hence, it clears that the connected components of a forest are trees.

📌 Example: As in both the graphs above, there exists no circuit, so called forest.

PROPERTIES OF TREES

1. A tree with n vertices has n - 1 edges (where n ≥ 0).
2. Any connected graph with n vertices and n - 1 edges is a tree.
3. A tree has no non-trivial circuit; but if one new edge (but no new vertex) is added to it, then the resulting graph has exactly one non-trivial circuit.
4. A tree is connected, but if any edge is deleted from it, then the resulting graph is not connected.
5. Any tree that has more than one vertex has at least two vertices of degree 1.
6. A graph is a tree iff there is a unique path between any two of its vertices.

📐 Formula: For a tree with n vertices, number of edges = n - 1.

📌 Example (EXERCISE): Explain why graphs with the given specification do not exist.

1. Tree, twelve vertices, fifteen edges. → Any tree with 12 vertices will have 12 - 1 = 11 edges, not 15.
2. Tree, five vertices, total degree 10. → Any tree with 5 vertices will have 5 - 1 = 4 edges. Since total degree = 2(edges) = 2(4) = 8, a tree with 5 vertices would have total degree 8, not 10.

📌 Example (EXERCISE): Find all non-isomorphic trees with four vertices. → Any tree with four vertices has 3 edges, total degree = 6. Possible degree combinations: 1, 1, 1, 3 and 1, 1, 2, 2. The corresponding trees are non-isomorphic.

📌 Example (EXERCISE): Find all non-isomorphic trees with five vertices. → There are three non-isomorphic trees with five vertices (4 edges). In part (a), tree has 2 vertices of degree ‘1’ and 3 vertices of degree ‘2’. In part (b), 3 vertices have degree ‘1’, 1 has degree ‘2’ and 1 vertex has degree ‘3’. In part (c), possible combinations of degree are 1, 1, 1, 1, 4.

📌 Example (EXERCISE): Draw a graph with six vertices, five edges that is not a tree. → Two such graphs are shown. First graph is not a tree because it is not connected and also there exists a circuit. Similarly, second graph is not a tree.

DEFINITION

🔑 Definition — Terminal vertex or leaf: A vertex of degree 1 in a tree. 🔑 Definition — Internal vertex or branch vertex: A vertex of degree greater than 1 in a tree.

📌 Example: The terminal vertices of the tree are v₁, v₂, v₅, v₆ and v₈ and internal vertices are v₃, v₄, v₇.

ROOTED TREE

🔑 Definition — Rooted tree: A rooted tree is a tree in which one vertex is distinguished from the others and is called the root. 🔑 Definition — Level: The level of a vertex is the number of edges along the unique path between it and the root. 🔑 Definition — Height: The height of a rooted tree is the maximum level to any vertex of the tree. 🔑 Definition — Children: The children of any internal vertex v are all those vertices that are adjacent to v and are one level farther away from the root than v. 🔑 Definition — Parent: If w is a child of v, then v is called the parent of w. 🔑 Definition — Siblings: Two vertices that are both children of the same parent are called siblings. 🔑 Definition — Ancestor and descendant: Given vertices v and w, if v lies on the unique path between w and the root, then v is an ancestor of w and w is a descendant of v.

📌 Example: Consider the rooted tree shown with root v₀. a. What is the level of v₈? → 3 (covers 3 edges). b. What is the level of v₀? → 0 (no edge from v₀ to v₀). c. What is the height of this tree? → 5 (maximum level). d. What are the children of v₁₀? → v₁₄, v₁₅ and v₁₆. e. What are the siblings of v₁? → v₃, v₄, and v₅. f. What are the descendants of v₁₂? → v₁₇, v₁₈, and v₁₉.

BINARY TREE

🔑 Definition — Binary tree: A binary tree is a rooted tree in which every internal vertex has at most two children. Every child in a binary tree is designated either a left child or a right child (but not both). 🔑 Definition — Full binary tree: A full binary tree is a binary tree in which each internal vertex has exactly two children.

📌 Example: In the example, v is the left child of u.

THEOREMS:

1. If k is a positive integer and T is a full binary tree with k internal vertices, then T has a total of 2k + 1 vertices and has k + 1 terminal vertices.
2. If T is a binary tree that has t terminal vertices and height h, then t ≤ 2ʰ. Equivalently, log₂ t ≤ h.

💡 Why this matters: The maximum number of terminal vertices of a binary tree of height h is 2ʰ.

📐 Formula: Full binary tree: total vertices = 2k + 1, terminal vertices = k + 1. Binary tree: t ≤ 2ʰ.

📌 Example (EXERCISE): Explain why graphs with the given specification do not exist.

1. full binary tree, nine vertices, five internal vertices. → Any full binary tree with five internal vertices has six terminal vertices, for a total of eleven vertices (2(5)+1=11), not nine. OR total vertices = 2k+1 = 9 → k=4, but given internal vertices = 5, which is a contradiction.
2. binary tree, height 4, eighteen terminal vertices. → Any binary tree of height 4 has at most 2⁴ = 16 terminal vertices. Hence, no such tree exists.

📌 Example (EXERCISE): Draw a full binary tree with seven vertices. → Total vertices = 2k + 1 = 7 → k = 3 internal vertices, k+1 = 4 terminal vertices. A full binary tree with seven vertices is shown with root a and children b, c, etc.

📌 Example (EXERCISE): Draw a binary tree with height 3 and having seven terminal vertices. → Height = h = 3. Any binary tree with height 3 has at most 2³ = 8 terminal vertices. With 7 terminal vertices and k = 6 internal vertices, a binary tree exists.

REPRESENTATION OF ALGEBRAIC EXPRESSIONS BY BINARY TREES

Binary trees are specially used in computer science to represent algebraic expression with arbitrary nesting of balanced parentheses.

📌 Example: Binary tree for a/b → The operator (/) is the root and a and b are the left and right children.

📌 Example: Binary tree for a/(c+d) → The operator (/) is the root. The terminal vertices are variables (here a, c and d), and the internal vertices are arithmetic operators (+ and /).

📌 Example (EXERCISE): Draw a binary tree to represent the expression a/(b-c·d). → The internal vertices are arithmetic operators, the terminal vertices are variables, and the operator at each vertex acts on its left and right subtrees in left-right order.

⭐ Key Takeaways

Trees are fundamental connected, circuit-free graphs where a tree with n vertices always has exactly n-1 edges, and any tree with more than one vertex must have at least two vertices of degree 1 (leaves). Rooted trees introduce hierarchical structure with root, levels, and height, while binary trees restrict internal vertices to at most two children, and full binary trees require exactly two children per internal vertex. Key formulas include the full binary tree vertex count (2k+1 total, k+1 terminal) and the binary tree terminal vertex bound (t ≤ 2ʰ). These concepts are directly applied to verify tree properties, draw non-isomorphic trees, and represent algebraic expressions.

🧠 Quick Revision Questions

1. What is a tree in graph theory, and what are its two defining properties?
2. How many edges does a tree with n vertices have, and why?
3. What is the difference between a terminal vertex (leaf) and an internal vertex in a tree?
4. In a binary tree of height 3, what is the maximum number of terminal vertices, and what theorem gives this bound?
5. How would you represent the expression (a + b) / (c - d) as a binary tree?

📘 Lecture 45 — Spanning Trees

📖 Overview: This lecture introduces the concept of spanning trees in graph theory, explaining how to find them from connected graphs and their practical applications in network design. It covers Kirchhoff's Matrix-Tree Theorem for counting spanning trees and presents both Kruskal's and Prim's algorithms for finding minimal spanning trees in weighted graphs.

🗂️ Topics Covered

The lecture covers spanning trees definition and properties, methods for finding spanning trees by edge deletion from cycles, complete enumeration of all spanning trees for small graphs, Kirchhoff's Matrix-Tree Theorem for counting spanning trees, weighted graphs and minimal spanning trees, Kruskal's algorithm for building minimal spanning trees, and Prim's algorithm with comparison of minimal spanning trees.

📝 Lecture Summary

SPANNING TREES

A spanning tree is needed when developing a system of roads between six major cities, where economic reasons require constructing the least possible number of roads while still connecting all cities. The subgraph representing these roads must be connected and circuit-free.

🔑 Definition — Spanning Tree: A spanning tree for a graph G is a subgraph of G that contains every vertex of G and is a tree.

REMARKS:

1. Every connected graph has a spanning tree.
2. A graph may have more than one spanning trees.
3. Any two spanning trees for a graph have the same number of edges.
4. If a graph is a tree, then its only spanning tree is itself.

EXERCISE: Find a spanning tree for a graph with vertices a, b, c, d, e, f and 9 edges.

SOLUTION: The graph has 6 vertices and 9 edges, so we must delete 9 - 6 + 1 = 4 edges (as a tree of n vertices has n-1 edges). We delete one edge in each cycle:

1. Delete af
2. Delete fe
3. Delete be
4. Delete ed

The resulting spanning tree connects a-b, b-c, c-d, d-e, e-f, but there is no path from a to e, a to d, or a to c.

EXERCISE: Find all spanning trees of the graph with vertices v₀, v₁, v₂, v₃.

SOLUTION: The graph has n = 4 vertices and e = 5 edges. We must delete e - v + 1 = 5 - 4 + 1 = 2 edges from cycles to obtain a spanning tree.

Eight spanning trees are found by deleting different pairs of edges:

1. Delete v₀v₁ & v₁v₂
2. Delete v₀v₁ & v₁v₃
3. Delete v₀v₁ & v₂v₃
4. Delete v₀v₃ & v₁v₂
5. Delete v₀v₃ & v₁v₃
6. Delete v₀v₃ & v₂v₃
7. Delete v₁v₃ & v₁v₂
8. Delete v₁v₃ & v₂v₃

EXERCISE: Find a spanning tree for (a) k₁,₅ (b) k₄

SOLUTION (a): k₁,₅ is a complete bipartite graph on (1,5) vertices. The graph itself is a tree (six vertices and five edges), so it is its own spanning tree.

SOLUTION (b): k₄ is a complete graph on four vertices. With n = 4 vertices and e = 6 edges, we must remove e - v + 1 = 6 - 4 + 1 = 3 edges. Removing edges ab, bd, and cd yields a spanning tree.

KIRCHHOFF'S THEOREM OR MATRIX-TREE THEOREM

🔑 Definition — Kirchhoff's Theorem: Let M be the matrix obtained from the adjacency matrix of a connected graph G by changing all 1's to -1's and replacing each diagonal 0 by the degree of the corresponding vertex. Then the number of spanning trees of G is equal to the value of any cofactor of M.

EXAMPLE: Find the number of spanning trees of the graph with vertices a, b, c, d.

Adjacency matrix A(G):

a: [0, 1, 0, 1]
b: [1, 0, 1, 1]
c: [0, 1, 0, 1]
d: [1, 1, 1, 0]

Matrix M (from Kirchhoff's theorem):

M = [ 2  -1   0  -1 ]
    [-1   3  -1  -1 ]
    [ 0  -1   2  -1 ]
    [-1  -1  -1   3 ]

📐 Formula: Cofactor of element at (1,1)

|  3  -1  -1 |
| -1   2  -1 |
| -1  -1   3 |

📌 Example computation: = 3(6-1) + (-1)(-3-1) + (-1)(1+2) = 15 - 4 - 3 = 8 spanning trees

EXERCISE: How many non-isomorphic spanning trees does a given simple graph have?

SOLUTION: There are eight spanning trees numbered 1-8. Trees 1 and 6 are isomorphic, and trees 2, 3, 4, 5, 7, 8 are isomorphic. Hence there are only two non-isomorphic spanning trees.

EXERCISE: An oil company wants to build pipelines between six storage facilities to move oil between any two facilities, constructing as few pipelines as possible.

SOLUTION: Find a set of edges that forms a connected graph containing all vertices with no cycles — a tree containing all vertices. This allows oil to go from any storage facility to any other without unnecessary building costs.

WEIGHTED GRAPHS AND MINIMAL SPANNING TREES

🔑 Definition — Weighted Graph: A graph for which each edge has an associated real number weight. The sum of the weights of all edges is the total weight of the graph.

📌 Example: A weighted graph with edge weights 2, 6, 3, 2, 3, 1 has total weight = 2 + 6 + 3 + 2 + 3 + 1 = 17

🔑 Definition — Minimal Spanning Tree: A spanning tree for a weighted graph that has the least possible total weight compared to all other spanning trees of the graph.

If G is a weighted graph and e is an edge, then w(e) denotes the weight of e and w(G) denotes the total weight of G.

EXERCISE: Find three spanning trees of a weighted graph and indicate the minimal one.

T₁: w(T₁) = 14 T₂: w(T₂) = 11 ← Minimal spanning tree T₃: w(T₃) = 15

KRUSKAL'S ALGORITHM

Input: G [a weighted graph with n vertices]

Algorithm:

1. Initialize T (the minimal spanning tree of G) to have all vertices of G and no edges.
2. Let E be the set of all edges of G and let m = 0.
3. While (m < n - 1): 3a. Find an edge e in E of least weight. 3b. Delete e from E. 3c. If addition of e to T does not produce a circuit, then add e to T and set m = m + 1 end while Output: T

EXERCISE: Use Kruskal's algorithm to find a minimal spanning tree.

SOLUTION: Order of adding edges:

1. {a, b}
2. {e, f}
3. {e, d}
4. {c, d}
5. {g, f}
6. {b, c}

PRIM'S ALGORITHM

Input: G [a weighted graph with n vertices]

Algorithm Body:

1. Pick a vertex v of G and let T be the graph with one vertex, v, and no edges.
2. Let V be the set of all vertices of G except v.
3. For i = 1 to n - 1: 3a. Find an edge e of G such that: (1) e connects T to one of the vertices in V, and (2) e has the least weight of all edges connecting T to a vertex in V. 3b. Let w be the endpoint of e that is in V. 3c. Add e and w to T, delete w from V. next i Output: T

EXERCISE: Use Prim's algorithm starting with vertex a to find a minimal spanning tree.

SOLUTION: Order of adding edges:

1. {a, b}
2. {b, c}
3. {c, d}
4. {d, e}
5. {e, f}
6. {f, g}

EXERCISE: Find all minimal spanning trees using (a) Kruskal's algorithm (b) Prim's algorithm starting with vertex a.

SOLUTION (a) — Kruskal's algorithm: Edges can be added in one of two orders:

1. {c, d}, {c, e}, {c, b}, {d, a}
2. {c, d}, {d, e}, {c, b}, {d, a} Thus there are two distinct minimal spanning trees.

SOLUTION (b) — Prim's algorithm starting at a: Edges can be added in one of two orders:

1. {a, d}, {d, c}, {c, e}, {c, b}
2. {a, d}, {d, c}, {d, e}, {c, b} Thus there are two distinct minimal spanning trees.

💡 Why this matters: Both Kruskal's and Prim's algorithms can produce the same set of minimal spanning trees, but the order of edge selection differs. A weighted graph may have multiple minimal spanning trees with the same total weight.

⭐ Key Takeaways

A spanning tree of a connected graph must contain all vertices and be circuit-free, with exactly n-1 edges for n vertices. Kirchhoff's Matrix-Tree Theorem provides a powerful algebraic method to count spanning trees by computing any cofactor of a modified adjacency matrix. For weighted graphs, minimal spanning trees minimize total edge weight and can be found using Kruskal's algorithm (selecting least-weight edges without creating cycles) or Prim's algorithm (growing from a starting vertex by adding the least-weight connecting edge). Both algorithms are greedy and yield optimal minimal spanning trees, though multiple distinct minimal spanning trees may exist for the same graph.

🧠 Quick Revision Questions

1. What is the formula for the number of edges to delete from a connected graph with n vertices and e edges to obtain a spanning tree?

2. In Kirchhoff's Matrix-Tree Theorem, how do you construct matrix M from the adjacency matrix of a graph?

3. What is the key difference between Kruskal's algorithm and Prim's algorithm for finding minimal spanning trees?

4. How many non-isomorphic spanning trees does a complete graph K₄ have?

5. If addition of an edge during Kruskal's algorithm produces a circuit, what should you do with that edge?