MATH 341 Introduction to Discrete Mathematics

Introduction to ideas and methods of discrete mathematics and their application.

This course is eligible for Credit/D/Fail grading. To determine whether you can take this course for Credit/D/Fail grading, visit the Credit/D/Fail website. You must register in the course before you can select the Credit/D/Fail grading option.
Credits: 3

Pre-reqs: One of MATH 220, MATH 223, MATH 226, CPSC 121.

Office Hours

Place: MATH building, office 220.

Final

Dec 13, 12:00 pm, BUCH A202
For questions regarding the material we have learned, or related to HW problems you are encouraged to visit the Math Learning Centre (MLC) on weekdays 11:00 am to 5:00 pm.

Text

We will loosely follow Discrete Mathematics - Elementary and Beyond by Lovasz, Pelikan, and Vesztergombi. This book can be freely downloaded from Springer via the UBC library (link). 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. Follow the first two chapters of Jukna's book to practice counting methods we used in class (link)

https://www.math.upenn.edu/~wilf/DownldGF.html

https://courses.library.ubc.ca/i.cHFWzx

https://courses.library.ubc.ca/i.gJffQq

https://courses.library.ubc.ca/i.dJwNmX

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%), two midterms (30%), and a final exam (50%).

There will be biweekly homework assignments, which are due Thursday. The lowest homework score will be dropped.

There will be two in-class midterms. 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 a 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.

Academic Concession Form

Midterm(s) info

You will write two midterms. The dates are Nov. 5 and Nov 7. As you could guess from the dates, the midterms cover the same topics.
Only your better midterm mark will count (30%). 


Course outline (Plan)

• sets, power sets
• binomial coefficients, binomial theorem
• lattice model of a gas, entropy, growth rate of n!
• Stirling's approximation, Pascal's triangle
• inclusion-exclusion principle
• derangements, permutations
• permutations cont'd: two-line and cycle notation, groups
• permutations cont'd: decomposition into disjoint cycles
• permutations cont'd: transposition, sign of a permutation
• Recurrence relations and generating functions, Fibonacci numbers
• Generating functions cont'd, Stirling numbers
• linear recurrences, Catalan numbers
• Catalan numbers cont'd
• Equivalence relations, partition function
• Sn, cycle structure
• Counting Trees
• Extremal set theory, Sperner's theorem
• Extremal set theory, Erdős-Ko-Rado theorem
• Erdős-Ko-Rado theorem cont'd, Sperner's theorem

Homework  Check Canvas!