Combinatorics

Course Code: B63003Y

Course Name: Combinatorics

Credits: 2.0

Level: Undergraduate

Pre-requisite: null

Lecture Time: 40 hours

Instructors:Xiaoming Sun

Course Description

This course introduces fundamental knowledge of discrete mathematics mainly in the fields of permutation and combination. This course is designed for undergraduates with major in computer science and technology. Students will be presented with classical theorem and formula, and given opportunity to exhibit what they learn from relevant academic literature and frontier areas.

Topics and Schedule

  1. Permutation and Combination (4 hrs)

1.1.   Permutation and Combination

1.2.   Binomial coefficients

1.3.   Rearrangement and Circular permutation

  1. Recurrence relation (4 hrs)

2.1.   Tower of Hanoi

2.2.   Division of plane

2.3.   Partition

2.4.   Stirling numberof the first and second kind

  1. Generating function (6 hrs)

3.1.   Solve the generating function

3.2.   Fibonacci sequence

3.3.   Catalan number

  1. Inclusion-exclusion principle (4 hrs)

4.1.   Inclusion-exclusion formula

4.2.   Conditional permutation

4.3.   Mobius inversion

  1. Polya theorem(5 hrs)

5.1.   Permutation group

5.2.   Burnside’s Lemma

5.3.   Polya theorem

  1. Pigeonhole principle (4 hrs)

6.1. Simple pigeonhole principle and application

6.2.Ramsey’s theorem

6.3.Ramsey number

  1. Fundamental number theory (3 hrs)
    1. Divisibility and Congruence
    2. Fermat’s theorem
    3. Euler function
    4. Quadratic congruence
  2. Fixed point (2 hrs)

8.1.Sperner’s theorem

8.2.Brower’s theorem of fixed point

  1. Student show (2 hrs)
  2. Tests and Q-course (6 hrs)

Grading

A weekly homework will be given during weeks of the class, the homework will be graded and scores will count for 20% of the total. At the middle and end of the class, there will be midterm and final exams, which will count for 20% and 60% respectively. The full score of this course is 100.

Textbook

[1]    L.Ronald, E.GrahamDonald, KnuthOren Patashnik, Mingyao Zhang, Fan Zhang, Concrete Mathematics: A Foundation for Computer Science, People Post Press, 2013

[2]    R.A.Brualdi, Su Feng, Introductory Combinatorics, China Machine Press, 2012

References