ECTS
4 credits
Training structure
Faculty of Science
Description
In the first part, we will explore the basic concepts of counting covered in L1 and L2.
In the second part, introduce the combinatorial study of graphs.
Objectives
This EU will address the following points:
Enumeration
- Concept of cardinality. Number of applications between two finite sets, number of parts of a finite set. Number of arrangements, number of permutations. Binomial coefficients.
- General sieve formula and applications.
- Stirling numbers of the first and second kind.
- Partially ordered sets and Möbius functions. Application to arithmetic.
Graph theory
- Concept of graphs. Degree. Paths, chains, cycles. Connectivity.
- Eulerian and Hamiltonian graphs. Bipartite graphs.
- Isomorphisms, automorphism groups.
- Adjacency matrix, spectrum, and properties.
- Trees, Cayley's formula. Spanning trees, Kruskal's algorithm.
- Coloring, chromatic polynomial.
- Planarity, Euler's formula. Six color theorem.
Teaching hours
- Enumerative combinatorics - CMLecture6 p.m.
- Enumerative combinatorics - TutorialTutorial6 p.m.
Mandatory prerequisites
The algebra courses in L1 and L2, in particular:
- HAX203X Arithmetic and Counting
Recommended prerequisites: L2 maths
Additional information
Hourly volumes:
CM: 18
TD: 18
TP: -
Land: -