离散数学

Chapter-1 Logic & Proofs

Proposition

proposition: a declarative sentence that is either true or false, but not both
propositional variables: use variables to represent propositions
atomic propositions: Propositions that cannot be expressed in terms of simpler propositions
compound propositions: propositions formed from existing propositions using logical operators

Logical Operators

The word “or” in English can represent both inclusive and exclusive

Conditional Statements

The contrapositive has the same truth values as the original implication

Propositional Equivalences

tautology: A proposition which is always true
contradiction: A proposition which is always false
contingency: A proposition which is neither a tautology nor a contradiction

A compound proposition is satisfiable if there is an assignment of truth values to make it true.
A compound proposition is unsatisfiable when it is false for all assignments of truth values to its variables.

Logical Laws

Normal Forms

Disjunctive Normal Form: A formula is said to be in disjunctive normal form if it is written as a disjunction, in which all the terms are conjunctions of literals
Conjunctive Normal Form: A formula is said to be in conjunctive normal form if it is written as a conjunction, in which all the terms are disjunctions of literals

minterm: a conjunctive of literals in which each variable is represented exactly once
maxterm: a disjunctive of literals in which each variable is represented exactly once

Full Disjunctive Normal Form: Each term includes all variables
Full Conjunctive Normal Form: Each term includes all variables

Predicate Logic

$$\begin{align} &\begin{cases} \neg\forall xP(x)\equiv\exists x\neg P(x)\\ \neg\exists xP(x)\equiv\forall x\neg P(x) \end{cases}\\ &\begin{cases} \forall x(A(x)\land B(x))\equiv\forall xA(x)\land\forall xB(x)\\ \exists x(A(x)\lor B(x))\equiv\exists xA(x)\lor\exists xB(x) \end{cases}\\ &\begin{cases} \forall xA(x)\lor\forall xB(x)\Rightarrow\forall x(A(x)\lor B(x))\\ \exists x(A(x)\land B(x))\Rightarrow\exists xA(x)\land\exists xB(x) \end{cases} \end{align}$$

Nested Quantifiers

Nest quantifiers are quantifiers that occur within the scope of other quantifiers
The order of nested quantifiers matters if quantifiers are of different types

Prenex Normal Form

Any expression can be transformed into a prefix normal form.
(1) Eliminate all occurrences of $\rightarrow$ and $\leftrightarrow$ from the formula in question
(2) Move all negations inward such that negation only appear as part if literals
(3) Standardize the variables a part (when necessary)
(4) moving all quantifiers to the front of the formula

Rules of Inference

An argument is a sequence of statements that end with a conclusion
By valid ,we mean the conclusion must follow from the truth of the preceding statements
We use rules of inference to construct valid arguments

Direct Proof

A direct proof of a conditional statement $p\rightarrow q$ is constructed when the first step is the assumption that $p$ is true, subsequent steps are constructed using rules of inference, with the final step show that $q$ must also be true

Vacuous Proof

The conditional statement $p\rightarrow q$ is true when we know that $p$ is false, consequently, if we can show that $p$ is false, then we have a proof called a vacuous proof

Trivial Proof

We can prove a conditional statement $p\rightarrow q$ if we know that the conclusion $q$ is true

Proof by Contraposition

To proof the conditional statement $p\rightarrow q$ ,we can proof that $\neg q\rightarrow\neg p$

Proof by Contradiction

Proof $p$ by contradiction:
(1) assume $p$ is false
(2) deduces that $\neg p\rightarrow(q\land\neg q)$ ,which $q\land\neg q$ is a contradiction
(3) $p$ follows from the above
Proof $p\rightarrow q$ by contradiction:
(1) assume that both $\neg q$ and $p$ are true
(2) show that $(p\land\neg q)\rightarrow\mathrm{F}$

Proof by cases

Convince the reader that the cases are inclusive and establish all implications
Without Loss of Generality: WLOG

Exhaustive Proof

An exhaustive proof is a special type of proof by cases where each case involves checking a single example

Uniqueness Proof

To show that a theorem assert the existence of a unique element with a particular property

$$\exists x(P(x)\land\forall y(y\neq x\rightarrow\neg P(y)))$$

existence: show that an element $x$ with the desired property exists
uniqueness: show that if $y\neq x$ ,then $y$ does not have the desired property. Equivalently, we can also show that if $x$ and $y$ both have the desired property, then $x=y$

---

Chapter-2 Basic Structures

Definition of Sets

A set is an unordered collection of objects

• The objects in a set are call the elements, or members, of the set
• $a\in A$ means $A$ is a member of the set $A$
• $a\not\in A$ means $A$ is not a member of the set $A$

• empty set: $\emptyset$

  Description of Sets

• Roster method: listing all its members between braces $S=\{1,4,5\}$

• Brace notation with ellipses: $S=\{1,2,\cdots,998244353\}$
• Specification using set builder: $S=\{x|P(x)\}$
• Venn diagrams

  Relations between Sets

Subset: $A\subseteq B\Leftrightarrow\forall x(x\in A\rightarrow x\in B)$
Equal: $A=B\Leftrightarrow A\subseteq B\land B\subseteq A$
Proper Subset: $A\subset B\Leftrightarrow A\subseteq B\land A\neq B\Leftrightarrow \forall x(x\in A\rightarrow x\in B)\land\exists x(x\in B\land x\not\in A)$

The Size of Sets:
If there are exactly $n$ distinct elements in $S$ where $n$ is a nonnegative integer, we say that $S$ is a finite set and $n$ is the cardinality of $S$
Power Sets:
Given a set $S$ ,the power set of $S$ is the set of all subsets of the set $S$ , $\mathcal{P}(x)$ denotes the power set of $S$

$$\mathcal{P}(A)\subset\mathcal{P}(B)\Rightarrow A\subset B$$

Cartesian Products:
The ordered n-tuple $(a_1,a_2,\cdots,a_n)$ is the ordered collection that has $a_1$ as its first element, $a_2$ as its second element, . . . ,and $a_n$ as its nth element

$$A_1\times A_2\times\cdots\times A_n=\{(a_1,a_2,\cdots,a_n|a_i\in A_i\quad\text{for}\quad i=1,2,\cdots,n\}$$

Truth Sets of Quantifiers:
Given a predicate $P$ and a domain $D$ , the truth set of $P$ is the set of elements $x$ in $D$ for which $P(x)$ is true, which is $\{x\in D|P(x)\}$

Set Operations

Union: $A\cup B=\{x|x\in A\lor x\in B\}$
Intersection: $A\cap B=\{x|x\in A\land x\in B\}$
Difference: $A-B=\{x|x\in A\land x\not\in B\}$
Complement: $\overline{A}=\{x|x\not\in A\land x\in U\}$
Symmetric Difference: $A\oplus B=(A\cup B)-(A\cap B)$

Functions

Let $A$ and $B$ be nonempty sets, A function $f$ from $A$ to $B$

$$f:A\rightarrow B,\quad\forall a(a\in A\rightarrow\exists b(b\in B\land f(a)=b))$$

$A$ is called the domain of $f$ and $B$ is called the codomain of $f$

A function $f$ is injection (one-to-one function) if

$$\forall a\forall b(f(a)=f(b)\rightarrow a=b)$$

A function $f$ from $A$ to $B$ is called surjection (onto function) if

$$\forall b\in B\exists a\in A(f(a)=b)$$

The function is a bijection (one-to-one correspondence) if it’s both one-to-one and onto

Inverse Functions

Let $f$ be a bijection from $A$ to $B$ ,then the inverse function of $f$ ,denoted as $f^{-1}$ is the function from $B$ to $A$ defined as

$$f^{-1}(y)=x\quad\mathrm{iff}\quad f(x)=y$$

Function $f$ is invertible if and only if $f$ is bijective

Composition of Functions

Let $g$ be a function from the set $A$ to the set $B$ and let $f$ be a function from the set $B$ to the set $C$ ,the composition of the function $f$ and $g$ denoted by $f\circ g$ is defined by

$$f\circ g(a)=f(g(a))$$

$f\circ g$ can not be defined unless the range of $g$ is a subset of the domain of $f$

Sequence

A sequence is a function from a subset of the set of integers to a set $S$ , we use the notation $a_n$ to denote the image of the integer $n$ ,we call a term of the sequence

geometric progression: the initial term $a$ and common ratio $r$ are real numbers

$$a,ar,ar^2,\cdots,ar^n$$

arithmetic progression: the initial term $a$ and common difference $d$ are real numbers

$$a,a+d,a+2d\cdots,a+nd$$

Cardinality of Sets

The cardinality of a set $A$ is equal to the cardinality of a set $B$ ,denoted $|A|=|B|$, if and only if there exists a bijection from $A$ to $B$

If there is an injection from $A$ to $B$ , the cardinality of $A$ is less than or the same as the cardinality of $B$ and we write $|A|\leq|B|$ ,when $|A|\leq |B|$ and $A$ and $B$ have different cardinality, then $|A|<|B|$

Countable

A set that is either finite or has the same cardinality as the set of positive integers called countable
A set that is not countable is called uncountable
When an infinite set $S$ is countable, we denote the cardinality of $S$ by $\aleph_0$
If $|A|=|\mathrm{Z}_+|$ , the set $A$ is countable infinite

Cantor’s Theorem

The cardinality of the powerset of an arbitrary set has a greater cardinality than the original arbitrary set.

$$|\mathcal{P}(\aleph_k)|=|\aleph_{k+1}|$$

---

Chapter-3 Algorithm

The Growth of Functions

asymptotic running time is the number of operation used by the algorithm as the input size approaches infinity

Big-O notation

Let $f$ and $g$ be functions from $\mathrm{Z}$ (or $\mathrm{R}$) to $\mathrm{R}$ , we say that $f(x)$ is $O(g(x))$ if there are constants $C$ and $k$ such that $|f(x)|\leq C|g(x)|$ whenever $x>k$

Big-Omega notation

Let $f$ and $g$ be functions from $\mathrm{Z}$ (or $\mathrm{R}$) to $\mathrm{R}$ , we say that $f(x)$ is $\Omega(g(x))$ if there are constants $C$ and $k$ such that $|f(x)|\geq C|g(x)|$ whenever $x>k$

Big-Theta notation

Let $f$ and $g$ be functions from $\mathrm{Z}$ (or $\mathrm{R}$) to $\mathrm{R}$ , we say that $f(x)$ is $\Theta(g(x))$ if $f(x)$ is $O(g(x))$ and $f(x)$ is $\Omega(g(x))$ ,there are constants $C_1,C_2$ and $k$ such that $0\leq C_1g(x)\leq f(x)\leq C_2g(x)$ whenever $x>k$

---

Chapter-4 Number Theory

Division

The notation $a\mid b$ denotes that $a$ divides $b$ ,and $a\not\mid b$ denotes that $a$ does not divide $b$
Let $a,b$ and $c$ be integers, where $a\neq0$ ,then
(1) if $a\mid b$ and $a\mid c$ ,then $a\mid(b+c)$
(2) if $a\mid b$ then $a\mid bc$ for all integers $c$
(3) if $a\mid b$ and $b\mid c$ ,then $a\mid c$
(4) if $a\mid b$ and $a\mid c$ ,then $a\mid mb+nc$ whenever $m$ and $n$ are integers

Modular Arithmetic

We use the notation $a\equiv b(\mathrm{mod}\,m)$ to indicate that $a$ is congruent to $b$ modulo $m$

(1) Let $a$ and $b$ be integers, and $m$ be a positive integer, then $a\equiv b(\mathrm{mod}\,m)$ if and only if $a\,\mathrm{mod}\,m=b\,\mathrm{mod}\,m$
(2) Let $m$ be a positive integer, if $a\equiv b(\mathrm{mod}\,m)$ and $c\equiv d(\mathrm{mod}\,m)$, then $a+c\equiv b+d(\mathrm{mod}\,m)$ and $ac\equiv bd(\mathrm{mod}\,m)$
(3) Let $m$ be a positive integer and let $a$ and $b$ be integers, then $(a+b)\,\mathrm{mod}\,m=((a\,\mathrm{mod}\,m)+(b\,\mathrm{mod}\,m))\,\mathrm{mod}\,m$ and $ab\,\mathrm{mod}\,m=((a\,\mathrm{mod}\,m)(b\,\mathrm{mod}\,m))\,\mathrm{mod}\,m$

Arithmetic Modulo m

Closure: If $a$ and $b$ belong to $\mathrm{Z}_m$ ,then $a+_mb$ and $a\cdot_mb$ belong to $\mathrm{Z}_m$
Associativity: $(a+_mb)+_mc=a+_m(b+_mc)$ and $(a\cdot_mb)\cdot_mc=a\cdot_m(b\cdot_mc)$
Commutativity: $a+_mb=b+_ma$ and $a\cdot_mb=b\cdot_ma$
Identity elements: $a+_m0=0+_ma=a$ and $a\cdot_m1=1\cdot_ma=a$
Additive inverses: $a+_m(m-a)=0$ and $0+_m0=0$
Distributivity: $a\cdot_m(b+_mc)=(a\cdot_mb)+(a\cdot_mc)$ and $(a+_mb)\cdot_mc=(a\cdot_mc)+_m(b\cdot_mc)$

Primes

An integer $p$ greater than $1$ is called prime if the only positive factors of $p$ are $1$ and $p$
A positive integer that is greater than $1$ and is not prime is called composite

the fundamental theorem of arithmetic
Every integer greater than $1$ can be written uniquely as a prime or as the product of two or more primes, where the prime factors are written in order of nondecreasing size.

GCD and LCM

Let $a$ and $b$ be integers, not both zero. The largest integer $d$ such that $d\mid a$ and $d\mid b$ is called the greatest common divisor of $a$ and $b$, denoted by $\gcd(a, b)$

The integers $a$ and $b$ are relatively prime if their greatest common divisor is $1$

The integers $a_1, a_2,\cdots, a_n$ are pairwise relatively prime if $\gcd(a_i , a_j ) = 1$ whenever $1\leq i < j \leq n$

The least common multiple of the positive integers a and b is the smallest positive integer that is divisible by both $a$ and $b$, denoted by $\mathrm{lcm}(a, b)$

(1) If $\gcd(a,b)=1$ and $a\mid bc$ ,then $a\mid c$
(2) If $p$ is prime and $p\mid a_1a_2\cdots a_n$ where each $a_i$ is an integer, then $p|a_i$ for some $i$
(3) If $ac\equiv bc(\mathrm{mod}\,m)$ and $\gcd(c,m)=1$ ,then $a\equiv b(\mathrm{mod}\,m)$

Bezout’s Theorem

If $a$ and $b$ are positive integers, then there exist integers $s$ and $t$ such that $\gcd(a, b) = sa + tb$

Fermat’s Little Theorem

If $p$ is prime and $a$ is an integer not divisible by $p$ ,then

$$a^{p-1}\equiv 1(\mathrm{mod}\,p)$$

Pseudoprimes

Let $b$ be a positive integer. If $n$ is a composite positive integer, and $b^{n−1} \equiv 1 (\mathrm{mod}\, n)$, then $n$ is called a pseudoprime to the base $b$

---

Chapter-5 Induction

Mathematical Induction

mathematical induction is used to prove propositions of form $\forall nP(n)$ where the domain of discourse is the set of positive integers:

$$P(n_0)\land\forall k\geq n_0(P(k)\rightarrow P(k+1))\rightarrow\forall n\geq n_0(P(n))$$

(1) Basis step: Establish $P(1)$
(2) Inductive step: Prove that $P(k)\rightarrow P(k+1)$ for $k\geq 1$
(3) Conclusion: The basis step and the inductive step together imply $\forall nP(n)$

Proof of Mathematical induction
The validity of mathematical induction follows from the well-ordering property for the set of $\mathrm{Z}^+$.
(1) Assume that there is at least of positive integer for which $P(n)$ is false
(2) $S$ is the set of positive integer for which $P(n)$ is false, then $S$ is nonempty
(3) By the well-ordering property, $S$ has a least element, which will be denoted by $m$
(4) Then $m\neq1,m-1$ is a positive integer, $m-1$ is not in $S$ ,so $P(m-1)$ is true
(5) Since the implication $P(m-1)\rightarrow P(m)$ is also true ,$P(m)$ must be true
by contradiction ,$\forall nP(n)$

Strong Induction

strong induction or second principle of mathematical induction.

$$P(n_0)\land\forall k\geq n_0(P(n_0)\land P(n_0+1)\land\cdots\land P(k)\rightarrow P(k+1))\rightarrow \forall n\geq n_0(P(n))$$

(1) Basis step: Establish $P(n_0)$
(2) Inductive Step: Prove $P(n_0)\land P(n_0+1)\land\cdots\land P(k)\rightarrow P(k+1)$
(3) Conclusion: the basis step and the inductive step together imply $\forall n\geq n_0 P(n)$

Note
The validities of both mathematical induction and strong induction follow from the well-ordering property. In fact, mathematical induction, strong induction, and well-ordering are all equivalent principles.

Structural Induction

recursion is a principle closely related to mathematical induction.
In a recursive definition, an object is defined in terms of itself.

(1) basis step: Show that the result holds for all elements specified in the basis step of thee recursive definition to be in the set
(2) Recursive step: Show that if the statement is true for each of the elements used to construct new elements in the recursive step of the definition, the result holds for these new elements.

---

Chapter-6 Counting

Counting Principles

The Sum Rule
If $S$ and $T$ are disjoint finite sets, then $|S\cup T|=|S|+|T|$
The Product Rule
If $S$ and $T$ are finite sets, then $|S\times T|=|S|\times|T|$
The Inclusion-Exclusion Principle
If $S$ and $T$ are finite sets, then $|S\cup T|=|S|+|T|-|S\cap T|$

The Pigeonhole Principle

If $k$ is a positive integer and $k+1$ or more objects are placed into $k$ boxes, then there is at least one box containing two or more of the objects.

If $n$ objects are placed into $k$ boxes, then there is at least one box containing at least $\lceil n/k\rceil$ objects.

Applications of P&C

r-permutation with repetition: The number of r-permutations of a set of $n$ objects with repetition allowed

$$n^r$$

n-permutation with limited repetition: the number of different permutation of $n$ objects, where there are $n_1,n_2,\cdots,n_k$ indistinguishable objects

$$\frac{n!}{n_1!n_2!\cdots n_k!}$$

r-circle permutation: The number of r-circle permutations of a set of $n$ objects is

$$\frac{P(n,r)}{r}$$

r-combination with repetition: The number of r-combination from a set with $n$ elements when repetition of elements is allowed is

$$\begin{pmatrix}n+r-1\\r\end{pmatrix}$$

Indistinguishable objects and distinguishable boxes: The number of ways to distribute $n$ indistinguishable objects into kk distinguishable boxes is

$$\begin{pmatrix}n-1\\k-1\end{pmatrix}$$

Combinatorial Identities

the binomial theorem: Let $x$ and $y$ be variables, and let $n$ be a nonnegative integer

$$\begin{align} (x+y)^n=\sum_{j=0}^n\begin{pmatrix}n\\j\end{pmatrix}x^{n-j}y^j \end{align}$$

Pascal’s identity: Let $n$ and $k$ be positive integers with $k\leq n$ ,then

$$\begin{pmatrix}n+1\\k\end{pmatrix}= \begin{pmatrix}n\\k-1\end{pmatrix}+ \begin{pmatrix}n\\k\end{pmatrix}$$

Vandermonde’s identity: Let $m,n$ and $r$ be nonnegative integer with $r\leq m,n$，then

$$\begin{pmatrix}m+n\\r\end{pmatrix}= \sum_{k=0}^r \begin{pmatrix}m\\r-k\end{pmatrix} \begin{pmatrix}n\\k\end{pmatrix}$$

Let $n$ and $r$ be nonnegative integer with $r\leq n$ ,then

$$\begin{pmatrix}n+1\\r+1\end{pmatrix}= \sum_{j=r}^n \begin{pmatrix}j\\r\end{pmatrix}$$

Combinatorial Proofs

double counting proof: uses counting arguments to prove that both sides of an identity count the same objects, but in different ways.

bijective proof: shows that there is a bijection between the sets of objects counted by the two sides of the identity.

---

Chapter-8 Counting

Catalan Numbers

Note That the initial conditions are $C_0=1$ and $C_1=1$

$$\begin{align} C_n&=C_0C_{n-1}+C_1C_{n-2}+\cdots+C_{n-2}C_1+C_{n-1}C_0\\ &=\sum_{k=0}^{n-1}C_kC_{n-k-1}\\ &=\frac{C(2n,n)}{n+1} \end{align}$$

LRR

Linear homogeneous recurrence relation with constant coefficients refers to a recurrence relation of the form

$$a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}$$

