Skip navigation

MATH 341: Introduction to Discrete Mathematics,

Spring term, 2018.

Instructor: Joshua Zahl.
Where and when : Tue Thu 12:30-14:00, in LASR 102.
My office: Math 117.
e-mail: jzahl@math.ubc.ca
Office hours: Tue 14:00-15:00, Wed 11:00-12:00, Thu 15:00-16:00
TA office hours: Wed 13:00-14:00, MATHX 1118

Text: We will loosely follow Discrete Mathematics - Elementary and Beyond by Lovász, Pelikán, and Vesztergombi. This book can be freely downloaded from Springer via the UBC library. Physical copies can also be purchased at the UBC book store. We will also use the secondary texts Combinatorics : topics, techniques, algorithms by Cameron, which is on reserve at the UBC library, and the book Generatingfunctionology by Wilf, which can be freely downloaded here.


Course Description

This course will introduce students to many of the structures in discrete mathematics and common approaches used to study them. This is a proof based course, with emphasis on both theory and applications. Course material for the first half will mostly be taken from the text Discrete Mathematics - Elementary and Beyond .

Grading policy

The course mark will be based on biweekly homework assignments (20%), one midterm (30%), and a final exam (50%).


There will be biweekly homework assignments, which are due Thursday at the beginning of class. The lowest homework score will be dropped.

There will be one in-class midterm. It will be held on Tuesday, February 27th. Please make sure you do not make travel plans, work plans, etc., without regard to the examination schedule in this class. There will be no make-up or alternate exams. If you miss the midterm, your score will be recorded as 0, unless you have a serious documented reason (an illness, a death in the family, etc.), in which case you should discuss your circumstances with the instructor as soon as possible, and in advance of the test.

The final exam will be on Monday, April 16 at 3:30pm.

Homework

Announcements

Jan 31: Homework 2 has been updated. Problem 2 was a bit difficult, so I've made it a bonus problem (it is now possible to receive over 100 % on the homework), and provided some hints

Jan 31: Here is a note defining the sign of a permutation. This will be useful for problems 4-8 of HW2.

Jan 30: Homework 2 has been updated. In problem 3, "there an integer t so that..." has been replaced by "there is a positive integer t so that...." This removes the issue that t = 0 trivially always works.

Jan 23: The TA's office hours have moved from MATHX 1101 to MATHX 1118.

Jan 13: Homework 1 has been updated. In problem 5, "for every nonnegative integer n" has been replaced by the requirement "for every positive integer n." This removes the issue that (n-1) choose (k-1) might not be defined.

(Approximate) Course outline

Here I will post short summaries of each class as we go along.

Jan 4: sets, power sets

Jan 9: binomial coefficients, binomial theorem

Jan 11: lattice model of a gas, entropy, growth rate of n!

Jan 16: Stirling's approximation, entropy of a gas, Pascal's triangle

Jan 18: inclusion-exclusion principle

Jan 23: derangements, permutations

Jan 25: permutations cont'd: two-line and cycle notation, groups

Jan 30: permutations cont'd: decomposition into disjoint cycles

Feb 1: permutations cont'd: transposition, sign of a permutation

Feb 6: Recurrence relations and generating functions, Fibonacci numbers

Feb 8: Generating functions cont'd, Stirling numbers

Feb 13: linear recurrences, Catalan numbers

Feb 15: Catalan numbers cont'd