21228 Discrete mathematics
The course meets 3:30-4:20 MWF in Hamerschlag Hall B103.
My office hours will be
2:00-3:20 MWF or by appointment, please send email to
jcumming@andrew.cmu.edu to arrange an appointment.
Homework will be set most Wednesdays, will be due in class on the following Wednesday
and will be returned to you in recitation on the Tuesday after that.
Late homework will not be accepted under any circumstances, but the two lowest
homework scores will be dropped. You may collaborate on the homework, but
must write up solutions by yourself.
The TAs for the course are Barbara Anthony (recitation meets
3:30-4:20 T in Scaife Hall 220, office hours are 3:30-5:00 Th in Wean Hall 6207)
and Mike Picollelli (recitations meet 1:30-2:20 T in Porter Hall A22
and 2:30-3:20 T in Scaife Hall 220, office hours are 1:00-3:00 Th in Wean Hall 7213). Questions about grading should be referred to the TAs in the first instance,
come and see me if you do not get satisfaction from them.
Prerequisites: You should know basic calculus and be comfortable with sets, functions and
the idea of proof by induction.
Text: There is no text for this course. We will be using a
set of notes
prepared by Prof Alan Frieze. As the course goes on I will add some supplementary
notes. I will also try to create an online record of exactly what material
we have covered in each class session.
Syllabus: Discrete mathematics (or finite combinatorics as it is sometimes called)
is the study of finite structures. It is an essential part of pure mathematics and
has also found applications in areas as diverse as economics, biology, and computer
science. In this course we will focus on finite sets,
partially ordered sets (posets) and graphs.
The most basic property of a finite set is the number of its elements. We will
study many methods for counting the elements of finite sets either exactly or
approximately. Methods we will look at include
recurrence relations, generating functions, inclusion-exclusion
and the probabilistic method.
We will also look at some more subtle structural questions about finite structures,
for example how large an antichain can we expect to find in a partially ordered
set? We will make an intense study of the properties of finite graphs
including planarity, colourability, and the existence of Eulerian and
Hamiltonian cycles.
There will be a midterm and a final. Grades will be assigned according to a formula
in which homework counts 30 percent, the midterm counts 25 percent
and the final counts 45 percent.
- Homework set 1 in PostScript and
PDF.
- Homework set 2 in PostScript and
PDF.
- Homework set 3 in PostScript and
PDF.
- Homework set 4 in PostScript and
PDF.
- Homework set 5 in PostScript and
PDF.
- Midterm in PostScript and
PDF.
- Homework set 7 in PostScript and
PDF.
- Homework set 9 in PostScript and
PDF.
- Final in PostScript and
PDF.
- Homework set 1 solutions in PostScript and
PDF.
- Homework set 2 solutions in PostScript and
PDF.
- Homework set 3 solutions in PostScript and
PDF.
- Watch this space
- Homework set 5 solutions in PostScript and
PDF.
- Homework set 7 solutions in PostScript and
PDF.
- Homework set 8 solutions in PostScript and
PDF.
- Homework set 9 solutions in PostScript and
PDF.
- Administrivia. There are n! ways of forming an ordered list from an n-element set.
Using calculus to get upper and lower bounds for ln(n!). Statement of Stirling's
formula (2 Pi n)^(1/2) (n/e)^n giving an approximate value for n!
- Definitions of "f is O(g)" and "f ~ g". If f ~ g then f is O(g) and g is O(f).
Stirling's formula actually says that n! ~ (2 Pi n)^(1/2) (n/e)^n.
The binomial coefficient n-choose-k, formula for n-choose-k in terms
of factorials, the binomial theorem. Problem: how many solutions
of x_1 + .... x_n = k in natural numbers? Certainly at most
(k+1)^n
- Counting the number of solutions to x_1 + ..... x_n = k.
Approach one: write down a recursion equation.
Approach two: set up a bijection with the set of strings
containing k 1's and n-1 0's. Approach three: consider the
coefficient of x^k in (1 -x)^(-n)
- Finding the coefficient of x^k in (1 - x)^(-n). Take the
equation 1/(1-x) = 1 + x + x^2 + ...... and differentiate
n-1 times. Recurrence relations: to solve
a_{n+2} = A a_{n+1} + B a_n we consider the quadratic
lambda^2 = A lambda + B. if it has distinct real roots lambda_1
and lambda_2 then the general solution is A_1 lambda_1^n + A_2 lambda_2^n
and we can solve for A_1, A_2 if we know a_0 and a_1.
Life is harder when there is a repeated root or
a pair of complex roots (see HW 2).
- Counting paths in the "integer lattice" (set of points with
integer coordinates). In a path we move one unit up or one unit to the right at
each step. The number of paths from (0, 0) to (a, b)
is (a+b)-choose-a. Exploiting translation symmetry: the number of
paths from (a, b) to (c, d) = number of paths from (0, 0) to (c -a, d - b).
Given b > a, how many paths from (0, 0) to (a, b) which stay strictly above the diagonal?
All such paths go through (0,1), so the answer is
total number of paths from (0, 1) to (a, b) MINUS number of such paths
which meet the diagonal
- For b > a, any path from (1, 0) to (a, b) meets diagonal. Use this to set up
a bijection between paths from (0, 1) to (a, b) which meet the diagonal
and path from (1, 0) to (a, b), using reflection symmetry.
Conclusion: number of paths from (0, 0) to (a, b) which stay strictly above the diagonal
is (a + b -1)-choose-(b-1) - (a + b-1)-choose-(a-1), which can be rearranged
as (b-a)/(b+a) times (b+a)-choose-a. Next problem: for b >= a, how many paths
from (0, 0) to (a, b) not going below diagonal? Shifting up by one,
this is number of paths from (0, 1) to (a, b+1) staying above diagonal,
that is (b-a+1)/(b+a+1) times (a + b +1)-choose-a.
- Special case of last time: number of paths from (0,0) to (n, n) which do
not go below the diagonal is 1/(n+1) times 2n-choose-n, an important quantity
called the nth Catalan number (see HW3). New topic: probability.
A finite probability space is a nonempty finite set X plus a function P which
assigns a probability to each element: probabilities are non-negative and sum to one.
An event is a subset of a probablility space, an outcome is an element of
a probability space. Examples: tossing a fair or biased coin one or several times.
Key fact: if we toss n times a biased coin with probability of a H being p, then
probability of seeing a H's is n-choose-a times p^a times (1-p)^(n-a) ... this
is a term in the binomial expansion of (p + (1-p))^n. An example
of an infinite probability space: toss a fair coin and wait till you see a
tail, P(you make n tosses) = 2^{-n}.
- Probabilistic arguments: to show there is an X with property Phi,
design an experiment which produces a random X somehow and
argue that P(the X resulting from the experiment has Phi) > 0.
Example: given n sets of size k where 2^{k-1} > n, we may colour
their elements in two colours so that each set contains points of
both colours. To see this look at a random colouring, argue that for
each set the probability that it is monochrome is 1/2^{k-1}, so
probability *all* sets are monochrome is at most n/2^{k-1}.
- A random variable is a function on a probability space. Expectation value
of a random variable. Expectation is linear. Variance of a random variable.
Proof of the Markov and Chebycheff inequalities.
- Proof of a recurrence for the Catalan number C_n. Look at paths
from (0,0) to (n, n) not going below the diagonal, and break them
at the largest i < n where they touch the diagonal. Then argue there
are C_i possibilities for the part up to (i, i) and C_{n-i-1}
possibilities for the remaining part. Conclusion is that
C_n = the sum for i from 0 to n-1 of C_i times C_{n - i -1}. With
C_0 = 1 this determines the C_n. More probability: computing the
expectation and variance of a variable with the binomial distribution
by cheesy algebraic tricks.