Combinatorics: Math 453-001, Spring 2008

Instructor: Michael Pelsmajer
[Departmental webpage] [Personal webpage]

Email the whole class:

Generic syllabus (Jan.'06)
Spring 2008 course information



Try something! But back off if it isn't working out. Repeat. (There may be no super-nice solution, so an idea might have to be pushed a bit before it works out.) How hard to push an idea before backing off? Experience helps (so do many problems). Discussion helps (possibly an internal dialogue if you're alone).


Perhaps you wish to know about alternative books. Rosen's Intro to Discrete Mathematics overlaps somewhat. Cameron's Combinatorics book is great for certain things. Brualdi and Bogart's Introductory Combinatorics books are standards. And perhaps Schaum's.

Midterm Exam on Thursday, March 6

Final Exam on Tuesday, May 13, 8am-10am

Homework assignments

Due Tuesday, January 29
Section 2.1: Read up through Example 2.3, and do #1,2,4,7,8 (updated 10:47am, 1/23/08)
Section 2.2: do #2,5
Section 2.3: do #5,6
Section 2.6: Read all, and do #3,5,6
Section 2.7: Read all, and do #2,9,11,12,16,17
assigned Thursday by email, corrected & clarified Thursday: [pdf]
(added the necessary multinomial coefficient to my first extra problem, and corrected the bonus problem)
Due Tuesday, Feb 5
Part one [pdf]
Part two [pdf]
(By email, I stated that I would accept Part two on Feb 7.)
Due Tuesday, Feb 12
Part one [pdf] (revised, Feb 6)
Part two: 1. Redo, with clear explanations/proofs, everything that was incorrect or missing on the homework & quiz returned on Thursday. 2. Read p285-289.
Due Tuesday, Feb 19
Read all of Section 5.1, except Example 5.9, and do #2abcdfghil, #3acefghijkln, #5, #9 (assigned Feb 10)
Correct everything without a checkmark on second homework and quiz (assigned Feb 12)
From Section 5.2, do #1afh, 2bc, 5, 6, and
From Section 5.3, do #1bdgijkm, 7, 13, 14, 15, (assigned Feb 16)
Due Tuesday, Feb 26
From Generatingfunctionology: Read Sections 1.1 and 1.2, and from Section 1.7 do #1(all but not e), #3(all but not d), #5ade, #6. (assigned Feb 20, revised #2 to be #3 on Feb 23)
Part two [pdf] (assigned via email Feb 23, critical revision & then posted Feb 26)
Due Tuesday, March 4
From Roberts & Tesman, Section 5.2, do #4abc, 13, 15
From R & T, Read Section 6.4.1 and also (but without agonizing over every detail) 6.4.4, then do #10, 19 (section 6.4 exercises)
(above assigned Feb 26, below assigned Feb 29)
From R & T Section 5.5 do #2abcdefg, 6abhik, and #12-15.
From R & T Section 6.3, do #11, and (as of 4pm, instead of #14) use an OGF to the solve the following recurrence:
ck+2 - 2ck+1 + 4ck = 2k, with c0 = 2, c1 = 1.
And, Catch up on old HW if necessary! Last chance!
Due Tuesday, March 25
and talk to me about Project ideas if you haven't already
(assigned Mar 11 & 14)
Due Tuesday, April 1
From Roberts & Tesman:
Read the beginning of 8.1, and examples 8.2 & 8.5.
From p446, do #1bdefhij, 4, 6, 7, 8, 18, 19. (For the purpose of these exercises, to describe an equivalence class it suffices to give one of its members, and say what size it is.)
From p454, do #2ac, 3.
(A1) Find every set of exactly 2 permutations of [3] that forms a group.
(A2) Find every set of exactly 3 permutations of [3] that forms a group.
(A3) Find every other set of permutations of [3] that forms a group.
(A4) Find every set of exactly 2 permutations of [4] that forms a group.
(By way of comparison: "X" in #3, p455 is a set of exactly 2 permutations of [3] that forms a group. The set of rotations of a 4-bead closed necklace from the lecture is a set of exactly 4 permutations of [4] that forms a group.)
(not much of a) Hint for (A): We don't have any nice technique for these problems. Just the definition of "permutation group", and the knowledge that only G1 and G3 really matter.
(above assigned Tuesday, March 25)
From Roberts & Tesman, p455, do #8, 9, 10, 14, 19.
From Roberts & Tesman, p460, do #4, 5.
(B) Count the number of k-bead, red/blue, open necklaces (see Example 8.2, p441), using Burnside's Lemma.
(C) Redo #18, p448, using Burnside's Lemma this time.
(above assigned Tuesday, March 27)
Due Tuesday, April 8
Optional: Read p472-473 (from R & T), regarding the new notation for cycles of a permutation.
From (R & T) 8.5, do #1.
(A) Find the OGF for distinct 3-colorings of vertices of a square, up to symmetry (not just rotation, but all symmetries), using the Polya-Redfield theorem.
(B1) Find the OGF for distinct 3-colorings of vertices of the tetrahedron (see p443-444), in terms of the colors, using the Polya-Redfield theorem. Do not simplify the expression.
(B2) Using part (B1), find the number of distinct 3-colorings of vertices of the tetrahedron.
(above assigned Wednesday, April 2)
From Section 8.5 (R & T), do #22, 23.
(C) We seat 100 people around a huge round table. Each person is a clone: of Ann, or of Bob. How many distinct seating arrangements are there?
(!) Take note of the project deadlines, and act appropriately. (See below)
(above assigned Thursday, April 3)
Due Tuesday, April 15
Do each of the following problems using Orbit-counting and/or Polya-Redfield. You needn't simplify any of your answers.
(A) Count the number of closed necklaces with red or blue beads, up to symmetry. (Unlike the 100-person table above, you can turn a necklace upside down.)
(B) Find the generating function for 5-vertex graphs, in terms of the number of edges, which we consider isomorphic graphs to be the same. [BONUS: How would this change if we allowed up to k edges between each pair of vertices?]
(C) Find the number of different cubes where the faces are each given one of k colors.
(D) Consider the 12-vertex, 20-edge, 10-face object you get by gluing two cubes together. Find Orb(b,w,g), where the faces are each colored black, white, or green.
(E) Express the following in terms of "Orb(b,w,g)" you just found: How many of the colorings in part (D) have at least one green face and at least one black face? (Hint: Warm up by finding the total number of colorings first, then by finding the number of colorings with at least one green face.)
(above assigned Thursday, April 17)
Due Tuesday, April 29
Read examples 9.13, 9.14 from p527-528
From section 9.4, do #2, 3, 4, 5, 10b, 45, 47.
(above assigned Friday, April 25)
Due Tuesday, May 6
From Section 9.5, do #1, 3, 4, 5, 8ab, 18, 19. (Notes: Doing all of #18 is challenging. You can do #19 even if you don't do #18.)
(above assigned Tuesday, April 29)
Bonus/Optional: From Section 9.5, do #20.
(above assigned Thursday, May 1)
Comments on midterm & homeworks: [PDF]
Project Presentations May 6, May 8
Comments on final exam: [PDF]


Some guidelines: Spring 2008 course information

Monday April 7 - Wednesday April 16 Project proposal (20% of your Project Grade), including:

Step 1: Make an appointment with me: Allow an hour for the meeting. Email me ASAP. (updated April 3)

Project ideas: