Math 60610 --- Spring 2009

Discrete Mathematics

Arrangements

• Instructor: David Galvin, dgalvin1@nd.edu
• Meetings: NOTE CHANGE!!! MWF 11:45am-12:35am, room HH 125; first meeting in Hurley 258
• Office hours: W 4-5, F 10.45-11.45
• Text(s):
  • Main text: Combinatorial Mathematics by Douglas West. This book hasn't been published yet; I will distribute photocopies of the first few chapters at the beginning of the semester, and a week or so into the semester I will have copies of the full text to distribute, probably at a cost of about $40.
  • Suplementary texts: A number of books have been put on reserve at the math library; the titles are listed here. Two excellent books on this list are available for free download: generatingfunctionology by Herbert Wilf and Graph Theory by Reinhard Diestel.
• Syllabus: See the course announcement here

Homeworks

Homeworks are assigned from West's and Wilf's books, as well as from this evolving page of problems. For the specific weekly assignments, see the announcements section below.

Announcements

• Here's the final exam, due back by May 7 at 4pm.


• Solutions to the third homework have been added to the homework page.


• Fourth homework: DUE WEDNESDAY, APR 8.
  • Questions from the homework page: 29, 30, 31
  • Easy questions from West not to hand in: 6.1.5, 6.1.7, 6.3.3, 6.3.4 (in both of these, \alpha is the size of the largest independent set)
  • Questions from West to hand in: 6.1.22, 6.2.5, 6.2.17, 6.3.14


• Solutions to the second homework have been added to the homework page.


• Here is a quick summary of the basic graph theory notation that we will use.


• Third homework: DUE FRIDAY, MAR 6.
  • West 3.2.7a) (Let a_n be the given sum; form the generating function \sum_n a_nx^n; get a nice expression for the generating function by reversing the order of summation and using known identities; find a_n by extracting the coefficient of x^n from the result. This is the snake oil method; Wilf 4.3 gives a lovely description.)
  • West 3.3.16 (It will be helpful here to use the summation formula that we derived for S(n,k).)
  • West 3.3.37
  • West 4.1.19
  • West 4.1.28 (``backwards'' inclusion-exclusion; figure out what counting problem might by amenable to inclusion-exclusion, and would lead to exactly the given expression.)


• Second homewok: DUE FRIDAY, FEB 13.
  • Easy questions from West (don't turn in): 1.3.3, 2.1.1, 2.1.6, 2.2.1, 2.2.8
  • Easy questions from Wilf (don't turn in): Chapter 1, questions 1 and 3
  • Questions from West to turn in: 2.1.19, 2.1.43 b), 2.2.13, 2.2.34 (after doing 2.1.43 b) you might try 1.3.30, but no need to turn this in)
  • Questions from Wilf to turn in: Chapter 1, questons 11 and 21 a)
  • Questions from the homework page: 13 (don't turn this in; just convince yourself that it's ok), 15, 16, 17. (Qustion 15 is killing me. My answer is a little too involved. An alternative to doing 15 is to show me that I'm being an idiot, and that it is not needed in the proof that the characteristic equation method produces the most general solution to a linear recurrence).


• First homework: DUE FRIDAY, JAN 30. The following easy questions from West need not be turned in: 1.1.3, 1.1.5, 1.1.9, 1.1.11, 1.1.14, 1.2.2, 1.2.3, 1.2.5, 1.2.7, 1.2.10. The following questions should be turned in: West 1.1.18, 1.1.31, 1.1.36, 1.2.13a), 1.2.13c), 1.2.25, 1.2.28, 1.2.38. Also do questions 1 through 4 on the list found here.


• THE TIME OF THE CLASS HAS CHANGED to MWF 11:50am-12:40am, HH 125; the first meeting will be in Hurley 258 on Wednesday January 14


• I'll be in my office from 3pm to 5pm this coming Friday (Jan 16).

Created by David Galvin, and last revised on December 15, 2008.