where $c_1,c_2,\cdots,c_k$ are real numbers, and $c_k\neq0$

Suppose that the characteristic equation $r^k-c_1r^{k-1}-\cdots-c_k=0$has $k$ distinct roots $r_1,r_2,\cdots,r_k$ Then a sequence $\{a_n\}$ is a solution of the recurrence relation

$$a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}$$

if and only if $a_n=\alpha_1r_1^n+\alpha_2r_2^n+\cdots+\alpha_kr_k^n$
if the characteristic equation has t distinct roots $r_1,r_2,\cdots,r_t$

$$\begin{align} a_n =&(\alpha_{1,0}+\alpha_{1,1}n+\cdots+\alpha_{1,m_1-1}n^{m_1-1})r_1^n\\ +&(\alpha_{2,0}+\alpha_{2,1}n+\cdots+\alpha_{2,m_2-1}n^{m_2-1})r_2^n\\ +&\quad\cdots\\ +&(\alpha_{t,0}+\alpha_{t,1}n+\cdots+\alpha_{t,m_t-1}n^{m_t}-1)r_t^n \end{align}$$

LNRR with Constant Coefficients

If $\{a_n^{(p)}\}$ is a particular solution of the nonhomogeneous linear recurrence relation (LNRR) with constant coefficients

$$a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}+F(n)$$

