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

The office hours are on Wednesdays 3:00 - 4:00 pm. Place: MATH building, office 220.

Note for Sept 18: The office hours will be held in the Math Annex building Room 1101

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 Lovász, Pelikán, 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.

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

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

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

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 at the beginning of class. 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

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
- Conjugacy classes of Sn, cycle structure
- Euler's Pentagonal number theorem
- Recurrence relation for the partition function
- Young tableau, hook-length formula
- Extremal set theory, Erdős-Ko-Rado theorem
- Erdős-Ko-Rado theorem cont'd, Sperner's theorem
- Sperner's theorem cont'd, SDRs, Hall's marriage theorem
- Hall's marriage theorem cont'd
- deBruijn-Erdős theorem
- deBruijn-Erdős theorem cont'd

Hints. For the first set of questions I provide a list of (quite direct hints).

For the next ones please read our course book, and follow our examples in class.

Q. 1. Check exercise 1.2.17. (If the two sides are equal, that's still OK)

Q. 2. Check exercise 1.3.3, and a few lines in the section above.

Q.3. We have solved a harder problem in class. I also mentioned that a simple counting (reducing every set into a part not interseted by others) will do the job.

For questions 4-6 you only need the definition of the binomial coefficient and a little algebra.

For the last few questions use your mathematical intelligence (and/or read Section 1.4)

Piazza

There is a Piazza account assigned to this course. It is up to you if you are using it or not. The course TA will try to follow the discussion.

The link is piazza.com/ubc.ca/winterterm12019/math341

All relevant info will be posted on the course website and on Canvas.

Supporting notes

Distributing $100 among 10 people. The general treatment of such problems is described here.

The nice explanation of this type of counting is given in our course book; Section 3.2 Distributing Presents.

Graphs without a C4 , i.e. cycle of length 4, doesn't have too many (more than n^{3/2}) edges. The details can be fund in Jukna's book.

Cauchy's Inequality. We used a special case, similar to the following: the sum of squares of n numbers is almost at least as large as n times the sqare of the average.

Jensen's inequality. We used it for (x choose 2) beeing a convex function of x.