Module Identifier MA33210  
Module Title DISCRETE MATHEMATICS  
Academic Year 2005/2006  
Co-ordinator Professor V Mavron  
Semester Semester 2  
Other staff Professor V Mavron  
Pre-Requisite MA21410  
Course delivery Lecture   (19 x 1 hour lectures)  
  Seminars / Tutorials   (3 x 1 hour example classes)  
Assessment
Assessment TypeAssessment Length/DetailsProportion
Semester Exam2 Hours (written examination)  100%
Supplementary Assessment2 Hours (written examination)  100%

Learning outcomes

On completion of this module, a student should be able to:
1. interpret problems in appropriate contexts and apply general counting principles to particular situations.
2. illustrate the principle of inclusion-exclusion and the pigeonhole principle by simple applications.
3. solve second order linear difference equations
4. model problems with difference equations;
5. describe concepts of certain combinatorial structures, e.g. codes, latin squares and balanced designs, and apply counting techniques to the investigation of their parameters.

Brief description

This module will aim to cover the basics of classical combinatorics, the emphasis being on techniques rather than theory. The key ideas are those of selections, permutations and partitions.

Aims

To understand the concepts of selection and permutation and to recognise when and how to use some basic counting techniques.

Content

1. Permutations and selections. Binomial coefficient. Identities involving binomial coefficients. Selections with repetition allowed. Multinomial coefficients. The Pigeonhole Principle.
2. Partitions of integers. Ferrers' Diagrams.
3. Principle of Inclusion and Exclusion. Derangements. Partitions of sets. Stirling numbers of the second kind.
4. Homogeneous second order linear difference equations. Simple inhomogeneous cases.
5. Latin squares. Orthogonality. Balanced designs.
6. Codes. Hamming distance. Error detection and correction.

Reading Lists

Books
** Recommended Text
R P Grimaldi (1999) Discrete Combinatorial Mathematics 4th. Addison-Wesley 0201304244
** Supplementary Text
I Anderson (1974) A First Course in Combinatorial Mathematics OUP 0198596170
C L Liu (1985) Elements of Discrete Mathematics 2nd. McGraw-Hill 007038133X
N Biggs (1989) Discrete Mathematics OUP 0198534272

Notes

This module is at CQFW Level 6