MAT3057

Combinatorics

Dr John Arkinstall

4 points - Second semester - Two hours of lectures and one 1-hour tutorial per week - Gippsland and distance (odd-numbered years only) - Prerequisites: MAT1085, MAT2016 - Prohibitions: MAP2032, MAT2082, GAS3614

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 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.

Assessment Two assignments: 30% - Examination (3 hours): 70%

Prescribed texts

Anderson I A first course in combinatorial mathematics OUP, 1974
or
Roberts F S Applied combinatorics Prentice-Hall, 1984.

Recommended texts

Brualdi R A Introductory combinatorics North Holland, 1977
Cohen J A D Basic techniques of combinatorial theory Wiley, 1977
Liu C L Introduction to combinatorial mathematics McGraw-Hill, 1968

Back to the 1999 Science Handbook