• 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. You can also find Exam reviews here!

              Chapter 2 Extra practice for Exam 1 Exam 1 solution

      Chapter 1

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. HW3 due today at 11:59pm!

• 9/23 Section 2.6, Section 2.6.1, Section 2.6.2

• 9/25 Section 2.6.2 continued, Section 2.6.3

----------------------------------------------------------------------------------------------------------------------

• 9/28 Section 2.6.4, Section 2.6.5. HW4 due today at 11:59pm!

• 9/30 Section 2.6.5 continued

• 10/2 Section 2.6.6

----------------------------------------------------------------------------------------------------------------------

• 10/5 Section 2.6.6 continued, Section 2.7.1. HW5 due today at 11:59pm!

• 10/7 Section 2.7.1 continued 

• 10/9 Section 2.7.2

----------------------------------------------------------------------------------------------------------------------

• 10/12 Midterm review No HW due this today

• 10/14 Exam 1 (Section 2.1 - 2.6.6 and Section 2.7.1 will only be Extra Credit problem)

• 10/16 Exam 1 solution, Section 2.7.2

----------------------------------------------------------------------------------------------------------------------

• 10/19

• 10/21 HW6 due today at 11:59pm!

• 10/23

----------------------------------------------------------------------------------------------------------------------

HW3(due 9/21): Textbook problems: Section 2.5: 3, 11, 12, 13

1. 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.

2. 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.

3. How many ways to assign the jobs, with the restriction that P1 cannot do J1 or J2, and P2 cannot do J2 or J3?

4. (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).

5. 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

1. 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?

2. 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.

3. 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.

4. Verify the claim from class: The number of ways to get changes for 10j cents using pennies, nickels and dimes is (j+1)^2.

HW5(due 10/5): Textbook problems: Section 2.6.4: 2, 3, 4, 7, 11, Section 2.6.5: 3, 4, Section 2.6.6: 5, 6

1. Explain the mistakes in each of the following WRONG computations. 

   • ∑k≥0 3kxk   =   3k ∑k≥0 xk  =  3k/(1−x) ??   Hint: Focus on the meaning of "k".

   • 1/(1−3x)  −  1/(1−2x)  =  ∑k≥0 3xk − ∑k≥0 2xk  =  ∑k≥0 (3−2)xk  =  ∑k≥0 xk ?

   • If a0 = 1 and ak = 2ak−1 + 1 for k ≥ 1, then:
       f(x)  =  ∑k≥0 akxk  =  a0 + ∑k≥1 (2ak−1+1)xk  =  1 + 2x ∑k≥1 xk−1 + x ∑k≥1 xk−1  =  1  +   3x/(1−x) ?

2. Solve the following recurrences.

   • Base value a0 = 3, recurrence ak = 2ak−1 − 1 for k ≥ 1.

   • Base value a0 = 3, recurrence ak = 3ak−1 − 2k for k ≥ 1.

3. Consider a sequence (ak)k≥0 defined recursively by:

ak = ak−1 − ak−2   for k ≥ 2.

3. • • Show that for any choice of initial values a0, a1, this sequence repeats itself with period 6; that is, ak = ak−6 for k ≥ 6. Take a0 and a1 as unspecified constants, and compute a2 = a1 − a0, then a3 in terms of a0 and a1, etc.

     • Compute the generating function G(x) = ∑k≥0 akxk in the same way as for Fibonacci numbers.

     • Determine the roots x = α, β of the denominator, x2 − x + 1 = 0. Write these as complex numbers a + bi for a,b real and i = √(−1), and draw them as vectors in the complex plane.

     • Compute α2, α3, . . . using complex multiplication, based on ordinary distributivity combined with i2 = −1. Show that α, β are complex 6th roots of 1, i.e. α6 = β6 = 1, while α2, α4 are cube roots of 1, and α3 is a square root of 1. 

     • Use this to give another proof that ak has period 6. That is, it is possible to expand the generating function in partial fractions:
       G(x)  =  A/(1−x/α) + B/(1−x/β) .
       (This follows from general algebra, without needing to compute the complex numbers A and B.) Now expand the right side to get a formula for ak. Why must it have period 6?

     • Since α, β are roots of the minimal polynomial x2 − x + 1 and of x6 − 1, we must be able to factor
       x6 − 1  =  p(x) (x2−x+1)
       for some polynomial p(x) with integer coefficients. Find this p(x) by long division or another factoring method. In fact, x2 − x + 1 is a cyclotomic polynomial.

     • Clear the denominator of f(x) to get: 

G(x)(x6 − 1)  =  ∑k≥0 akxk (x6 − 1)  =  q(x)

for some polynomial q(x). Multiply out and equate coefficients of xk on each side, and give yet another proof that ak has period 6..

HW6(due 10/21)

• Let w = (156)(243) and v = (14)(25)(36) be two permutations in S6 written in cycle notations. Compute compositions wv and vw. Express them in both two line notations and cycle notations.

• Write down all symmetries of a regular hexagon (there are 12 elements). Pick a rotation and a reflection. Use both two-line notations and cycle notations to represent them as elements in symmetric group S6.

• Burnside's Theorem for the hexagon with G = D6, n = 6 beads of k = 2 colors (Repeat what we did in class for square)

• The rigid symmetries (rotation and reflection) of a regular n-gon form the dihedral group G = Dn. (In class, we looked at D4, the 8 symmetries of a square.) We label the vertices counterclockwise 1,2, . . , n, and consider each symmetry as a permutation of the vertices, meaning Dn ⊂ Sn. For example, the 1⁄n counterclockwise turn ρ1 is the permutation ρ1(i) = i+1 mod n, which in cycle notation is ρ1 = (1,2,3, . . . , n).  In general, let ρi denote the i⁄n counterclockwise rotation, and denote the reflections by τi for i = 1, . . . , n, starting with τ1 having a line of reflection through vertex 1, then turning the line of reflection by 1⁄n for each successive i (if n is odd) and by 1⁄2n (if n is even).

  1. For D4, write each of the 8 symmetries in two-line and cycle notation. 

  2. For Dn, show that ρk = ρ1 ∘ ··· ∘ ρ1 = ρ1k, the result of ρ1 repeated k times. 

  3. For D4, show that the reflections τi are all given by τ1 ∘ ρ1i. 

Note: The above holds for every Dn. Thus all of Dn is generated by repeatedly composing τ = τ1 and ρ = ρ1, and these two elements are generators. The relations ρn = τ2 = ε and ρ τ = τ ρ−1 give another way to compute the multiplication table.

• Organic molecules. The figure below, from HHM p.207, shows the rigid skeleton of a molecule with three carbon atom rings bonded to a nitrogen atom in the middle:
  Number the n = 15 external atoms clockwise from the top. To make a complete organic molecule, each of the 15 atoms must have a hydrogen H or hydroxyl OH attached, which we can consider as k = 2 colors. How many different molecules are possible?
  Here "different" naturally means up to rotation and reflection symmetry in space: two molecules are obviously the same if we can rotate/reflect one to the other. 

  1. Show that the symmetry group G = Sym(X) can have at most 6 elements σ ∈ G. Hint: Consider how σ could move the outermost corners 1,6,11.

  2. Write all 6 symmetries of X in cycle notation. For example, τ1 is a flip (180° rotation) around the central vertical axis in the skeleton, making the permutation τ1 = (1)(2,15)(3,14)(4,13)(5,12)(6,11)(7,10)(8,9).
     Hint: The symmetry group is the same as that of a triangle, but acting on the 15 vertices instead of just 3 corners.

  3. Use Burnside's Theorem to determine the number of different molecules.

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.