Combinatorial Mathematics CS 290F

Winter 2007-08

Instructor: J. Yellin, x9-2195, yellin@soe.ucsc.edu

Class Hours: TTh 12-145pm , 169 BE

Office Hours: By appointment, 173 BE

Text: Concrete Mathematics, Graham, Knuth, and Patashnik (AW, 2d ed.,1994).

Introduction.

Reading: GKP, pp.1-16. Problems, pp.17-20: 8,11,22.

1. Sums and recurrences, multiple summation.

Reading: GKP, pp. 21-40. Problems, p. 63: 5,7,12,14,17.

2. Sums II. Infinite sums, general summation methods.

Reading: GKP, pp. 41-61. Problems: pp.62-66, 19,22,31,35,36.

3. Binomial coefficients, identities, manipulating binomial coefficients, related summations.

Reading: GKP, pp. 153-195. Problems: pp.242ff., 1-8,13-18,35-38,59,65,100.

4. Binomial coefficients II. Generating functions, hypergeometric functions and transformations.

Reading: GKP, pp. 196-229.

Problems: pp.242ff., 9-12,19,20,22,24,28,45,46,49,63,69,71a,74,76,84,86b.

5. Sequences of number theory. Stirling, Eulerian, Harmonic Numbers

Reading: GKP, pp. 257-272. Problems: 1-4,6,8,9,11-13,17,18,20,21,23.

6. Sequences II. Harmonic sums, Bernoulli numbers, Fibonacci numbers, continuants.

Reading: GKP, pp. 273-309. Problems: 28, 44,53,58,60,65,68,75,79,83,87,90.

7. Generating Functions. Basic tools and methods, recurrences.

Reading: GKP, pp. 320-336. Problems: 1-5, 7,9,14,15,17-19

8. Generating Functions II. Particular examples, convolutions, exponential generators, Dirichlet series.

Reading: GKP, pp. 337-371. Problems: 21,23,26,29,31,33-35,37,41,46.

9. Discrete Probability. Probability generating functions.

Reading: GKP, pp. 381-401. Problems: 1-7, 9, 11, 14,18,21.

10. Discrete Probability II. Coin flip problems, hashing.

Reading: GKP, pp. 401-426. Problems: 26, 28, 32, 35, 37,39,45-47,53,59

Midterm Exam(s), TBA

Final Examination: Wednesday, March 19, 8-11am