## 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

- Homework 1, Due January 25, 2018. [LaTeX source] [Solutions]
- Homework 2, Due February 8, 2018. [LaTeX source] [Solutions]
- Homework 3, Due March 1, 2018. [LaTeX source]

### 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 hintsJan 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