# Final Exam Syllabus – Discrete Math (V63.0120)

$\gdef\NN{\mathbb{N}} \gdef\QQ{\mathbb{Q}} \gdef\RR{\mathbb{R}} \gdef\ZZ{\mathbb{Z}} \gdef\P{\mathsf{P}} \gdef\cross{\times} \gdef\o{\circ} \gdef\id{\iota} \gdef\st{\; : \;} \gdef\mod{\text{ mod }} \gdef\union{\cup} \gdef\inter{\cap} \gdef\tor{\text{ or }} \gdef\tand{\text{ and }} \gdef\setdiff{\setminus}$
• Relations: 4.1-4.5
• Combinatorics: 5.1-5.4 (5.5 skipped)
• Probability: 6.1-6.3
• Graph theory: 7.1, 7.3 (7.2 skipped)
• Any previous material will only be covered implicitly through the above material.

## Sections 4.1-4.5 – Relations

A relation $R$ with domain $A$ and codomain $B$ is a subset of $A \cross B$: $R \subseteq A \cross B$.

Can be defined using one of the following:

• a formula for $R$ in set-builder notation
• an exhaustive enumeration of pairs in $R$
• a table
• an arrow diagram

### Possible properties of a relation

You should be able to prove or disprove any of the properties below.

• function: For every element $a \in A$, there is exactly one element $b \in B$ such that $(a,b) \in R$.
• image: An image of a function is the set of all possible outputs the function. This is a subset of the co-domain.
• inverse: $(b,a) \in R^{-1} \subseteq B\cross A$ exactly when $(a,b) \in R \subseteq A\cross B$
• invertible function: $R$ is an invertible function of both $R$ and $R^{-1}$ are functions. In this case, $R \o R^{-1} = \id_{B}$ and $R^{-1} \o R = \id_{A}$ (the identity functions).

For relations with the same domain and co-domain ($A=B$), the following additional properties may hold:

• reflexive: $\forall a \in A$, $(a,a)\in R$.
• irreflexive: $\forall a \in A$, $(a,a)\notin R$.
• symmetric: $\forall a,b \in A$, if $(a,b)\in R$ then $(b,a)\in R$.
• antisymmetric: $\forall a,b \in A$, if $a \ne b$ and $(a,b)\in R$ then $(b,a)\notin R$.
• Alternatively: $\forall a,b \in A$, if $(a,b)\in R$ and $(b,a)\in R$, then $a = b$.
• transitivity: $\forall a,b,c \in A$, if $(a,b)\in R$ and $(b,c)\in R$, then $(a,c)\in R$.

Special combinations

• Partial order: reflexive, antisymmetric, transitive
• Strict partial order: irreflexive, antisymmetric, transitive
• Equivalence relation: reflexive, symmetric, transitive
• results in a partitioning of the domain/codomain $A$

### Function $f: A \rightarrow B$

• one-to-one $\equiv$ injective: Every element in the domain is mapped to a unique element in the codomain. i.e. $\forall x_1, x_2 \in A, f(x_1) = f(x_2) \rightarrow x_1 = x_2$
• $f$ is one-to-one → $n(A) \leq n(B)$
• Proof strategy: "Let $x_1,x_2\in A$ such that $f(x_1)=f(x_2)$." Then show that $x_1=x_2$.
• onto $\equiv$ surjective: Every element in the codomain is produced by some element in the domain. i.e. $\forall x_1, x_2 \in A, f(x_1) = f(x_2) \rightarrow x_1 = x_2$
• $f$ is onto → $n(A) \geq n(B)$
• Proof strategy: "Let $y\in B$." Then produce an $x$ satisfying $f(x)=y$.
• one-to-one correspondence $\equiv$ invertible $\equiv$ bijective: Both one-to-one and onto.
• $f$ is a one-to-one correspondence → $n(A) = n(B)$

All three properties above are conserved via composition. E.g. the composition of two invertible functions is invertible.

### Set cardinality

• Two sets have the same cardinality if there is a one-to-one correspondence between them.
• A set $A$ is infinite if it has the same cardinality as a strict subset of itself. i.e. There is a map from $A$ to itself that is one-to-one, but not onto.
• Cantor-Bernstein Theorem: If you have two functions $f:A\rightarrow B$ and $g:B\rightarrow A$ that are both one-to-one, then the sets $A$ and $B$ have the same cardinality.
• Cantor's Theorem: For every set $A$, $A$ and $\P(A)$ do not have the same size.
• All sets that have the same cardinality at $\ZZ$ are said to be countable. E.g. $\NN, \QQ, \ZZ^2$, but not $\P(\ZZ)$ nor $\RR$.

## Sections 5.1-5.4 (5.5 skipped) – Combinatorics

### Counting rules

