Instructor: |
Monty (or William)
McGovern
Office: Padelford C-450 Phone: 206-543-1149 Email: mcgovern@math.washington.edu Office Hours: MW 1:30, or by appointment; grader office hour Th 10:30 or by appointment, Padelford C-450 |
Lectures: |
Monday, Wednesday & Friday, 9:30-10:20 a.m., Smith Hall 305 |
Required Text: |
Introductory Combinatorics, by Brualdi, (4th ed., Prentice Hall, 2004). |
Prerequisites: |
Math 308 or the equivalent. |
Grading: |
Your grade will be based on weekly homework, two midterms, and a final exam, each accounting for 1/3 of the final grade. The midterms will be given on October 17 and November 14; the final exam will be given on Wednesday, December 10, at 8:30 a.m., and will be comprehensive. If you cannot complete a homework assignment on time, you can always turn it in by 4:00 on the day it is due to the grader's (Kurt Luoto's) mailbox. PLEASE turn in WHATEVER YOU CAN rather than nothing. I encourage you to work on homework in groups, though each assignment must be written up individually. In the midterms and final you may use two letter-sized pages (one sheet front and back of notes in your own handwriting). |
Incompletes and Drops: |
The grade of Incomplete will be given ONLY if a student has been doing satisfactory work until the end of the quarter and then misses the final exam for a documented illness, religious reason, or family emergency. |
What to Expect: |
I will begin by reviewing mathematical induction and the pigeonhole principle, two basic techniques to be used throughout the course. Then I will apply these techniques and others to study enumeration, existence, and extremal problems (the "three Es" of combinatorics). More precisely, I will cover most of Chapters 2 through 8 in Brualdi and some topics from Chapter 9. |
Due: | Problems: |
Sep 26 |
show that the sum of the cubes of the first n natural
numbers is the SQUARE of the sum of these numbers. |
Oct 3 |
p. 40 #7,10,13 (counts double),16, a board problem given in
class: read Chapter 2, 3.1--3.3 |
Oct 10 |
section 3.6 #4,7,9,18,28: finish Chapter 3 and start Chapter 4 |
Oct 17
|
study problems, midterm: section 3.6 #22,50; section 4.6
#8,19,20; finish Chapter 4
|
Oct 24 |
4.6 #7,8; 5.8 #11,12,33 [case of even n only; for extra credit,
do odd n]: read Chapter 5
|
Oct 31 |
5.8 #19; 6.7 #1,14,16,31: read 6.1-6.4 |
Nov 7 |
6.7 #9,24; 7.8 #1,5,8: read 6.5,7.1-7.3 |
Nov 14
|
study problems: 6.7 #11,32[correction: ALL squares EXCEPT
(1,1),(2,2)..,(n,1) are forbidden]; 7.8 #32,34,35: read 7.4,7.5 |
Nov 21
|
7.8 #35,45; 8.6 #1,2,34 [correction to #34: Catalan number C_n,
NOT large Schroder number R_n]: finish Chapter 7, read 8.1-8.3 |
Dec 5
|
turn in problems from missing HW assignments: read 8.5,8.6 (omit
8.4), start Chapter 9 |