then every solution is of the form $\{a_n^{(p)}+a_n^{(h)}\}$ where $\{a_n^{(h)}\}$ is a solution of the associated homogeneous recurrence relation

Suppose that $F(n)=(b_tn^t+b_{t-1}n^{t-1}+\cdots+b_1n+b_0)s^n$ , the multiplicity of $s$ in the characteristic equation is $m$ ,there is a particular solution of the form

$$n^m(p_tn^t+p_{t-1}n^{t-1}+\cdots+p_1n+p_0)s^n$$

Divide-and-Conquer

Let $f$ be an increasing function that satisfies the recurrence relation

$$f(n)=af(n/b)+c$$

whenever $n$ is divisible by $b$ , where $a\geq1$ , $b\in Z^+,b>1,c\in R^+$

$$f(n)\text{is} \begin{cases} O(n^{\log_ba}),&a>1\\ O(\log n),&a=1 \end{cases}$$

when $n=b^k$ and $a\neq1$ when $k$ is a positive integer,

$$f(n)=C_1n^{\log_ba}+C_2,C_1=f(1)+c/(a-1),C_2=-c/(a-1)$$

Master Theorem

Let $f$ be an increasing function that satisfies the recurrence relation

$$f(n)=af(n/b)+cn^d$$

whenever $n=b^k$ ,where $k\in Z^+,a\geq1,b>1,b\in Z,c\in R^+,d\in R,d\geq0$

