Combinatorics

This course provides a study of combinatorial analysis based on the text by Chen Chuan-Chong and Koh Khee-Meng. It focuses on fundamental counting principles and the algebraic tools required to solve complex enumeration problems. Syllabus topics include: - Permutations and Combinations: Application of the Addition, Multiplication, Bijection, and Injection Principles. Coverage includes circular permutations, selections with repetitions, and distribution problems involving distinct and identical objects. - Binomial and Multinomial Coefficients: The Binomial and Multinomial Theorems, properties of Pascal’s Triangle, and methods for proving combinatorial identities. - Pigeonhole Principle and Ramsey Theory: Using the Pigeonhole Principle and its generalized form to prove the existence of patterns, leading to an introduction to Ramsey numbers. - Inclusion and Exclusion: The Generalized Principle of Inclusion and Exclusion (GPIE) applied to derangements, the Sieve of Eratosthenes, and the Euler phi-function. - Generating Functions: Modeling selections and arrangements using ordinary and exponential generating functions, including the study of integer partitions. - Recurrence Relations: Techniques for solving linear homogeneous and non-homogeneous recurrence relations, systems of recurrences, and nonlinear relations involving Catalan numbers.