I find it a good time to recap this session’s discrete math course, since I will be taking the finals on Monday. I hope you will enjoy this ride with me!
By the way, the reason that I call discrete math ‘the art of counting’ is that enumeration is indeed an important part of it. You will find them basically everywhere in the following sections!
Sets, Functions, Logic & Proof
Sets and functions are fundamental since they are the notations for everything.
There are loads of details, so they won’t fit into this log. Here, I will focus more on the function part that will be particular handy in the ‘counting problems’ section.
Simply put, a function is a mapping that maps one input to exactly one output. Any function can be described by its three main components: domain, codomain & range. This slide from Prof. Cai is a good illustration of the three:
(P.S. You can find these resources at his personal repo: My teachings | Throw All Things Away)
At the same time, three properties stem from the three main components. They are surjection(onto: range=codomain), injection(1-to-1: each element of the codomain is the image at most one element of the domain) and bijection(injection and surjection combined). Bijection is particularly useful property since it allows for the conversion between problem A & B. Examples of this can be found in the later sections.
Sequences & Series
For series & sequences, the most important thing is to understand their convergence. So here I will post a cookbook for convergence tests:
(The tables are taken from Elementary Calculus textbook)
Convergence for sequences
Procedures of the Monotone Bounded Test: Check monotone + check bounded. The ratio test is handy (Check the following example).
Convergence for series
Counting problems & Tools
Transform a hard problem via bijection
A typical example: counting the number of labelled trees. For this task, we rely on the bijection between labelled trees and prufer code. This give us the Cayley’s Formula for counting labelled trees: nn-2
(Find the proof of the bijection in the ‘induction’ section)
Generating Functions
First, we look at definition of generating functions:
Rigorous speaking, generating functions are not functions. Mathematicians have constructed a new set of operations (add, subtract, multiply, multiplicative-inverse, derivatives, integration …) for them. My buddy Mr. Xie told me that to systematically learn about all of this, you can take the abstract algebra course.
Nevertheless, when using generative functions as tools for enumeration, it is okay to consider them as a regular function (and just apply the same rules of multiplying polynomials when multiplying them).
The following example illustrates how generating functions are used to compute integer compositions:
To make to computation easier, we usually write generating functions in their closed-forms before multiplying them. Then we expand them after the multiplication.
Warning: Do NOT use the regular generating functions for compositions tasks where the sequence matters (e.g. Strings)! Use the exponential generating function instead:
Induction
Prove by induction is something that you should always pack in your tool box. The procedure: 1. Validate the base case (e.g. n = 1); 2. Set up the induction hypothesis (Argument is true for n = k, k >= 1); 3. Prove that the argument is also true for n = k + 1.
Prove by induction is useful for many proofs in discrete math. For instance:
The exclusion-inclusion formula
Spin-off: the inclusion-exclusion formula can be used to derive many other useful formula. For example:
Surjections numbers can also be used to find the Stirling numbers (divide by m! to remove the sequence!)
Another example is the derangement numbers:
Bijection between labelled trees & prufer code
Recurrence
Many real world problems can be modelled in the form of recurrence (You must recall the Fibonacci sequence and many other classical examples from CS101). In this section, the most important takeaways are the advancement operator and solving recurrences.
Graphs
Graph theory is perhaps the most fascinating part of discrete math: coloring problems, trees, eulerian and Hamiltonian graphs, and many more … Graph theory have important usages in the design of algorithms. It is also an comprehensive exercise of the proof methods, i.e., proof by contradiction and proof by induction (As you have seen in the previous example).
Epilogue
Just as I mentioned in the beginning, it is impossible to cover all topics of discrete math in this piece of log. But I do hope that it gives you some idea about this intriguing subject. For me, writing this log do make the tedious preparations for the final more enjoyable!
One last remark: discrete math is like a magical tool box. I will definitely come back to it when taking algorithm courses! (Maybe also for GNNs?)
发表回复