## Introduction to Combinatorics

#### Fall 2005 Math 413 Sections F13/F14

Announcements:
(Dec 19) I have finished grading the final exams. The average was 164 points out of 200. I have computed the final grades and posted them to Banner. Please email me if you want to know your grade directly or would like to see your final exam. Thanks for a great class, and enjoy the winter break!

Course Materials:
Course outline and course log recording topics covered in each lecture.
Textbook: Introductory Combinatorics by Richard A. Brualdi, Pearson Prentice Hall, fourth edition, 2004. (errata for the 4th edition)

Homework (for students registered for 3 credits, do 4 out of the 5 problems):
 #1: Sec 1.8: 26, 27, 29, 32, 35; due Wed Aug 31 (solutions) #2: Sec 1.8: 8; Sec 2.4: 5, 8, 14, 15; due Wed Sep 7 (solutions) #3: Sec 2.4: 19; Sec 3.6: 7, 11, 27, 28; due Wed Sep 14 (solutions) #4: Sec 3.6: 38, 45; Sec 5.8: 12, 15, 16 (use any technique); due Wed Sep 21 (solutions) #5: Sec 5.8: 20, 27 (correction), 30, 31, 50; due Fri Sep 30 (solutions) #6: Sec 5.8: 47, 48; Sec 6.7: 3, 6, 8; due Wed Oct 5 (solutions) #7: Sec 6.7: 13, 21, 24(a), 29; Sec 7.8: 1(b,c); due Wed Oct 12 (solutions) #8: Sec 7.8: 1(d), 4, 14, 19(b,d,e), 25; due Wed Oct 19 (solutions) #9: Sec 7.8: 25 (using gen funcs), 28(b,c,e), 29(b,d,e), 30(c,d), 38; due Wed Oct 26 (solutions) #10: Sec 7.8: 42(b,c); Sec 8.6: 1, 2; additional exercises; due Wed Nov 2 (solutions) #11: Sec 8.6: 6, 7, 8, 12(b,d), 13; due Wed Nov 9 (solutions) #12: Sec 8.6: 19, 20, 27; additional exercises; due Wed Nov 16 (solutions) #13: Sec 10.5: 14&15(i,ii,iii), 20, 24, 28; additional exercise; due Wed Dec 7 (solutions) suggested: Sec 10.5: 32, 34, 36, 42, 47; not to be submitted

Homework (for students registered for 4 credits):
 homework 1; due Fri Sep 30 (solutions: 1,6; 2,5; 3,8; 4; 7) homework 2; due Fri Oct 28 (solutions: 1,7; 2,5; 3,8; 4,6) homework 3; due Fri Dec 2 (solutions: 1,6; 2,8; 3,5; 4,7)

Other Materials:
 Test 1 solutions Test 2 solutions Test 3 solutions Informal early feedback summary

Instructor:
Stephen Hartke, hartke @ math . No . Spam . uíuc . edu (appropriately changed)
Office: Illini Hall Room 227A, Phone: 217-265-6760
Office Hours: MW 3:00-3:50pm or by appointment.
Meeting Times:
Mon, Wed, and Fri, 2:00pm-2:50pm, Altgeld Hall Room 141
Tests:
Fri Sep 23, Fri Oct 21, Fri Nov 18 in class.
Final Exam:
Fri, Dec 16, 1:30pm-4:30pm, Altgeld Hall Room 141

Alexandr Kostochka taught Math 413 in the spring.
Bruce Reznick taught Math 313 (the old course number) in spring 2004.
Vince Vatter taught combinatorics at Rutgers University in summer 2005.

Old Announcements:
(Dec 12) As I announced in class, I will have the formulas and other information from Test 3 and Quiz 10 available on the final exam. No one requested any additional information, so this sheet is the version that will appear on the final.
(Dec 9) I will not be holding regular office hours next week. If you wish to discuss something, please email me and we will arrange a time to meet.
(Dec 5) The final exam is Fri, Dec 16, 1:30pm-4:30pm, in Altgeld Hall Room 141. The exam is cumulative, covering material from the entire semester, but with an emphasis on material covered after the third test. The format will be similar to the tests. (Nov 16) There will be no homework due on Wednesday, Nov 30. There will be one more homework in the semester, due on Wednesday, Dec 7.
(Nov 11) The third test will be in class on Friday, Nov 18. The format will be the same as the previous tests. The material covered will be up through today's lecture (partition numbers and combinatorial proofs). There will be no quiz next week, but the homework is due on Wed, Nov 16.
(Nov 14) A change of problem #3 on Homework #12:
Write down the generating function for the number of ways that k colored dice can sum to n.
Write down the generating function for the number of ways that any number of indistinguishable dice can sum to n.
For k=3 and n=10, determine exactly the number of ways that:
3 colored dice can sum to 10.
3 indistinguishable dice can sum to 10.
(it's probably easiest to not use the generating functions for this)
If you've already done the current (harder) form of the problem, that's fine--you can submit that solution. Just make sure that it's clearly stated.

(Oct 14) The second test will be in class on Friday, Oct 21. The format will be the same as the first test. The material covered will be up through today's lecture (section 7.5 on solving recurrences with generating functions). There will be no quiz next week, but the homework is due on Wed, Oct 19.
(Sep 26) Homework 5 is due on Friday, Sep 30. We will also have the quiz this week on Friday, not Wednesday.
Here are the Test #1 solutions. The average grade was 70; the median was 72.
Thanks to everyone for filling out the informal early feedback form. Here is a summary of the results.
(Sep 22) There is an error in the textbook for problem 5.8.27: the 1/2 should not appear on the right side of the equation. A corrected version of the problem appears below.
(Sep 16) The first test will be in class on Friday, Sep 23. The test will be closed-book and closed-notes, with problems similar in difficulty to the homework and quizzes. The material covered will be up through today's lecture (section 5.3 on identities). There will be no quiz next week, but the homework is due on Wed, Sep 21.
(Sep 13) By the poll taken in class on Monday, quizzes will remain on Wednesdays.
(Sep 12) For problem 3.6.7 on homework #3, assume that aces are only high. In other words, a deck of card consists of 52 cards divided among 4 suits (2 of which are red and 2 of which are black), and 13 ranks. If you've already done the problem assuming that aces can be either low or high, that's fine, but clearly state this assumption in your solution.
(Aug 17) Assignment of instructor to this class.
(Jul 29) Initial assignment of instructor to another class.