| CODE | MAT1411 | ||||||||
| TITLE | Discrete Methods | ||||||||
| UM LEVEL | 01 - Year 1 in Modular Undergraduate Course | ||||||||
| MQF LEVEL | 5 | ||||||||
| ECTS CREDITS | 4 | ||||||||
| DEPARTMENT | Mathematics | ||||||||
| DESCRIPTION | - Permutations, - Combinations, - Partitions of a set, - The inclusion-exclusion principle, - Recurrence relations, - Generating functions, - Partitions of a positive integer. Aims: The aim of this study-unit is to provide an in-depth understanding of a wide range of elementary methods in mainly combinatorial enumeration: counting the number of ways of choosing a number of objects out of a given number, with or without repetition, ordered or unordered; counting the number of functions between two finite sets; solve first order recurrence relations and second order recurrence relations with constant coefficients; find the size of a union of a number of finite sets. These techniques are at the basis of further studies in combinatorics and also in other subjects, such as Discrete Probability and Computer Science. Simple applications of this type will be illustrated. One aim of the course is to show the student that Combinatorics is a well-integrated subject with other areas of mathematics. Learning Outcomes By the end of the study-unit, the student will be able to: - Distinguish between different ways of choosing k out of n objects; - Use the Pigeonhole Principle; - Learn the use of factorial, falling factorial, binomial coefficient, multinomial coefficient, and Stirling numbers of the Second Kind; - Find the number of functions, injections, and surjections between two finite sets, and find expressions for the number of partitions of a finite set; - Use the method of generating functions; - Solve first order recurrence relations; - Solve linear second order recurrence relations with constant coefficients by finding a homogeneous solution and a particular solution; - Solve elementary problems involving the combinatorics of partitions of integers. Skills By the end of the study-unit the student will be able to: - See in action the power of viewing the same counting problem expressed in two seemingly different ways, a useful technique in all of mathematics; - Obtain the same solution of a counting problem in different ways; - Be able to use algebra (like generating) functions to solve counting problems and use counting techniques to solve algebraic problems such as the expansion of a binomial expression raised to a negative or positive integer; - See how choosing k out of n objects can be viewed as a problem of distributing objects in bins; - Use counting techniques in simple discrete probability problems; - If time permits, use recurrence relations to solve simple problems like the Gambler’s Ruin Problem in Probability; - Familiarise themselves with partitions of an integer and Euler’s phi-function, which is of great importance in other branches of mathematics, and solve simple combinatorial problems on partitions of an integer. Main texts and supplementary reading: Main text One of - Biggs N.L., Discrete Mathematics, 2nd Edition, Oxford University Press, 2002. My favourite introduction to Discrete Mathematics at this level. This book should be bought by anyone intending to follow the Discrete Stream or, at least, by students who feel they are good in this topic and would like to know more. or - V. K. Balakrishnan. Combinatorics. (Schaum Series), 1997 This is recommended for those who will not take the Discrete Stream, and are mainly interested in getting through this course. It is, as is usual for the Schaum Outline Series, a problem-based text. A very inexpensive buy. Buying both books is, of, course, encouraged. - My course notes, found on the VLE, complement closely the lecture course Supplementary reading: - R.P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th Edition, 2004. Considered by some to be the best introduction to Discrete Mathematics. Should appeal to students of CS. - F.S. Roberts & B. Tesman, Applied Combinatorics, (2nd or later edition). Prentice-Hall, 2009. Does not follow the same route as our course, and has a much wider coverage. But contains a wonderful variety of applications. - A. Tucker, Applied Combinatorics (6th edition). (Wiley), 2012. Again, this book does not follow closely the same route as our course, but some could find it easier than Biggs’ book for learning new topics. - P.J. Cameron, Combinatorics: Topics. Techniques, Algorithms. (Cambridge University Press), 1998. One could describe this as a more advanced text than Biggs’. The author’s website contains solutions to exercises. |
||||||||
| ADDITIONAL NOTES | Leads to: MAT2413 | ||||||||
| STUDY-UNIT TYPE | Lecture | ||||||||
| METHOD OF ASSESSMENT |
|
||||||||
| LECTURER/S | Josef Lauri |
||||||||
|
The University makes every effort to ensure that the published Courses Plans, Programmes of Study and Study-Unit information are complete and up-to-date at the time of publication. The University reserves the right to make changes in case errors are detected after publication.
The availability of optional units may be subject to timetabling constraints. Units not attracting a sufficient number of registrations may be withdrawn without notice. It should be noted that all the information in the description above applies to study-units available during the academic year 2024/5. It may be subject to change in subsequent years. |
|||||||||