Combinatorics: Math 453-001, Spring 2008

Email the whole class: MATH45300101S_AT_alpha1_DOT_ais.iit.edu

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

Advice/Tips

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

Etc.

1/22/08

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:

c_k+2 - 2c_k+1 + 4c_k = 2^k, with c₀ = 2, c₁ = 1.

And, Catch up on old HW if necessary! Last chance!

Due Tuesday, March 25

[pdf]

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]

Projects

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

• Written outline of what your project will cover. You should be able to discuss every item in the outline briefly, intelligently.
• You should have worked through some of your material in more detail - the only reason for not getting very far is if you're stuck on something substantial. (If I can clear up the trouble in a minute, then it's not substantial; in which case, you should have seen me earlier to get unstuck.)
• A 10-15 minute presentation, at the board. Introduce the topic, giving necesary definitions, etc., go through at least one substantial example or proof. Be prepared to discuss more material than that, and expect that I'm going to ask a lot of questions.

Project ideas:

• Voting Theory (& Game Theory): start by reading parts of Roberts & Tesman, then perhaps Saari's "Chaotic Elections"
• Snake Oil & WI asked for something, but I forgot what.Z method: everything you need is in Wilf's Generatingfunctionology
• Probabilistic method (other arguments similar to a certain argument we saw for the lower bound of the Ramsey number R(n,n) )
• Analytic Methods for generating functions (Chapter 5 of Wilf; must know some Complex Analysis and be willing to learn more as needed)
• Number Theoretic Generating Functions: Start w/chapter 2 of Wilf, Dirichlet series
• Certain experimental designs called (t,m,s)-nets (which somehow resemble the structure of a completed Sudoku puzzle) (See [this].) It is less obvious how you can start this without my help, at this point.
• Selfish Routing and the Price of Anarchy
• You come up with some idea... but here it is even more critical that we discuss your plans, and that I approve it well in advance.