Discrete Math Relations Induction Combinatorics

Discrete Math Concepts

Binary Relations

Cartesian Product

The Cartesian product of two sets A and B, denoted A × B, is the set of all ordered pairs (a, b) where a is in A and b is in B.

Example: If A = {0, 1}, the Cartesian product A × A is {(0,0), (0,1), (1,0), (1,1)}.

Properties of Binary Relations

A binary relation R on a set A can have several properties:

1. Reflexive: For all x ∈ A, (x, x) ∈ R.
2. Symmetric: For all x, y ∈ A, if (x, y) ∈ R, then (y, x) ∈ R.
3. Transitive: For all x, y, z ∈ A, if (x, y) ∈ R and (y, z) ∈ R, then (x, z) ∈ R.
4. Irreflexive: For all x ∈ A, (x, x) ∉ R.
5. Antisymmetric: For all x, y ∈ A, if (x, y) ∈ R and (y, x) ∈ R, then x = y.

Examples of Relation Properties

Consider a set A = {0, 1}.

• The relation R = A × A = {(0,0), (0,1), (1,0), (1,1)} is reflexive, symmetric, and transitive. This is an equivalence relation.
• The relation R = {(0,0), (1,1)} is reflexive, symmetric, and transitive. This is also an equivalence relation.
• The relation R = {(0,1)} on A = {0, 1} is irreflexive, transitive, and antisymmetric.

Relation Closures

Closure Definition

If R is a binary relation and P is a property, the P-closure of R is the smallest relation R' containing R such that R' satisfies property P. It is obtained by adding the minimum number of pairs to R.

Reflexive Closure

The reflexive closure of R, denoted r(R), is obtained by adding all pairs (x, x) for every x in the domain of R that are not already in R.

Example: Let R = {(a,a), (a,b), (b,a), (b,c)} on the set {a, b, c}. The reflexive closure r(R) = R ∪ {(b,b), (c,c)} = {(a,a), (a,b), (b,a), (b,c), (b,b), (c,c)}.

Symmetric Closure

The symmetric closure of R, denoted s(R), is obtained by adding all pairs (y, x) for every pair (x, y) in R that are not already in R. The set {(y,x) | (x,y) ∈ R} is called the converse of R, denoted R⁻¹.

Example: Let R = {(a,a), (a,b), (b,a), (b,c)}. The symmetric closure s(R) = R ∪ R⁻¹ = R ∪ {(c,b)} = {(a,a), (a,b), (b,a), (b,c), (c,b)}.

Transitive Closure

The transitive closure of R, denoted t(R), is the smallest transitive relation containing R. It includes all pairs (x, z) such that there is a path from x to z in R (i.e., x R y₁ R y₂ ... R z).

Example: Let R = {(a,b), (b,c), (c,d)}. The transitive closure t(R) = R ∪ {(a,c), (a,d), (b,d)}.

Warshall's Algorithm

Warshall's algorithm is an efficient algorithm to compute the transitive closure of a binary relation on a set represented by its adjacency matrix.

Mathematical Induction

Proof by induction is a powerful technique used to prove statements about an infinite sequence of objects, typically integers starting from some base value.

Principle of Mathematical Induction (PMI)

Let P(n) be a statement about an integer n. To prove that P(n) is true for all integers n greater than or equal to some integer m, we perform two steps:

1. Basis Step: Prove that P(m) is true.
2. Inductive Step: Assume that P(k) is true for an arbitrary integer k ≥ m (this is the inductive hypothesis). Then prove that P(k+1) is true.

If both steps are completed, the Principle of Mathematical Induction guarantees that P(n) is true for all integers n ≥ m.

Combinatorics

Permutations and Combinations

Combinatorics deals with counting arrangements and selections of objects.

Permutations

A permutation is an arrangement of objects in a specific order. The number of permutations of n distinct objects taken r at a time is denoted P(n, r) and calculated as:

P(n, r) = n! / (n - r)!

Example: Let S = {C, A, T, S}.

• The number of permutations of 4 objects taken 4 at a time: P(4, 4) = 4! / (4 - 4)! = 4! / 0! = 24 / 1 = 24.
• The number of permutations of 4 objects taken 1 at a time: P(4, 1) = 4! / (4 - 1)! = 4! / 3! = 24 / 6 = 4. The permutations are {C}, {A}, {T}, {S} (as single-element sequences/arrangements).

Combinations

A combination is a selection of objects where the order does not matter. The number of combinations of n distinct objects taken r at a time is denoted C(n, r) or (n choose r) and calculated as:

C(n, r) = n! / (r! * (n - r)!)

Example: Let S = {a, b, c, d, e}. The number of combinations of 5 objects taken 3 at a time:

C(5, 3) = 5! / (3! * (5 - 3)!) = 5! / (3! * 2!) = 120 / (6 * 2) = 120 / 12 = 10.

The combinations are: {a,b,c}, {a,b,d}, {a,b,e}, {a,c,d}, {a,c,e}, {a,d,e}, {b,c,d}, {b,c,e}, {b,d,e}, {c,d,e}.

Bag Permutations (Permutations with Repetition)

For a collection (bag) of objects where some are identical, the number of distinct permutations is calculated by dividing the total number of permutations (if all were distinct) by the factorial of the counts of each repeated object.

Formula: n! / (n₁! * n₂! * ... * n_k!) where n is the total number of objects and nᵢ is the count of the i-th distinct object type.

Example: Let S = {m, i, s, s, i, s, s, i, p, p, i}. Counts: m=1, i=4, s=4, p=2. Total objects n = 1 + 4 + 4 + 2 = 11.

Number of distinct permutations = 11! / (1! * 4! * 4! * 2!) = 39,916,800 / (1 * 24 * 24 * 2) = 39,916,800 / 1152 = 34,650.

Bag Combinations (Combinations with Repetition)

The number of combinations of selecting k items from a set of n types with unlimited repetition allowed for each type is given by the formula:

C(n + k - 1, k) = (n + k - 1)! / (k! * (n - 1)!)

Example: Selecting 5 people (k=5) from 3 types of items (n=3) with repetition allowed.

Number of combinations = C(3 + 5 - 1, 5) = C(7, 5) = 7! / (5! * (7 - 5)!) = 7! / (5! * 2!) = 5040 / (120 * 2) = 5040 / 240 = 21.

Binomial Theorem

The Binomial Theorem provides a formula for expanding powers of a binomial (x + y)ⁿ:

(x + y)ⁿ = Σ (from k=0 to n) C(n, k) * x^(n-k) * y^k

Example: Expand (x + 4)⁴ using the Binomial Theorem.

(x + 4)⁴ = C(4, 0)x⁴4⁰ + C(4, 1)x³4¹ + C(4, 2)x²4² + C(4, 3)x¹4³ + C(4, 4)x⁰4⁴

= 1 * x⁴ * 1 + 4 * x³ * 4 + 6 * x² * 16 + 4 * x * 64 + 1 * 1 * 256

= x⁴ + 16x³ + 96x² + 256x + 256