$$f(n)\text{is} \begin{cases} O(n^d)&a<b^d\\ O(n^d\log n)&a=b^d\\ O(n^{\log_ba})&a>b^d \end{cases}$$

Generating Functions

The generating function for the sequence $a_0,a_1,\cdots,a_k,\cdots$ of real numbers is the infinite series

$$G(x)=a_0+a_1x+\cdots+a_kx^k+\cdots=\sum_{k=0}^\infty a_kx^k$$

Extended Binomial Theorem

Let $x$ be a real number with $|x|<1$ and let $u$ be a real number, then

$$(1+x)^u=\sum_{k=0}^\infty\begin{pmatrix}u\\k\end{pmatrix}x^k$$

Useful GFunctions

Inclusion-Exclusion

Let $A_1,A_2,\cdots A_n$ be finite sets, then

$$\begin{align} |A_1\cup A_2\cup\cdots\cup A_n| &=\sum_{1\leq i\leq n}|A_i| -\sum_{1\leq i< j\leq n}|A_i\cap A_j|\\ &+\sum_{1\leq i<j<k\leq n}|A_i\cap A_j\cap A_k|-\cdots+(-1)^{n+1}|A_1\cap A_2\cap\cdots\cap A_n| \end{align}$$

Derangement

Counting the permutations of $n$ objects that leave no objects in their original positions, the number of derangements of a set with $n$ elements is

