Authorised by Academic Registrar, April 1996
Objectives The objectives of this subject are for students to develop dexterity and skill in the use and choice of counting techniques; achieve a basic understanding of graph theory and in the use of algorithms, both in the proof of graph theoretic results and in computation; understand the application of combinatorial methods in the analysis of problems in the theory of designs and in combinatorial optimisation.
Synopsis This subject aims to introduce and develop the theory and applications of combinatorial (counting) methods. Principles of enumeration: elementary counting principles, permutations and combinations, generating functions, recurrence relations, the principle of inclusion-exclusion. Combinatorial structures: block designs, latin squares, difference sets, directed and undirected graphs, combinatorial matrices, systems of distinct representatives. Applications: design of experiments, error-correcting codes, assignment problems, network flows, applications of graph theory. Emphasis on algorithms. For the distance class, four two-hour expository and discussion classes are held over the semester to supplement notes for the subject, with extensive problem sets for which full solutions are provided.
Assessment Assignments: 40% + Examination: 60%