Introduction to Discrete Mathematics

22m:150, Fall 1999
Instructor: Fred Goodman

Contact Information:


325G Maclean Hall


goodman at math dot uiowa dot edu


Voice: 319-335-0791

Paper Mail:

Fred Goodman
Department of Mathematics MLH
The University of Iowa
Iowa City, IA 52242-1419 USA

Office Hours:

official: M, W: 2:30, F: 12:30.

unofficial: anytime, night or day

Class Hours:

T Th 9:30-10:45,

N207 Lindquist


Click here to read the syllabus.


Richard Brualdi, Introductory Combinatorics, 3rd Edition, Prentice Hall, 1992.

This text is required.


Assignment lists:

There will be 8 to 12 written assignments. Details will appear here as the assignments are made.

1st assignment, due Tuesday, September 7: Exercises from Chapter 2: 1, 3, 6, 7, 8.

2nd assignment, due Tuesday, September 14: Exercises from Chapter 3: Numbers 12, 14, 17-21.

3rd assignment, due Tuesday, September 21: Exercises from Chapter 3: Numbers 22-25, 30-33.

4th assignment, due Thursday, September 30: Generalizing problems from Chapter 3, we can compute circular permutations, and "necklaces" of multisets with arbitrary multiplicities. The method is the Polya-Burnside counting method for configurations with symmetry, explained in class. Using this method, count circular permuations and "necklaces" of the multiset

{2 a, 2 b, 2 c}.

5th assignment, due Thursday, October 7: Count necklaces with 6 beads of three colors of beads, in which each color must be used at least once.

6th assignment, due Tuesday, October 12: Write computer programs to accomplish the following tasks (using your favorite language):

1. Generate all permuations of {1,2,...,n}. Test the program for small n.

2. Compute the next permuation in lex order. Also use this to generate the list of permuations of {1,2,...,n} for small n.

3. For small n and for k <= Binomial(n, 2), compute f(n,k) = number of permuations of n of length k.

7th assignment, due Thursday, October 21: Chapter 5, Exercises 7-11, 14-18, 25, 26.

8th assignment, due Thursday, November 11:

Suppose that (a_1, a_2, ...,a_n ) is a non-negative, symmetric, unimodal sequence. Let r >= 1 and define a new sequence by b_n = Sum_{j = 0 to r-1} a_{n-j}. Show that this new sequence is also non-negative, symmetric, unimodal.

Chapter 6, Exercises 1, 4, 8, 11, 12, 14, 15, 16, 24, 28.


There will be one or two midterm exams, dates to be negotiated; the dates will appear here when they are known. There will be a comprehensive final exam at the time specified in the Fall, 1999 course schedule, namely on MONDAY, DECEMBER 13 AT 2:15 PM. The text of the exams will appear here after the exams have been done by all students.

Here are some exams from previous semesters, in pdf format.

Midterm, 1998.

Final, 1998.