Skip to Main Content

# Combinatorics: Course Outline (MAT 463)

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Combinatorial problems arise in many areas of pure mathematics, notably in algebra, probability theory, topology, and geometry.

## Course Objective

By the end of the course, that they know some of the uses of, and how to solve, problems involving permutations, combinations, graph enumeration and algebraic combinatorics.

## Course Contents

To basic counting principles, Permutations, Combinations. The injective and bijective principles, Arrangements and selections with repetitions. Graphs in Combinatorics. The Binomial theorem, combinatorial identities. Properties of binomial coefficients, Multinomial coefficients, The multinomial theorem. The Pigeonhole principle, Examples, Ramsay numbers, The principle of inclusion and exclusion, Generalization. Integer solutions. Surjective mapping, Stirling numbers of the second kind, The Sieve of Eratostheries, Euler  φ-function, The Probleme des Manages. Ordinary Generating Functions, Modelling problems. Partition of integers, Exponential generating functions. Linear homogeneous recurrence relations, Algebraic solutions of linear recurrence relations and constant functions, The method of generating functions, A non-linear recurrence relation and Catalpa numbers.