F19PB - Pure Mathematics B

Course leader(s):

• Christian Saemann (Edinburgh, September)

Syllabus

1. Naive set theory (1.1 1. Sets and subsets, 1.2 2. Operations with sets, 1.3 3. Relations and functions, 1.4 4. Cardinality of a set)

2. Counting methods (2.1 1. Counting basics, 2.2 2. Enumerative combinatorics , 2.3 3. Binomial coefficients, 2.4 4. The multinomial numbers, 2.5 5. Grid routes and the Catalan numbers, 2.6 6. Partitions, 2.7 7. Generating functions, 2.8 8. Group actions, 2.9 9. Burnside’s lemma, 2.10 10. Pólya enumeration theorem)

3. Graph theory (3.1 1. Graphs, 3.2 2. Planar graphs, 3.3 3. Colouring graphs, 3.4 4. Bipartite graphs)

Learning outcomes

By the end of the course, students should be able to do the following:

• apply basic set theoretic language to counting problems and to differentiate between countable and uncountable sets
• formulate solutions to counting problems using basic techniques from enumerative combinatorics
• recognise different counting problems as equivalent to archetypal counting problems such as selection or distribution problems, integer partitions or set partitions, or Catalan paths
• formulate generating functions for counting problems in order to calculate their answers
• formulate cycle indices for problems counting group orbits in order to apply Burnside's lemma and Polya's enumeration theorem to calculate their answers
• compose arguments using theorems for simple and planar graphs
• formulate collision problems as graph colouring problems

Further details

Curriculum explorer: Click here

SCQF Level: 9

Credits: 15