## 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** in BUCH A202 .

### 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] [Solutions]
- Homework 4, Due March 15, 2018. [LaTeX source] [Solutions]
- Homework 5, Due March 29, 2018. [LaTeX source] [Solutions]
- Homework 6, not to be handed in. [LaTeX source][Solutions]

### Announcements

March 25: Homework 5 has been updated. In problem 2b, we have F_{2}= 1, not F

_{2}= 2. To compensate for this, F

_{n}has been replaced by F

_{n+1}. I will instruct the grader to be lenient when grading this problem; if you already solved the problem using the previous definitions, no points will be deducted.

March 12: Homework 4 has been updated. The definition of an algebraic number in problem 5 has been clarified---P(x) is algebraic if it is the root of a

*nonzero*polynomial with integer coefficients.

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

Feb 20 & 22: Reading week

Feb 27: Midterm

Mar 1: Equivalence relations, partition function

Mar 6: Conjugacy classes of S

_{n}, cycle structure

Mar 8: Euler's Pentagonal number theorem

Mar 13: Recurrence relation for the partition function

Mar 15: Young tableau, hook-length formula

Mar 20: Extremal set theory, Erdős-Ko-Rado theorem

Mar 22: Erdős-Ko-Rado theorem cont'd, Sperner's theorem

Mar 27: Sperner's theorem cont'd, SDRs, Hall's marriage theorem

Mar 29: Hall's marriage theorem cont'd

Apr 3: deBruijn-Erdős theorem

Apr 5: deBruijn-Erdős theorem cont'd