production
Skip to Content

MA1510: COMBINATORICS (2017-2018)

Last modified: 25 May 2018 11:16


Course Overview

Combinatorics is the branch of mathematics concerned with counting. This includes counting structures of a given kind (enumerative combinatorics), deciding when certain criteria can be met, finding "largest", "smallest", or "optimal" objects (extremal combinatorics and combinatorial optimization), and applying algebraic techniques to combinatorial problems (algebraic combinatorics). The course is recommended to students of mathematics and computing science.



Course Details

Study Type Undergraduate Level 1
Session Second Sub Session Credit Points 15 credits (7.5 ECTS credits)
Campus None. Sustained Study No
Co-ordinators
  • Professor Ben Martin
  • Dr Alexey Sevastyanov

Qualification Prerequisites

  • Either Programme Level 1 or Programme Level 2

What courses & programmes must have been taken before this course?

  • Any Undergraduate Programme (Studied)

What other courses must be taken with this course?

None.

What courses cannot be taken with this course?

None.

Are there a limited number of places available?

No

Course Description

* Induction * Growth rates * Subsets and binomial coefficients (subsets of fixed size, properties of binomial coefficients, the binomial therem) * Partitions and Bell numbers * Counting with symmetry * Recurrences * Generating functions * Derangements * Principle of inclusion-exclusion * Extremal problems * The Pigeonhole Principle * Ramsey theory * Graph theory

 

Syllabus

  • Counting and probability, induction, growth rates.
  • Permutations, subsets, selections, the Binomial Theorem, partitions, Bell numbers.
  • Generating functions, derangements, exponential generating functions.
  • Inclusion and exclusion, Stirling numbers of the second kind.
  • Extremal set theory, intersecting families, Sperner families.
  • The Pigeonhole Principle, Ramsey numbers, Ramsey’s Theorem.
  • Graphs, paths, trees, topological graph theory, Euler’s Theorem, the Platonic solids.

Further Information & Notes

Course Aims

The course will develop a collection of techniques to solve existence and counting problems in discrete mathematics. It will touch on applications to other parts of mathematics and computer science.

 

Learning Objectives
By the conclusion of the course the student should have gained an understanding of basic combinatorial concepts and techniques including induction, permutations, partitions, binomial coefficients, generating functions and graphs. The course will also develop students’ skills of logical reasoning and proofs. Many of the methods encountered will be applicable in later mathematics courses.

Degree Programmes for which this Course is Prescribed

  • Master of Engineering in Computing Science

Contact Teaching Time

43 hours

This is the total time spent in lectures, tutorials and other class teaching.

Teaching Breakdown


Assessment

1st Attempt: 1 two-hour written examination (80%); in-course assessment (20%). Resit: 1 two-hour written examination paper (maximum of (100%) resit and (80%) resit with (20%) in-course assessment).

Formative Assessment

Informal assessment of weekly homework through discussions in tutorials.

Feedback

In-course assignments will normally be marked within one week and feedback provided to students in tutorials.

Compatibility Mode

We have detected that you are have compatibility mode enabled or are using an old version of Internet Explorer. You either need to switch off compatibility mode for this site or upgrade your browser.