Combinatorics
Dr John Arkinstall
6 points * Second semester * 4 hours per week * Gippsland/Distance (odd-numbered years only) * Prerequisites: GAS1612, GAS2614 * Prohibition: MAP2032
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%
Prescribed texts
Anderson I A first course in combinatorial mathematics OUP, 1974
or
Roberts F S Applied combinatorics Prentice-Hall, 1984
Recommended texts
Liu C L Introduction to combinatorial mathematics McGraw-Hill, 1968
Brualdi R A Introductory combinatorics North Holland 1977
Cohen J A D Basic techniques of combinatorial theory Wiley, 1977
| Published by Monash University, Clayton, Victoria
3168 Copyright © Monash University 1996 - All Rights Reserved - Caution Authorised by the Academic Registrar December 1996 |