Department of Mathematical Sciences

Mathematics

MATHEMATICS 344

Discrete Mathematics

The aim of this module is to introduce students to combinatorics and elementary number theory, counting and reasoning techniques.  We plan to treat the following topics:

Permutations, combinations, trees, lattice paths, words, generating functions, recursions, inclusion-exclusion, Lagrange inversion, special numbers, matrix-tree theorem, Polya’s enumeration theory, congruences, residue classes, Legendre symbol, reciprocity, continued fractions, theorems of Fermat and Wilson, pythagorean triples, sums of 2 and 4 squares, Diophantine equations, continued fractions.

Module information

  • 21539 344 (16) Mathematics 344
  • 3 lectures and 1 tutorial of 2 hours per week.
  • Prerequisite modules: a pass in Mathematics 214, 244.
  • Language specification : E

Lecturers

  • Prof H Prodinger:  Office 1028, Bedryfsielkunde Building (e-mail: hproding@sun.ac.za)

Study material

  • Typed course materials will be available for some (not all) parts of the course.

Here is a small list of relevant books:

  • Graham-Knuth-Patashnik, “Concrete Mathematics”
  • Stanley, “Enumerative Combinatorics”
  • Flajolet-Sedgewick, “Analytic Combinatorics”
  • Andrews, “The theory of Partitions”
  • Andrews, “Number Theory”
  • Hardy-Wright, “An Introduction to the Theory of Numbers”
  • Rademacher, “Lectures on Elementary Number Theory”

Course presentation

The course material is dealt with in detail during the lectures. Tutorials provide the opportunity to work on problems and discuss course work under the supervision of the lecturer.

Assessment

The class mark will be determined using the mid-semester test and selected exercises. The final mark is determined from the class mark, with a weight of 0.4, and the exam mark, with a weight of 0.6. Class tests are graded and returned to students as soon as possible.

Outcomes

Students who successfully complete this module will have a knowledge of the basics of combinatorics and elementary number theory.

Students will be well equipped to continue with more advanced courses.  Discrete mathematics is one of the department’s major strengths;  there are lots of possibilities for students who want to continue with honours projects, masters or PhD theses.

But students who do not wish to continue will find this course interesting and stimulating in its own right:  Numbers and counting have fascinated people for thousands of years!  Combinatorics and number theory have many interesting applications as well, for instance in cryptography and analysis of algorithms.