Math 536 - Combinatorics II

Math 536 - Combinatorics II - Spring 2007

Professor: Ron Gould

Text: Combinatorics - Topics, Techniques, Algorithms by Peter J. Cameron, Cambridge Univ. Press, 1994 and other supplied materials.

Office: E432 Math and Science Center Office Hours: 10:00-10:40AM MWF or by appointment
Office Phone: 404-727-7924 email: rg@mathcs.emory.edu

Combinatorics Hall of Fame: (2nd semester)

Ramsey

Polya

Hamming

Reading Assignments:
- Chapter 9
- Chapter 10 + handouts
- Chapter 15
- Chapter 16
- Chapter 17

Written Assignments:
(Usually due one week after chapter materials are completed in class.)
Assignment 1: In Chapter 9, Problems # 3, 6, 7, 8, 9

Assignment 2: Chapter 10 (pages 156-157) problems #1, 4, 6, 7a. Also the following problems:

Q1 (a) Show that in any 2-coloring of the edges of the complete graph on 6 vertices, there are at least two monochromatic triangles.
(b) Show that in any 2-coloring of the edges of a complete graph on 7 vertices, there are at least 4 monochromatic triangles.

Q2 A student has 37 days to prepare for an exam. She knows she will require no more than 60 hours of study. She wishes to study at least 1 hour per day. Show that no matter how she schedules her study time (in an integer number of hours per day), there is a succession of days during which she will have studied exactly 13 hours.

Q3 Prove that no matter how the integers 1, 2, ..., 12 are positioned around a circle, some set of three consecutive integers sums to at least 19.

Assignment 3: Chapter 15, Problems 1, 2, 5. (Note in 5b - this means find all nonisomrphic graphs on 4 vertices.)

Q1 Find the number of distinct bracelets of 5 beads made from yellow, blue and white beads. Two bracelets are indistinguishable if the rotation of one will yield another (no flips allowed).

Q2 The six faces of a cube are to be painted with 6 different colors, each face with a distinct color. In how many ways can this be done?

Q3 A benzine ring is a ring of six carbon atoms at the vertices of a hexagon. Different organic compounds may be made by attaching another group of atoms (a radical) to each of these six carbon atoms. How many different compounds can be made by attaching one H, CH3 or OH radical at each vertex. Assume all C-C bonds are equivalent and that the rings may be turned over (flipped).

Q4 Redo problems Q1 and Q3 using pattern inventories.

Assignment 4: From Chapter 16, Problems: 1, 3, 7, 8, 10, 11, 12

Assignment 5: Chapter 17, Problems: 1, 7, 8 Along with class assigned problems.

Professor: Ron Gould

Reading Assignments:

Written Assignments: