Math 116 -
Combinatorial Analysis - Fall 2008
Professor: Alex Dugas my
homepage
Office: 6510 South Hall
Office Hours: T : 1:30 - 3:00, F : 11 - 12:30.
Prerequisites: Math 8 (with a grade of C or better).
Text: Richard
Brualdi. Introductory Combinatorics. 4th
Edition, Pearson Prentice Hall 2004.
(A copy will be placed on 2hr reserve at the library.
Earlier editions will most likely contain the necessary material and
exercises, but the numbering of pages and problems is likely to
be different.)
Lecture: MWF
Course Timetable (subject to change) |
|||
Date |
Topics |
Reading
|
|
F 9/26 |
Introduction.
Counting. |
Browse Ch. 1 |
3.6: Ex. 1, 2, 6, 9, 20 Solutions |
M 9/29 |
Additon. Multiplication. |
3.1: p. 44-47 |
|
W 10/1 |
Subtraction. Division. |
3.1: p. 48-53 |
|
F 10/3 |
Permutations. Circluar
Permutations. |
3.2: p. 53-60 |
|
M 10/6 |
Circular Permutations. |
3.6: Ex. 7b,e,f, 10, 11, 14, 22 Solutions |
|
W 10/8 |
Combinations.
Binomial Coefficients. |
3.3: p. 60-62 |
|
F 10/10 |
Combinations.
Fubini's Principle. |
3.3: p. 63-64 |
|
M 10/13 |
Permutations with
repetition. |
3.4: p. 64-68 |
3.6: Ex. 21, 32, 39, 41, 45, 46 5.8: Ex. 1, 3. Solutions |
W 10/15 |
Combinations with
repetition. |
3.5: p. 71-75 |
|
F 10/17 |
Pascal's Triangle.
Pascal's Identity. |
5.1: p. 124-8 |
|
M 10/20 |
Pascal's Identity. |
5.8: Ex. 6, 7, 9, 11, 15, 25, 27 (due: 10/29) |
|
W 10/22 |
Binomial and Multinomial
Theorems. |
5.2: p. 129-31 5.5:
p. 144-7 |
|
F 10/24 |
Identities for Binomial
Coefficients. |
5.3: p. 131-5 |
|
M 10/27 |
Inclusion-Exclusion
Principle |
6.1: p. 160-5 |
|
W 10/29 |
Inc.-Exc. continued.
More combinations with repetition. |
6.1,2: p. 166- 170 |
|
F 10/31 |
Derangements. |
6.3: p. 173-5 |
|
M 11/3 |
Recurrence Relations for
counting Derangements |
6.3: p. 176-8 |
6.7: Ex. 9, 14, 15, 16, 20, 21 7.8: Ex. 1c, d Solutions |
W 11/5 |
Recursively Defined
Sequences. Recurrence Relations. |
7.1: p. 206-12 |
|
F
11/7 |
Take-Home
Midterm Due in class. Fibonacci Numbers. |
7.1: p. 212-17 |
|
M 11/10 |
Solving Linear Homogeneous
Recurrence Relations. |
7.2: p. 218-24
(optional: p. 225-8 ) |
7.8:
Ex. 4, 9, 16, 21 and write the gen- erating function as a rational function for the sequence in 16. Solutions |
W 11/12 |
Nonhomogenous Recurrence
Relations. |
7.3: p. 228-34 |
|
F 11/14 |
Generating
Functions. Applications to Recurrence Relations. |
7.4: p. 235-6 7.5: p. 241-5 (skim) |
|
M 11/17 |
Generating
Functions. Counting Solutions to Equations. |
7.5: p. 246-9 (skim) 7.4: p. 237-41 |
|
W 11/19 |
Exponential Generating
Functions. |
7.7: p. 253-7 |
7.8: Ex. 29a,c 30a, 35, 36, 42c,d 8.6: Ex. 1, (2 = bonus) Solutions |
F 11/21 |
Examples of Generating
Functions. Derangements. |
||
M 11/24 |
Catalan Numbers:
Recurrence relation and formula. |
8.1: p. 267-71 |
|
W 11/26 |
Class Canceled:
Happy Thanksgiving Eve |
7.6: p. 249-53 | |
F 11/28 |
No Class: Thanksgiving |
||
M 12/1 |
More Catalan numbers. |
8.1: p. 272-6 |
|
W 12/3 |
Difference Sequences |
8.2: p. 276-84 |
|
F 12/5 |
|||
Th 12/11 |
Final Exam - 8:00 - 11:00 am |
|
|