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 notes: You can find the handwritten course notes here! I will update before every class.
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 Section 2.2. HW1 due today at 11:59pm!
9/11 Section 2.2 continued, Section 2.3
----------------------------------------------------------------------------------------------------------------------
9/14 Section 2.5. HW2 due today at 11:59pm!
9/16 Section 2.5 continued (Euler function, derangements)
9/18 Section 2.5 continued, Derangement practice, Solution
----------------------------------------------------------------------------------------------------------------------
9/21 Section 2.6
9/23 Section 2.6, Section 2.6.1, Section 2.6.2
9/25 Section 2.6.2 continued, Section 2.6.3
Homework
HW1(due 9/9): Textbook problems: 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 nonnegative 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.
HW2(due 9/14): Textbook problems: Section 2.2: 2, 3, 5, 7(a), 7(d), 7(e), 10, 11. Section 2.3: 4(a), 4(b),
(Optional, but you should definitely look at this when you prepare for exam. This basically covers everything from Week 1)
A teacher gives an exam to 10 students (Quincy, Rhonda, Sally, Tom, Ursula, Victor, Wanda, Xavier, Ying, Zoltan).
How many ways could the exams be arranged in a stack? Example: top-to-bottom X,S,U,Y,Q,R,T,V,Z,W.
Students are listed alphabetically in the grade book, and each receives a grade of 4,3,2,1, or 0. Example: Q gets 3, R gets 1, S gets 3, etc. How many possible grade lists?
The grade distribution is all the grades written highest-to-lowest. Example: 4,4,4,3,3,2,2,2,2,0. How many possible grade distributions?
The teacher gives a gold star to 3 of the students. Example: R,T,W each get a star. How many ways to distribute stars?
The teacher gives 3 prizes (a pen, a pencil, and a bag of skittles) to three different students. Example: pen to S, pencil to Q, skittles to Y. How many ways to distribute prizes?
Same as previous question, but a given student may receive more than one prize. Example: pen and skittles to U, pencil to V. How many ways to distribute prizes?
6 identical gold rings are to be put on 10 fingers, with at most one ring allowed on each. Determine how many arrangements of rings are possible. Example: 11010 10110, where 1 = a ring, 0 = no ring, and the ten positions correspond to fingers.
Same as previous question, 6 rings on 10 fingers, but with multiple rings allowed on each finger. Example: 03000 01200, where the number indicates how many rings on each finger.
Give a combinatorial proof to the following equality:
((n | k)) = ((n-1 | k)) + ((n | k-1))
where ((n | k)) represents n multi-set choose k introduced on 9/4.
Show that binomial coefficients form a log-concave sequence. Prove for 1 < k < n, we have
HW3(due 9/21): Textbook problems: Section 2.5: 3, 11, 12, 13
Number of orderings of V, W, X, Y, Z such that V is not the first or last, and X is not in the third.
Six different jobs (J1, . . . ,J6) are assigned to 6 people (P1, . . . ,P6), one job to each.
How many ways to assign the jobs? That is, count all possible job rosters.
Impose the restriction that P1 cannot do J1, P2 cannot do J2, and P3 cannot do J3 (but P4,P5,P6 can do any job). How many allowed job rosters?
Hint: PIE with A = {all job rosters} and forbidden sets B1 = {rosters with P1 doing J1}, and similarly B2, B3.
How many ways to assign the jobs, with the restriction that P1 cannot do J1 or J2, and P2 cannot do J3 or J4?
Hint: PIE with A = {all job rosters} and 4 bad sets.
How many ways to assign the jobs, with the restriction that P1 cannot do J1 or J2, and P2 cannot do J2 or J3?
(Similar setup as the example we had in class) Use PIE to solve the following problem: Consider a grid of integer points (x,y) for 0 ≤ x,y ≤ 4, and paths through this grid with steps to the North (x,y) → (x,y+1), or East (x,y) → (x+1,y). Find the number of paths from (0,0) to (4,4) that do not pass through (1,1), (1,3), (3,1), or (3,3).
Jellybeans
A jar has unlimited jellybeans of 4 flavors. How many ways to choose an unordered handful of 18 beans. Example: 10 of the first flavor, 8 of the fourth flavor.
Same, except the jar has only 5 of each flavor. Hint: Use PIE with the bad sets being the handfuls with too many beans of flavor 1,2,3,4.
Count the ways to add 4 numbers between 0 and 5 whose sum is 18, that is a1 + a2 + a3 + a4 = 18, where ai ∈ {0,1,2,3,4,5}. Example: 5 + 3 + 5 + 5 = 18.
Count the ways to roll 4 distinct 6-sided dice with total 22. Example: 6 + 4 + 6 + 6 = 22.
HW4(due 9/28): Textbook problems: Section 2.6: 3, Section 2.6.2: 5, 6, 8, 9
What is the probability of getting 5 heads in 10 tosses of a coin (which lands heads or tails each time)?
Do this problem by the Method of Generating Functions.
Step 0: We want to count the number of ways to get 5 heads in 10 tosses. Generalize into a sequence of problems {ak} by changing a specific number in the original problem to a general k, without changing the basic setup: ak counts the number of ways to get . . .
Step 1: Find the generating function f(x) = ∑k akxk.
Step 2: Expand f(x) using binomial theorem, and explicitly find the coefficient of xk, giving a formula for ak. Can you explain the answer by combinatorial reasoning alone?
Rolling dice. A standard cubical die has faces numbered 1,2, . . . ,6. (Dice is plural, die is singular.)
Let ak be the number of ways to roll a total of k = 2,3, . . . ,12 with two dice. For example, you can roll a 3 as 1+2 or 2+1, so a3 = 2. There is a total of 6×6 = 36 possible rolls, so the probability of k = 3 is 2/36.
Compute a2, . . . , a12 by generating functions.
Sicherman dice are a pair of cubical dice with special number labels instead of the standard 1,2, . . . ,6: one has labels 1,2,2,3,3,4, the other has 1,3,4,5,6,8. Show that the probability of rolling k = 2, . . . ,12 with these dice is the same as the probability for a standard pair.
Do the same for rolls of 3 dice.
Consider a triple deck with three identical copies of 52 distinct cards, similarly to the double deck problem in class. Find the number of distinct 5-card hands from the triple deck.
Verify the claim from class: The number of ways to get changes for 10j cents using pennies, nickels and dimes is (j+1)^2.
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.