MATH 116    COMBINATORICS  



   Instructor: Azer Akhmedov
   Office: 6702 South Hall.
   E-mail: akhmedov A.T. math.ucsb.edu
   Phone: 893 2889
   Office Hours:  Wednesday 2-5pm.


    GRADING POLICY:   SCHEME 1: Homework: 30%,  Midterms: 20% + 20% = 40%,  Final: 30%.
                                         SCHEME 2: Homework 30%,   Midterms: 15% + 15% = 30%,  Final: 40%.
                                         I will choose the better of the two grades obtained by these schemes.
                                        

    TEXTBOOK:     Peter J. Cameron.  Combinatorics - Topics, Techniques, Algorithms.

   

  MIDTERM 1:   October 26th.        MIDTERM 2:   November 28th.

  FINAL:  Dec13th, 4-7pm.  In classroom.

  Books, calculators are not allowed in the exams.  You may use one 3x5 notecard. Please bring ID and a bluebook.
 
  REVIEW SESSION for Final: Dec.11th, Tuesday 11pm-12noon.  South Hall 6635.
  

    
  HOMEWORK:          Homeworks are due every Friday in class. There will be 10 homeworks during the quarter. The lowest
                                       score will be dropped for every student and substitued with the highest score.                                         
                                       Problems marked with STAR are more difficult than usual; they will be graded lightly but I strongly  
                                       encourage you to try your best, and at least to find some partial solutions.
 
Date
 Section
                     Topic    
             Homework
09/28
 3.1, 3.2.
 Subsets of fixed size. Binomial coefficients.
10/1
 3.2, 3.3.
 Binomial Theorem.  Pascal's Triangle.
10/3
 3.5.
 Permutations.
10/5
 3.6.
 Estimate for factorials. Stirling Formula.
 HWK#1.  Section 3.13.
3a, 3d, 8, 10*, 11*.
10/8
 3.7.
 Selections.
10/10
Review of Chapter 3.
10/12
 4.1.
 Fibonacci Numbers.
 HWK#2
10/15
 4.3.
 Linear Recurrence Relations.
10/17
 4.5.
 Catalan Numbers.
10/19
 5.1.
 Inclusion-Exclusion Principle.
 HWK #3. Section 4.8.
1a, 2, 3, 6, 8a, 10, 15, 16.
10/22
 5.2.
 Generalization.
10/24
 10.1,10.2
 The Pigeonhole Principle.

10/26
    MIDTERM 1
 HWK#4
10/29
 10.3,10.4
 Ramsey's Theorem. Ramsey Numbers.
10/31
 10.5.
 Shur's Theorem.
11/2
 10.5.
 More Applications.
 HWK#5. Section 10.7.
1, 2, 3a, 4, 5a, 6, 7.
11/5
 11.1
 Graphs.  Isomrphisms of Graphs.
11/7
 11.2.
 Trees and Forests.
11/9
 Euler Graphs.
 HWK#6
11/12
 11.4
  VETERAN'S DAY. HAPPY HOLIDAYS!
11/14
 11.4.
 Euler Graphs.
11/16
 11.5.
 Hamiltonian Graphs.
11/19
Review of Chapter 11.
 HWK#7. Section 11.13.
2, 5, 6, 7b, 12*
11/21
 18.2.
 Planar Graphs.

11/23
THANKSGIVING. HAPPY HOLIDAYS!
11/26
 18.5.
 Euler's Formula.
11/28
MIDTERM 2
 HWK#8
12/30
 18.6.
 Applications. Platonic Solids.
12/3
 18.7
 Semiregular Polyhedra - Soccer Ball.
12/5
2, 3 and 5  Colour Theorems.
 HWK#9