Mathematics

ECM3721 - Combinatorics (2015)

Back | Download as PDF
MODULE TITLECombinatorics CREDIT VALUE15
MODULE CODEECM3721 MODULE CONVENERDr Robin Chapman (Coordinator)
DURATION: TERM 1 2 3
DURATION: WEEKS 11 weeks 0 0
Number of Students Taking Module (anticipated) 19
DESCRIPTION - summary of the module content

Combinatorics, a branch of pure mathematics, is the study of finite mathematical structures and is used frequently in computer science to obtain estimates on the number of elements of certain sets. This module will be particularly concerned with enumerative questions, that is, counting the number of structures of a particular kind. We will consider structures, including partitions, lattice paths and block designs. Furthermore, we will look at relations with other branches of mathematics, notably probability theory, algebra, matrix theory and number theory. Your goal is to solve combinatorial problems of standard type in the topics covered and to tackle easier problems of non-standard form.


Prerequisite module: ECM1702 and ECM2712 or equivalent
 

AIMS - intentions of the module

To inspire a genuine engagement with combinatorial methods and their applications in other branches of mathematics

INTENDED LEARNING OUTCOMES (ILOs) (see assessment section below for how ILOs will be assessed)

On successful completion of this module, you should be able to:
 

Module Specific Skills and Knowledge:
1 solve combinatorial problems of standard type in the topics covered and to tackle easier problems of non-standard form.
Discipline Specific Skills and Knowledge:
2 understand the close links between combinatorial problems and other areas of mathematics including the central topics of algebra and probability theory;
3 appreciate the role of conjecture and investigation within mathematics.
Personal and Key Transferable/ Employment Skills and  Knowledge:
4 develop strategies to solve challenging mathematical problems, which will enhance your time management and problem solving skills.

SYLLABUS PLAN - summary of the structure and academic content of the module

- binomial and multinomial coefficients;

- application to basic enumerative problems and to lattice path counting;

- the pigeonhole principle;

- parity arguments;

- the inclusion-exclusion principle;

- recurrences;

- generating functions;

- the Catalan numbers and Catalan families;

- rook polynomials applications to derangements and the probleme des menages;

- designs;

- affine and projective designs;

- Fisher's inequality;

- symmetric designs;

- Steiner triple systems;

- partitions of sets;

- Stirling and Bell numbers;

- partitions of numbers;

- partitions with restricted parts;

- Euler's pentagonal number theorem;

- Ramsey's theorem;

- special cases of Van der Waerden's theorem;

- Ramsey-type problems.

LEARNING AND TEACHING
LEARNING ACTIVITIES AND TEACHING METHODS (given in hours of study time)
Scheduled Learning & Teaching Activities 33.00 Guided Independent Study 117.00 Placement / Study Abroad 0.00
DETAILS OF LEARNING ACTIVITIES AND TEACHING METHODS
Category Hours of study time Description
Scheduled learning and teaching activities 33 Lectures/example classes
Guided independent study 117 Guided independent study
     

 

ASSESSMENT
FORMATIVE ASSESSMENT - for feedback and development purposes; does not count towards module grade
Form of Assessment Size of Assessment (e.g. duration/length) ILOs Assessed Feedback Method
Not applicable      
       
       
       
       

 

SUMMATIVE ASSESSMENT (% of credit)
Coursework 20 Written Exams 80 Practical Exams
DETAILS OF SUMMATIVE ASSESSMENT
Form of Assessment % of Credit Size of Assessment (e.g. duration/length) ILOs Assessed Feedback Method
         
Written exam – closed book 80 2 hours All Specific comments by markers and general comments on website
Coursework – example sheets 20 60 hours All Specific comments by markers and general comments on website
         
         

 

DETAILS OF RE-ASSESSMENT (where required by referral or deferral)
Original Form of Assessment Form of Re-assessment ILOs Re-assessed Time Scale for Re-reassessment
All above Written exam (100%) All August Ref/Def period
       
       

 

RE-ASSESSMENT NOTES

If a module is normally assessed entirely by coursework, all referred/deferred assessments will normally be by assignment.


If a module is normally assessed by examination or examination plus coursework, referred and deferred assessment will normally be by examination. For referrals, only the examination will count, a mark of 40% being awarded if the examination is passed. For deferrals, candidates will be awarded the higher of the deferred examination mark or the deferred examination mark combined with the original coursework mark.

RESOURCES
INDICATIVE LEARNING RESOURCES - The following list is offered as an indication of the type & level of
information that you are expected to consult. Further guidance will be provided by the Module Convener

ELE – http://vle.exeter.ac.uk

Reading list for this module:

Type Author Title Edition Publisher Year ISBN Search
Set Bryant, Victor Aspects of combinatorics : a wide-ranging introduction Cambridge University Press 1993 000-0-521-41974-3 [Library]
Set Cameron, Peter Combinatorics: Topics, Techniques, Algorithms Cambridge University Press 1994 000-0-521-45761-0 [Library]
CREDIT VALUE 15 ECTS VALUE 7.5
PRE-REQUISITE MODULES ECM2712, ECM1702
CO-REQUISITE MODULES
NQF LEVEL (FHEQ) 6 AVAILABLE AS DISTANCE LEARNING No
ORIGIN DATE Friday 09 January 2015 LAST REVISION DATE Wednesday 11 March 2015
KEY WORDS SEARCH Combinatorics; generating functions; design theory; partitions.