Introduction to Discrete Mathematics

22m:90, Fall 1998
Instructor: Fred Goodman

---

Contact Information:

Syllabus:

Syllabus in PDF format (Adobe Acrobat/Acrobat Reader needed.)

Textbook:

Richard Brualdi, Introductory Combinatorics, 2nd 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 8:

Exercises 1-10, Chapter 2 of Brualdi.

2nd assignment, due Thursday, September 17:

Regarding Exercise 1 of Chapter 2, find out (something about) for which integers k the chess player will necessarily play exactly k games in some number of successive days.

Exercises from Chapter 3: Numbers 12, 14, 18-21.

3rd assignment, due Thursday, September 24:

Consider problem 21 of Chapter 3. Suppose the 4 streets around the block with southwest corner 4 blocks east and 3 blocks north of home are unavailable. Then how many routes are there between home and the office?

Write a computer program in your favorite programming language to list (in lexicographic order) all permutations of n numbers a_1 < a_2 < ... < a_n. You may suppose that the n numbers are input in increasing order, so they don't have to be sorted first.

4th assignment, due Thursday, October 1:

Chapter 3, Exercises 24-26, 31-33.

Use your computer program which lists permutations of {1,2,..n} to look into the following problem. For a given n, how many permutations of {1,2, ...,n} are there with each possible length 1, 2, 3, ...? What is the maximum possible length of permutations of {1,2,...,n}? Try this out for n = 2, 3, 4, 5, 6, 7.

5th assignment, due Tuesday, October 13:

Try to find a combinatorial explanation for the data concerning the distribution of lengths of permutations. Denote by f(n, k) the number of permutations in S_n which have length k. The data suggest that f(n, k) is the sum of n numbers

f(n-1, k) + f(n-2, k) + ...

Chapter 5, Exercises 7-10, 14, 16-18, 22, 23.

6th assignment, due Tuesday, October 20:

Try to show in general that if a1, a2, ... an is a symmetric unimodal sequence, and r<=n, then the sequence bn = sum_{j=0 to r-1} a(n-j) is also symmetric unimodal.

Chapter 5, Exercises 24, 29, 30, 31, 33, 36, 37. Chapter 6, Exercises 1, 3, 4.

7th assignment, due Thursday, November 5:

Chapter 6: Exercises 4, 11, 12, 14, 15, 23, 24.

8th assignment, due Tuesday, November 17:

Chapter 7: Exercises 1, 3, 6, 7, 13, 16, 17.

9th assignment, due Tuesday, November 24:

Chapter 7: Exercises 21, 24 b and d, 25 b and c, 30, 31, 37 a and b, 38.

Exams:

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. The text of the exams will appear here after the exams have been done by all students.

Midterm (pdf format - requires Adobe Acrobat Reader).

Final (pdf format- requires Adobe Acrobat Reader).