• Rule of sums for disjoint sets
• $n(A \union B)=n(A)+n(B)$
• $n(A \union B \union C)=n(A)+n(B)+n(C)$
• Rule of sums with overlap: (more general) $n(A \union B)=n(A)+n(B)-n(A\inter B)$
• Rule of complements: $n(A')=n(U)-n(A)$
• Rule of products:
• $n(A\cross A\cross … \cross A)$ (r times) $= n(A) \cdot n(A) \cdot … \cdot n(A) = n(A)^r$
• $n(A\cross B) = n(A)\cdot n(B)$
• $n(A\cross B\cross C) = n(A)\cdot n(B)\cdot n(C)$

### Useful operators

• Factorial: $n! = n \times (n-1) \times (n-2) \times … \times 2\times 1$
• Permutations: $P(n,r) = {}_nP_r = P^n_r = \frac{n \times (n-1) \times (n-2) \times … \times (n-r+1) \times (n-r) \times … \times 2 \times 1}{(n-r) \times … \times 2 \times 1} = \frac{n!}{(n-r)!}$
• Combinations: $C(n,r) = {}_nC_r = C^n_r = {n \choose r} = \frac{P(n,r)}{r!} = \frac{n!}{(n-r)!\;r!} = C(n,n-r)$
• Forms the entries of the Arithmetic Triangle, also called Pascal's Triangle.
• Binomial theorem: The coefficient of $x^r$ in $(1+x)^n$ is $C(n,r)$. i.e. $(1+x)^n = \sum_{i=0}^n C(n,r) x^r$
• Together, these facts imply that the sum of the $n^{th}$ row in Pascal's Triangle is $\sum_{i=0}^n C(n,r) = (1+1)^n = 2^n$.

### Ways to pick $r$ items from $n$

order matters? Y Ways to pick $r$ items from $n$ E.g. Pick 2 from $\{a,b,c\}$ $n^r$ ordered lists(a,a), (a,b), (a,c) (b,a), (b,b), (b,c) (c,a), (c,b), (c,c)  $C(r+n-1,r)=C(r+n-1,n-1)$unordered lists or bags(a,a), {a,b}, {a,c} (b,b), {b,c} (c,c)  $P(n,r)$ permutations (a,b), (a,c) (b,a), (b,c) (c,a), (c,b),  $C(n,r)=C(n,n-r)$ sets {a,b}, {a,c} {b,c} 

### Intuition and examples

• Ordered lists (order matters, repetitions allowed)
• Determine the number of $r$-letter words that can be made from an alphabet of size $n$.
• Determine the number of non-negative integers less than 1000 with no 9's.
• Number of possible birthday combinations of 23 people.
• Permutations (order matters, no repetitions)
• Anagrams
• Selecting a committee where the order matters. E.g. number of ways to select 3 people to be President, VP, and secretary.
• Number of ways for 23 people to have unique birthdays.
• Sets (order doesn't matter, no repetitions)
• Selecting a sub-group of people with irrelevant order. E.g. number of ways to select 3 people to be on the board of directors.
• Number of ways of picking 23 distinct days from a year.
• Unordered lists, bags (order doesn't matter, repetitions allowed)
• Pick 7 fruits from an unlimited supply of apples, bananas, and oranges.
• Equivalent to the number of non-negative integers satisfying $a+b+c=7$.
• Number of ways to fill a shopping bag with exactly $r$ fruits from an unlimited supply of $n$ distinct objects.
• Equivalent to the number of binary strings of length $r+n-1$ with exactly $r$ zeros (or exactly $n-1$ ones).
• Number of ways of picking 23 days from a year, where you can pick the same date multiple times.

## Sections 6.1-6.3 – Probability

### Properties

• $Prob(E) = \frac{n(E)}{n(E)+n(\overline{E})} = \frac{n(E)}{n(S)}$
• $Prob(E) + Prob(\overline{E})=1 \;\tor\; Prob(E) = 1 - Prob(\overline{E})$
• $Prob(E \tor F) = Prob(E) + Prob(F) - Prob(E \tand F)$
• $Prob(E \tand F) = Prob(E) Prob(F | E) = Prob(F) Prob(E | F)$ (Bayes' Law)
• Splitting an event into possible cases, or contexts.
• $Prob(E) = Prob(E \tand F) + Prob(E \tand \overline{F})$
• If $F, G, H$ disjoint and encompass the set of all possibilities – i.e. $Prob(F \tor G \tor H) = 1$, then
$Prob(E) = Prob(E \tand F) + Prob(E \tand G) + Prob(E \tand H)$

Disjoint events = Mutually-exclusive events

• $Prob(E \tand F) = Prob(E | F) = Prob(F | E) = 0$
• $Prob(E \tor F) = Prob(E) + Prob(F)$

Mutually-independent, or simply independent

• $Prob(E | F) = Prob(E)$ and $Prob(F | E) = Prob(F)$
• $Prob(E \tand F) = Prob(E) Prob(F)$
• Using decision trees/probability trees to compute probability
• Bernoulli trial: $Prob($E exactly $k$ times in $n$ indep. trials$)$ = $C(n,k) p^k (1-p)^{n-k}$ where $Prob(E) = p$ for each trial.
• Don't always have to do this using the formula explicitly.
• E.g. Probability of getting 6 exactly twice in five rolls of a fair die can be computed either of the following ways.
• With formula above: $C(5,2) \left(\frac{1}{6}\right)^2 \left(\frac{5}{6}\right)^3$
• Or by counting: $\frac{n(6 \text{ exactly two times})}{n(\text{total possibilities})} = \frac{C(5,2)5^3}{6^5}$
Numerator: (pick two positions out of five for the 6's) × (the number of ways to pick the three non-6's)
• E.g. Jim has a probability of $4/5$ of winning a poker game. What is the probability that in 5 games, he would win two and lose three?
• Use formula explicitly: $C(5,2) \left(\frac{4}{5}\right)^2 \left(\frac{1}{5}\right)^3$
• Use formula implicitly: The possibilities are WWLLL, WLWLL, LWWLL, etc. In other words, you have 5 spots "_ _ _ _ _". Two of these spots are W ("win") and three are L ("lose").
• There are $C(5,2)$ ways to pick the two winning spots out of 5. (And $C(3,3)=1$ way to pick the three losing spots from the remaining ones.)
• The probability of particular case with 2 wins and 3 losses (e.g. WWLLL) is $\left(\frac{4}{5}\right)^2 \left(\frac{1}{5}\right)^3$
• Putting it all together: The probability of him winning two out of 5 is: $C(5,2) \left(\frac{4}{5}\right)^2 \left(\frac{1}{5}\right)^3$.
• E.g. Probability of getting exactly three 4's and exactly one 3 when rolling a die 5 times.
• In other words, you have five spots "_ _ _ _ _". Two of these are 4 and one is 3. The last one is neither 3 nor 4.
• Pick three spots for 4: $C(5,3)$
• Pick 1 spot for 3 from the remaining spots: $C(2,1)$
• (Optional) Pick 1 spot for the non-3/4: $C(1,1)=1$
• The probability of each case (e.g. 434_4) where you have exactly three 4's and exactly one 3 is $\left(\frac{1}{6}\right)^3 \left(\frac{1}{6}\right)^1 \left(\frac{4}{6}\right)^1$
• Putting it all together: $C(5,3)C(2,1)\left(\frac{1}{6}\right)^3 \left(\frac{1}{6}\right)^1 \left(\frac{4}{6}\right)^1$
• Or by counting: So the number of ways to pick exactly three 4's and exactly one 3 is $C(5,3) C(2,1) 4$ (the last 4 is because we have 4 ways to pick the non-3/4). This means that the total probability is $\frac{C(5,3) C(2,1) 4}{6^5}$.

## Sections 7.1, 7.3 (7.2 skipped) – Graphs:

### Terminology and definitions

• Graph: G = (V,E)
• V = set of vertices/nodes
• degree of node v = deg(v) = number of edges incident to v, except that loops are counted twice
• E = set of edges - has two endpoints (vertices)
• node/vertex v is an endpoint of edge e &lrarr; edge e is incident with vertex v
• loop: if the two endpoints are the same
• parallel edges: edges with the same endpoints
• $\sum_{v\in V}\;deg(V) = 2\;n(E)$
• walk: sequence of alternating vertices and edges where every edge lies between its endpoints
• length = number of edges in the walk
• trivial walk: length=0 (E.g. A)
• closed walk: the first and the last vertex are the same (E.g. A 4 D 1 C 3 A)
• trail: walk with no repeated edges
• circuit: closed trail
• cycle: circuit with first/last vertex being the only repeated node
• path: walk with no repeated vertices (always a trail)
• Terms not included on the final: simple graph, directed graph, connected, subgraph, connected component

### Eulerian trails/circuits

• Eulerian trail/circuit: traverses every edge exactly once
• Provide an Eulerian trail/circuit of a graph
• Eulerian graph: one that contains an Eulerian circuit (i.e. a closed Eulerian trail)
• A connected graph is Eulerian if and only if every vertex has even degree.
• Make a graph Eulerian by adding the minimum number of edges.

### Isomorphisms

• Tell whether or not graphs are isomorphic. Prove using a simple argument (e.g. counting vertex degree) that two graphs are not isomorphic.
• Identifying planar graphs
• A graph is planar if and only if it does not contain $K_5$ and $K_{3,3}$ as a subgraph
• Draw planar embeddings of provided graphs.
• Euler's formula for planar graphs: $V+F=E+2$ (Note that the number $F$ of faces includes the unbounded face defined by the outer-most cycle of edges.)