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 9:00 - 9:50 am. in 1109 North Hall.



Announcements:

 

 

 

Course Timetable (subject to change)

    Date

      Topics    

    Reading   

  
 Homework  

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

 

 

 


Course Content and Goals:
  The emphasis of this class is on Enumerative Combinatorics, that is, on techniques for counting finite sets.  By nature, this subject consists of a variety of different techniques for counting different things, and the difficulty in solving problems often arises in recognizing the correct method, if not in creating an entirely new one.  We will thus also practice problem solving strategies that are useful in approaching challenging problems.  After reviewing some elementary counting principles, we will study Combinations and Permutations and develop the theory of Binomial Coefficients and Pascal's Triangle.  We then move on to Recurrence Relations and applications of Generating Functions.  Other topics include the Pigeonhole Principle and the Inclusion-Exclusion Principle.  In the text this corresponds roughly to most of Chapters 3, 5 and 7, together with parts of Chapters 2 and 6.  If time permits, we may also dabble in Graph Theory (Chapter 11).

Homework:  Homework exercises will be assigned in lecture and listed on the course webpage.  Homework will be due in lecture each Friday.  You may work together on homework problems; however, you must write up your answers individually.  You must show all your work and clearly explain your reasoning in order to receive full credit.  Your lowest homework score will be automatically dropped.

Exams: There will be one or two take-home midterm exams during the quarter.  The final exam is scheduled for Thursday December 11, 8:00--11:00 am.  The problems on the exams will be similar to those seen in class or on the homeworks.   No make-up exams will be given, except in extraordinary circumstances.  If you have a serious conflict with any of these exams or miss one for any reason, it is your responsibility to notify me immediately so that other arrangements may be made

Grades:
  Grades will be computed from your scores on homeworks and exams as follows:  Participation = 10%, Homework = 25%, Midterm(s) = 25%, Final = 40%.  No letter grades will be assigned until the end of the semester, and the exact grading scale will be curved relative to the difficulty of the exams.