Combinatorics
BS BN BT DT BC BP BDT
Dr John Arkinstall
6 points * Second semester * 4 hours per week * Gippsland/Distance (odd-numbered years only) * Prerequisites: GAS1612, GAS2614
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 Gippsland class, there are two two-hour classes per week for thirteen weeks. Classes vary through the semester, with tutorial and workshop sessions later in the course. 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