$$\begin{align} D_n&=n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!})\\ &=(n-1)(D_{n-1}+D_{n-2}) \end{align}$$

---

Chapter-9 Relations

Relations and Properties

A binary relation from $A$ to $B$ is a subset of $A\times B$
A relation on a set $A$ is a relation from $A$ to $A$

The relation $R$ on a set $A$ is transitive if and only if $R^n\subseteq R$ for $n=1,2,3\cdots$

n-ary Relations

An n-ary relation is a subset of $A_1\times A_2\times\cdots\times A_n$
The sets $A_1,A_2,\cdots,A_n$ are called the domains of the relation, $n$ is called its degree
A domain is a primary key when no two n-tuples in the relation have the same value

Matrices-Relations

$R$ is symmetric if and only if $M_R=(M_R)^t$
$\begin{cases}M_{R_1\cup R_2}=M_{R_1}\lor M_{R_2}\\M_{R_1\cap R_2}=M_{R_1}\land M_{R_2}\\M_{S\circ R}=M_R\odot M_S\end{cases}$

Closures of Relations

the closure of $R$ with respect to $P$ is the relation $S$ on $A$ with property $P$ that contains $R$ and is a subset of every subset containing $R$ with property $P$

There is a path of length $n$ from $a$ to $b$ if and only if $(a,b)\in R^n$

The connectivity relation $R^\ast$ consists of the pairs $(a,b)$ such that there is a path of length at least one from $a$ to $b$ in $R$ , $\begin{align}R^\ast=\bigcup_{n=1}^\infty R^n\end{align}$

$M_{R^\ast}=M_R\lor M_R^{[2]}\lor M_R^{[3]}\lor\cdots\lor M_R^{[n]}$

Warshall’s Algorithm

$W_k=[w_{ij}^{[k]}],\quad w_{ij}^{[k]}=w_{ij}^{[k-1]}\lor(w_{ik}^{[k-1]}\land w_{kj}^{[k-1]})$

Equivalence Relations

Equivalence relation is reflexive, symmetric and transitive.

Two elements $a$ and $b$ that are related by an equivalence relation are called equivalent. $a\sim b$ denote that $a$ and $b$ are equivalent elements with respect to a particular equivalence relation

Equivalence Classes

Let $R$ be a equivalence relation on a set $A$ . The set of all elements that are related to an element $a$ of $A$ is called the equivalence class of $a$

$$[a]_R=\{s|(a,s)\in R\}$$

If $b\in[a]_R$ , then $b$ is called a representative of this equivalence class

Let $R$ be an equivalence relation on a set $A$. these statements for elements $a$ and $b$ of $A$ are equivalent: $aRb,\quad [a]=[b],\quad [a]\cap[b]\neq\emptyset$

Let $R$ be an equivalence relation on a set $S$ , Then the equivalence classes of $R$ form a partition of $S$ . Conversely , given a partition $\{A)i|i\in I\}$ of the set $S$ , there is an equivalence relation $R$ that has the sets $A_i,i\in I$ as its equivalence classes.

Partial Orderings

A relation $R$ on $S$ is called a partial ordering if it is reflexive, antisymmetric and transitive. A set $S$ together with a partial ordering $R$ is called a partially ordered set, and is denoted by $(S,R)$ . Members of $S$ are called elements of the poset.

The elements $a$ and $b$ of a poset $(S,\preceq)$ are called comparable if either $a\preceq b$ or $b\preceq a$ . When $a$ and $b$ are elements of $S$ such that neither $a\preceq b$ nor $b\preceq a$ , $a$ and $b$ are called incomparable.

If $(S,\preceq)$ is a poset and every two elements of $S$ are comparable , $S$ is called a totally ordered or linearly ordered set, and $\preceq$ is called a total order or a linear order. A totally ordered set is also called a chain.

$(S,\preceq)$ is a well-ordered set if it is a poset such that $\preceq$ is a total ordering and every nonempty subset of $S$ has a least element.

Suppose that $S$ is a well-ordered set. Then $P(x)$ is true for all $x\in S$
For every $y\in S$, if $P(x)$ is true for all $x\in S$ with $x\prec y$ , then $P(y)$ is true

An element of is called maximal if it is not less than any element of the poset
An element of is called minimal if it is not greater than any element of the poset

