MA3004: Combinatorics

School Cardiff School of Mathematics
Department Code MATHS
Module Code MA3004
External Subject Code G100
Number of Credits 10
Level L6
Language of Delivery English
Module Leader Professor Roger Behrend
Semester Spring Semester
Academic Year 2014/5

Outline Description of Module

Combinatorics is the branch of discrete mathematics concerned with the theory of arranging objects according to specified rules.  The objects can be material (such as people in a group or cards from a pack) or abstract (such as numbers, symbols, steps in a process or choices in a procedure). A frequent aim of combinatorics, when applied to particular cases, is to determine the number of arrangements, but without actually listing them. Accordingly, combinatorics is sometimes regarded as being the study of counting or enumeration. However, some other questions which can be addressed by combinatorics are whether certain arrangements are possible at all, and, if so, what an optimal way of obtaining them might be.  Also, in many cases the arrangements will depend on variables, and an aim is often then to study the number of arrangements as a function of these variables and, if possible, obtain an explicit formula for that counting function.

In this module, various general principles and methods of combinatorics will be studied, and then applied to several important enumeration problems, including some in graph theory. 

On completion of the module a student should be able to

  • State the primary aims and applications of combinatorics.
  • Describe, generate, enumerate and utilise basic combinatorial objects, such as permutations, selections, compositions, set partitions, integer partitions and graphs.
  • Apply combinatorial techniques to certain real-world problems.
  • Prove certain combinatorial identities using both algebraic methods and counting arguments.

How the module will be delivered

27 – 50 minute lectures

Some handouts will be provided in hard copy or via Learning Central, but students will be expected to take notes of lectures.

Students are also expected to undertake at least 50 hours private study including preparation of solutions to given exercises.

Skills that will be practised and developed

Skills:

Appreciation of the general scope and importance of combinatorics. 

Ability to study the arrangements of objects using a variety of basic principles and techniques.

Transferable Skills:

Ability to understand, manipulate and apply concepts in discrete mathematics. 

Critical thinking and problem solving skills. 

Ability to present work in a scholarly manner.

How the module will be assessed

Formative assessment is carried out by means of regular homework exercises.  Feedback to students on their performance in the homework and their progress towards the learning outcomes will be provided during lectures.

Summative assessment is by means of written examination at the end of the module.  This gives students the opportunity to demonstrate their overall fulfilment of the learning outcomes.  It also enables them to provide evidence of the higher levels of knowledge and understanding required for above-average marks.

The examination paper has a choice of three from four equally weighted questions.

Assessment Breakdown

Type % Title Duration(hrs)
Exam - Spring Semester 100 Combinatorics 2

Syllabus content

  • Set theory, including power sets, Cartesian products, set partitions, multisets, and the general inclusion-exclusion principle.
  • Functions, including left and right inverse functions, and properties of injective, surjective and bijective functions.
  • Permutations of finite sets and multisets.
  • Selections from finite sets, for the four cases in which order is important or unimportant, and repetition is allowed or not allowed.
  • Integer compositions and partitions.
  • Fundamental identities involving binomial coefficients or Stirling numbers.
  • Applications of permutations, selections, compositions and partitions to certain real-world problems.
  • Proofs of combinatorial identities using both algebraic methods (involving, for example, recursion relations and generating functions) and counting arguments (involving, for example, explicit bijections between finite sets).

Essential Reading and Resource List

Combinatorics: Topics, Techniques, Algorithms, Cameron, P. J., Cambridge University Press, 1994

Background Reading and Resource List

Not applicable.


Copyright Cardiff University. Registered charity no. 1136855