[Discrete Mathematics] lecture 5 - counting

Overview

---

This lecture introduces the fundamentals of counting and recurrence relations. It begins by defining finite and infinite sets, emphasizing the concept of cardinality and distinguishing between countable and uncountable sets. Key counting principles such as the Pigeonhole Principle, sum and product rules, and formulas for permutations and combinations are presented, along with proofs and exercises.

The lecture then transitions to recurrence relations, defining linear homogeneous recurrence relations with constant coefficients and outlining their solutions using characteristic polynomials. It concludes with the general solution form, including the handling of repeated roots.

Introduction to Counting

---

Definition 1 (finite)
A set $A$ is finite if $A$ is empty or there is some natural number $n$ such that there is a bijection from the set ${1, 2, \ldots, n}$ to set $A$.

The integer $n$ is called the cardinality of $A$ and is denoted by $|A|$.

Definition 2 (infinite)
A set $A$ is infinite if there exists an injection $f: A \to A$ such that $f(A)$ is a proper subset of $A$.
A set is infinite if it is not finite.

A proper subset of $A$ is a subset of $A$ that is not equal to $A$. ($A \subsetneq A$)

Definition 3 (cardinality)
A set $A$ is of cardinality $\aleph_0$, denoted by $|A| = \aleph_0$, if there is a bijection from a set $\N$ of natural numbers to $A$.

$\aleph_0$ is essentially the cardinality of the set of natural numbers.

Definition 4 (countably infinite)
A set $A$ is countably infinite if $|A| = \aleph_0$.
A set is countably infinite if it is infinite and there is a bijection from $\N$ to $A$.
A set is countable or denumerable if it is either finite or countably infinite.
A set is uncountable or uncountably infinite if it is not countable.

Definition 5 (enumeration)
An enumeration of a set $A$ is a surjective function $f: [1,n] \to A$.
If $f$ is injective(i.e. bijective), then it is a enumeration without repetitions
(i.e. $n=|A|$).
If $f$ is not injective, then it is a enumeration with repetitions
(i.e. $n>|A|$).

Basic Theorems

Theorem 1 (Pigeonhole Principle)
If $A$ and $B$ are finite sets with $|A| > |B|$, then there is no injective function from $A$ to $B$.

Exercise

Prove the following: Every integer has a multiple of itself whose decimal representation consists only of 0s and 1s.

Hint: Use the Pigeonhole Principle.

Theorem 2
Let $A$ be a finite set. Then the cardinality of $A$ is unique.

Theorem 3
Let $A$ and $B$ be finite sets. Suppose there is a bijection from $A$ to $B$. Then $|A| = |B|$

Theorem 4 (rule of sum)
If $A$ and $B$ are finite disjoint sets, then $|A \cup B| = |A| + |B|$

Theorem 5 (rule of product)
If $A$ and $B$ are finite sets, then $|A \times B| = |A| \cdot |B|$

Theorem 6 (counting function)
Let $A$ and $B$ be finite sets. Then there are $|B|^{|A|}$ functions from A to B.

Theorem 7
Let $A$ be a finite set of $n$ elements. The number of distinct permutations of $A$ is $n!$

Theorem 8
The number of r-permutations of a set of $n$ elements is $P(n, r) = \dfrac{n!}{(n - r)!}$

Theorem 9
The number of r-combinations of a set of $n$ elements is $C(n, r) = \dfrac{n!}{r!(n - r)!}$

Theorem 10
The set $\N$ of natural numbers is an infinite set.

Exercise
Prove Theorem 10.

Theorem 11
Let $A$ be a superset of $B$. If $B$ is infinite, then $A$ is infinite.

Collory 12
Every subset of a finite set is finite.

Exercise
Prove that $\Z$ is countably infinite using definition 5.

Theorem 13
The subset of real numbers, $[0,1]$, is not countably infinte.

Proof.

Let $f$ be arbitrary function $f: \N \to [0,1]$.
We can write
$f(1) = 0.a_{11}a_{12}a_{13} \ldots$
$f(2) = 0.a_{21}a_{22}a_{23} \ldots$
$f(3) = 0.a_{31}a_{32}a_{33} \ldots$
$f(4) = 0.a_{41}a_{42}a_{43} \ldots$
$\vdots$
$f(n) = 0.a_{n1}a_{n2}a_{n3} \ldots$
where $a_{ij}$ is the $j^{th}$ digit of the decimal representation of $f(i)$ and $i,j \in \N$. Now, we can construct a new number $x = 0.b_1b_2b_3b_4 \ldots$ where $b_i = 1$ if $a_{ii} \neq 1$, otherwise, $b_i = 2$. Then, we have that $x$ is not in the range of $f$.
Therefore, we have a contradiction. $[0,1]$ is not countably infinite.

Recurrence Relations

---

Definition 6
A linear homogeneous recurrence relation of order $k$ with constant coefficients is a recurrence relation of the form

$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}$$

where $c_1, c_2, \ldots, c_k$ are constants and $c_k \neq 0$.

The general solution for a linear homogeneous recurrence relation

$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}$$

is given by its characteristic polynomial

$$P(x) = x^k - c_1 x^{k-1} - c_2 x^{k-2} - \ldots - c_k$$

Let $r_1, r_2, \ldots r_k$ be the roots of $P(x)=0$. Then a sequence ${a_n}$ is the solution of the recurrence relation if and only if

$$a_n = \alpha_1 r_1^n + \alpha_2 r_2^n + \ldots + \alpha_k r_k^n$$

for $n \geq0 $ where $\alpha_1, \alpha_2, \ldots, \alpha_k$ are constants determined by the initial conditions of the recurrence relation.

If a root $r_i$ of multiplicity $m$ exist, then the general solution is given by

$$ a_n = P_1(n) r_1^n + P_2(n) r_2^n + \ldots + P_t(n)r_t^n $$

where $P_t(n)$ is a polynomial of degree $m-1$ in $n$.

e.g. $a_n = (\alpha_1 + \alpha_2 n) r_1^n + \alpha_3 r_2 ^n$

The rest of the lecture was about applying the above theorem to solve some recurrence relations. Some of the examples may be posted later, but for now, I will just leave the theorem and the definition of recurrence relations.