greatest element is an element in a poset that is greater than every other element
least element is an element in a poset that is less than every other element

upper bound /lower bound /least upper bound /greatest lower bound

A partially ordered set in which every pair of elements has both a least upper bound and a greatest lower bound is called a lattice

Every finite nonempty poset $(S,\preceq)$ has at least one minimal element

---

Chapter-10 Graphs

Graphs and Graph Models

A graph $G=(V,E)$ consists of $V$ ,a nonempty set of vertices (or nodes) and $E$ ,a set of edges. Each edge has either $1$ or $2$ vertices associated with it , called its endpoints.

A digraph $(V, E)$ consists of a nonempty set of vertices $V$ and a set of directed edges $E$. Each directed edge is associated with an ordered pair of vertices. The directed edge $(u, v)$ is said to start at $u$ and end at $v$.

Graph Terminology

The set of all neighbors of a vertex $v$ of $G=(V,E)$ , denoted by $N(v)$ , is called the neighborhood of $v$ . If $A$ is a subset of $V$ , we denote by $N(A)$ the set of all vertices in $G$ that are adjacent to at least one vertex in $A$ , $N(A)=\bigcup_{c\in A}N(v)$

The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex v is denoted by $\deg(v)$

Graph Properties

Let $G=(V,E)$ be an undirected graph with $m$ edges, then

$$2m=\sum_{v\in V}\deg(v)$$

An undirected graph has an even number of vertices of odd degree.

In a graph with directed edges the in-degree of a vertex $v$, denoted by $\deg^−(v)$, is the number of edges with $v$ as their terminal vertex. The out-degree of $v$, denoted by $deg^+(v)$, is the number of edges with $v$ as their initial vertex.

Let $G=(V,E)$ be a graph with directed edges, then

$$\sum_{v\in V}\deg^-(v)=\sum_{v\in V}\deg^+(v)=|E|$$

$K$-Complete $C$-Cycle $W$-Wheels $Q$-Cube

Bipartite Graphs and Matchings

A simple graph $G$ is called bipartite if its vertex set $V$ can be partitioned into two disjoint set $V_1$ and $V_2$ such that every edge in the graph connects a vertex in $V_1$ and a vertex in $V_2$ , the pair $(V_1,V_2)$ is a bipartition of the vertex set $V$ of $G$

A simple graph is bipartite if and only if it is possible to assign one of two different colors to each vertex of the graph so that no two adjacent vertices are assigned the same color.

A matching $M$ in a simple graph $G=(V,E)$ is a subset of the set $E$ of edges of the graph such that no two edges are incident with the same vertex.

A matching $M$ in a bipartite graph $G=(V,E)$ with bipartition $(V_1,V_2)$ is a complete matching from $V_1$ to $V_2$ if every vertex in $V_1$ is the endpoint of an edge in the matching, equivalently $|M|=|V_1|$

Hall’s Marriage Theorem

The bipartite graph $G=(V,E)$ with bipartition $(V_1,V_2)$ has complete matching from $V_1$ to $V_2$ if and only if $|N(A)|\geq|A|$ for all subsets $A$ of $V_1$

Subgraphs

A subgraph of a graph $G=(V,E)$ is a graph $H=(W,F)$ ,where $W\subseteq V$ and $F\subseteq E$
A subgraph $H$ of $G$ is a proper subgraph of $G$ if $H\neq G$

Let $G=(V,E)$ be a simple graph, the subgraph induce by a subset $W$ of the vertex set $V$ is the graph $(W,F)$ , where the edges set $F$ contains an edge in $E$ if and only if both endpoints of this edge are in $W$

Graph Isomorphism

The simple graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are isomorphic if there exists a one-to-one and onto function $f$ from $V_1$ to $V_2$ with the property that $a$ and $b$ are adjacent in $G_1$ if and only if $f(a)$ and $f(b)$ are adjacent in $G_2$ ,for all $a$ and $b$ in $V_1$

Connectivity

A path is a sequence of edges that begins at a vertex of a graph and travels from vertex to vertex along edges of the graph.

A path or circuit is simple if it does not contain the same edge more than once.

An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph. We say that we disconnect a graph when we remove vertices or edges, or both, to produce a disconnected subgraph.

There is a simple path between every pair of distinct vertices of a connected undirected graph.

A connected component of a graph $G$ is a connected subgraph of G that is not a proper subgraph of another connected subgraph of $G$.

Cut Vertices

Sometimes the removal from a graph of a vertex and all incident edges produces a subgraph with more connected components. Such vertices are called cut vertices(or articulation points).

Connected graphs without cut vertices are called nonseparable graphs

The vertex connectivity of a noncomplete graph $G$ , denoted by $\kappa(G)$ the minimum number of vertices that can be removed to disconnect a graph.

A graph is k-connected (or k-vertex-connected), if $\kappa(G)\geq k$

