Discrete Math-Final

{$ \def\NN{\mathbb{N}} \def\QQ{\mathbb{Q}} \def\RR{\mathbb{R}} \def\ZZ{\mathbb{Z}} \def\P{\mathsf{P}} \def\cross{\times} \def\o{\circ} \def\id{\iota} \def\st{\; : \;} \def\mod{\text{ mod }} \def\union{\cup} \def\inter{\cap} \def\tor{\text{ or }} \def\tand{\text{ and }} \def\setdiff{\setminus} $}

Final Exam Syllabus

  • 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? 
repetitions allowed?Yordered listunordered list, bag

E.g. Pick 2 from {$\{a,b,c\}$}

(a,a), (a,b), (a,c)
(b,a), (b,b), (b,c)
(c,a), (c,b), (c,c)
(a,a), {a,b}, {a,c}
       (b,b), {b,c}
       (a,b), (a,c)
(b,a),        (b,c)
(c,a), (c,b),      
       {a,b}, {a,c}

Pick {$r$} items from {$n$}
  order matters? 
repetitions allowed?Y{$n^r$}{$C(r+n-1,r)=C(r+n-1,n-1)$}

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


  • {$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 ⇆ 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.


  • 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.)