| MATH30001 Combinatorics and Number Theory | SEMESTER: First |
| CONTACT: Dr Gábor Megyesi (M/P7) | CREDIT RATING: 10 |
| Aims: | To introduce students to selected topics of combinatorics and elementary analytic number theory. |
| Intended Learning Outcomes: | On successful completion of the course students will be:
|
| Pre-requisites: | None |
| Dependent Courses: | None |
| Course Description: | The combinatorial half of this course is concerned with
enumeration, that is, given a family of problems P(n), n a natural number, find a(n), the number of
solutions of P(n) for each such n. The basic device is the generating function, a
function F(t) that can be found directly from a description of the problem and for which
there exists an expansion in the form F(t) = sum {a(n)gn(t); n a
natural number}. Generating
functions are also used to prove a family of counting formulae to prove combinatorial
identities and obtain asymptotic formulae for a(n). In Number Theory we look at the question of identifying irrational numbers and approximating them by rationals. We introduce continued fractions which we study in detail. These lead also to solutions of certain equations (Pell's equations) in integers. When identifying irrational numbers we find criteria which guarantee that a number is transcendental. |
| Teaching Mode: | 2 Lectures per week |
| 1 Tutorial per week | |
| Private Study: | 5 hours per week |
| Recommended Texts: | H S Wilf, Generatingfunctionology, Academic Press. 2nd ed., 1994. |
| A Baker, A Concise Introduction to the Theory of Numbers, CUP, 1984. | |
| Niven, Zuckerman and Montgomery, An Introduction to the Theory of Numbers, (5th edition), 1991, Wiley. | |
| Assessment Methods: | Coursework: 20% |
| Coursework Mode: Two computer assignments (worth 12%), plus a take home test in Week 10 (worth 8%). | |
| Examination: 80% | |
| Examination is of 2 hours duration at the end of the First Semester. |
| No. of lectures | Syllabus |
| 3 | Combinatorics Examples using ordinary power series and exponential generating functions, general properties of such functions. |
| 1 | Dirichlet Series as generating functions. |
| 3 | A general family of problems described in terms of "cards, decks and hands" with solution methods using generating functions. |
| 2 | Generating function proofs of the sieve formula and of various combinatorial identities. Certifying combinatorial identities. |
| 2 | Some analytical methods and asymptotic results. |
| 1 | Number Theory Examples of continued fractions. |
| 1 | The study of finite continued fractions. |
| 1 | Alpha has infinite continued fraction if alpha irrational. |
| 3 | Alpha has periodic continued fraction if alpha is quadratic irrational. |
| 3 | Application to approximation of irrationals by rationals. Hurwitz's Theorem. |
| 1 | Application to solutions of Pell's equation. Proof that e and cos {(p x pi)/q}, for natural numbers p and q, are irrational (apart from obvious exceptions). |
| 1 | Liouville's Theorem on algebraic numbers. Construction of transcendental numbers. |
Last revised August, 2006