The edge connectivity of a graph $G$ , denoted by $\lambda(G)$ is the minimum number of edges in an edge cut of $G$

An inequality for vertex connectivity and edge connectivity $\kappa(G)\leq\lambda(G)\leq\min_{v\in V}\deg(v)$

Connectedness in Digraphs

A directed graph is strongly connected if there is a path from $a$ to $b$ and from $b$ to $a$ whenever $a$ and $b$ are vertices in the graph.

A directed graph is weakly connected if there is a path between every two vertices in the underlying undirected graph.

The strongly connected components of $G$ is the subgraphs that are strongly connected but not contained in larger strongly connected subgraphs.

Euler Paths and Circuits

A Euler circuit in a graph $G$ is a simple circuit containing every edge of $G$ .
An Euler path in $G$ is a simple path containing every edge of $G$

A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree.

A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.

Hamilton Paths and Circuits

A simple path in a graph $G$ that passes through every vertex exactly once is called a Hamilton path, and a simple circuit in a graph $G$ that passes through every vertex exactly once is called a Hamilton circuit.

If $G$ is a simple graph with n vertices with $n\geq3$ such that the degree of every vertex in $G$ is at least $n/2$, then $G$ has a Hamilton circuit.

If $G$ is a simple graph with $n$ vertices with $n \geq 3$ such that $\deg(u) + \deg(v) \geq n$ for every pair of nonadjacent vertices $u$ and $v$ in $G$, then $G$ has a Hamilton circuit.

Shortest-Path Problems

Graphs that have a number assigned to each edge are called weighted graphs.

Planar Graphs

A graph is called planar if it can be drawn in the plane without any edges crossing.

$$2e=\sum_{\text{all region R}}\deg(R)\geq3r$$

If $G$ is a connected planar simple graph with $e$ edges and $v$ vertices, where $v\geq3$, then $e\leq 3v − 6$.

If a connected planar simple graph has $e$ edges and $v$ vertices with $v\geq3$ and no circuits of length three, then $e\leq 2v − 4$.

If $G$ is a connected planar simple graph, then $G$ has a vertex of degree not exceeding five.

Euler’s Formula

Let $G$ be a connected planar simple graph with $e$ edges and $v$ vertices. Let $r$ be the number of regions in a planar representation of $G$. Then $r=e-v+2$

Kuratowski’s Theorem

A graph is nonplanar iif it contains a subgraph homeomorphic to $K_{3,3}$ or $K_5$

Dual Graph

Each map in the plane can be represented by a graph, each region of the map is represented by a vertex. Edges connect two vertices if the vertices have a common border. The resulting graph is called the dual graph of the map.

The chromatic number of a graph is the least number of colors needed for a coloring of this graph. The chromatic number of a graph $G$ is denoted by $\chi(G)$.

the Four Color Theorem

The Chromatic number of a planar graph is no greater than four
Any graph with chromatic number $\geq5$ is not a planar graph

---

Chapter-11 Trees

Definition of Trees

A tree is a connected undirected graph with no simple circuits

An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices

Rooted Trees

A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.

m-ary tree: every internal vertex has no more than $m$ children.
full m-ary tree: every internal vertex has exactly $m$ children
binary tree: An m-ary tree with $m=2$

An ordered rooted tree is a rooted tree where the children of each internal vertex are ordered.

Properties of Trees

A tree with $n$ vertices has $n-1$ edges
A full m-ary tree with $i$ internal vertices contains $n=mi+1$ vertices

A full m-ary with

• $n$ vertices has $i=(n-1)/m$ internal vertices and $l=[(m-1)n+1]/m$ leaves
• $i$ internal vertices has $n=mi+1$ vertices and $l=(m-1)i+1$ leaves
• $l$ leaves has $n=(ml-1)/(m-1)$ vertices and $i=(l-1)/(m-1)$ internal vertices

The level of a vertex $v$ is the length of the unique path from the root to this vertex.
The level of the root is defined to be zero.
The height of a rooted tree is the maximum of the levels of vertices.
A rooted m-ary tree of height $h$ is balanced if all leave are at level $h$ or $h-1$
There are at most $m^h$ leaves in an m-ary tree of height $h$

If an m-ary tree of height $h$ has $l$ leaves, then $h\geq\lceil \log_ml\rceil$
If the m-ary tree if full and balanced, then $h=\lceil\log_ml\rceil$

Expression Notations

We obtain the prefix form of an expression when we traverse its rooted tree in preorder
Expressions written in prefix form are said to be in Polish notation

We obtain the postfix form of an expression by traversing its binary tree in postorder
Expressions written in postfix form are said to be in reverse Polish notation

Spanning Trees

Let $G$ be a simple graph. A spanning tree of $G$ is a subgraph of $G$ is a tree obtaining every vertex of $G$

A simple graph is connected if and only if it has a spanning tree

Minimum Spanning Trees

A minimum spanning tree in a connected weighted graph is a spanning tree that has the smallest possible sum of weights of its edges.