Instructor: Dr. Yupeng Li yupengli@msu.edu
Lectures: Mon, Wed, Fri 10:20 - 11:10am, Wells Hall A236
Office Hours: Thu 11:00am - 1:00pm, Wells Hall C308
Textbook: Harris, Hirst, Mossinghoff, Combinatorics and graph theory, 2nd ed, free from Springer. We will first cover Chapter 2, then selections from Chapter 1. We will follow the textbook fairly closely.
Course Diary
----------------------------------------------------------------------------------------------------------------------
8/31 Intro + Section 2.1
9/2 Section 2.1 continued
9/4 Section 2.1 continued, Stars and bars, multi-set choose
----------------------------------------------------------------------------------------------------------------------
9/7 No class!
9/9 HW1 due today at 11:59pm!
9/11
Homework
HW1(due 9/9): Section 2.1: 2, 11, 12,
You have 5 white balls ◦ and 3 black balls •, which you lay out in a row.
How many different arrangements are possible? Example: ◦ ◦ • ◦ • • ◦ ◦
How many arrangments with no two black balls next to each other? Example: • ◦ ◦ • ◦ • ◦ ◦
Multinomial coefficients:
A class has 20 students. How many ways to split the class into four teams of 5 each (teams A,B,C,D)?
How many ways to choose just an A team and a B team from the class (with 5 each, no overlap)?
Count the anagrams (rearrangements) of the word MISSISSIPPI. Example: SPSPSSIIMII.
Given fifteen people chosen at random, what is the probability that none of them have the same birthday out of 365 days in the year (assuming all birthdays equally likely, and ignoring leap year)?
Count the number of nonnegative integer solutions to the equation: x + y + z + u + v = 15. Example: x = y = 0, z = 3, u = v = 6 is a positive integer solution to the equation.
What happens if we change the "nonnegative" to "positive" in the previous question?
How many four-digit numbers are there with increasing (but not necessarily distinct) digits? Example: 2556.
Course Information
GOALS: This is a problem-based course on combinatorial theory. Students will learn to solve problems about enumeration, binomial coefficients, generating functions, recurrences, counting with symmmetry, graphs, trees, planar graphs, and graph coloring. Students will also practice writing proofs in weekly assigned homework.
ATTENDANCE: I expect students to attend all lectures, unless you have a documented reason and you make prior arrangements with me.
GRADES: Homework 10%, 2 Midterm exams 25% each, Final exam 40%.
Tentative Grade Scale: ≥90% = 4.0, ≥85% = 3.5, ≥80% = 3.0, ≥75% = 2.5, ≥70% = 2.0, ≥60% = 1.0.
WEEKLY HOMEWORK: Weekly problem sets will be assigned. You are expected to solve all the problems, but you should submit solutions to only five problems from each set. Each submission will be graded for completion, and one of the five submitted problems will be selected at random and graded for correctness. Homework must be submitted through D2L by 11:59 p.m. every Monday. If Monday is a holiday, homework will be due on Wednesday.
Although large language models (LLMs) can readily solve all the homework problems in this course, working through the problem sets yourself is essential to your learning and success. Exam problems will be difficult, if not impossible, unless you have personally worked through, not merely read solutions to, the corresponding homework problems. Every problem you give up on is a lost opportunity to learn, so consult a solution only after making a sustained and serious effort. If you find that you need solutions for most of the problems, please arrange to meet with me for help. You cannot learn mathematics merely by watching "someone else" do it, any more than you can learn to play a sport by watching others: you must practice it yourself.
MIDTERM EXAMS: We will have two in-class exams.
Exam 1: Oct 14
Exam 2: Dec 7
FINAL EXAM: 7:45 - 9:45am Dec 18
ACCESSIBILITY: Let me know if you have any difficulty using any of the course materials, and we will arrange a work-around.