ECTS
4 credits
Component
Faculty of Science
Description
In the first part, the basic concepts of enumeration seen in L1 and L2 are studied in greater depth.
The second part introduces the combinatorial study of graphs.
Objectives
This UE will cover the following points:
Count
- Notion of cardinal. Number of applications between two finite sets, number of parts of a finite set. Number of arrangements, number of permutations. Binomial coefficients.
- General screen formula and applications.
- Stirling numbers of the first and second kind.
- Partially ordered sets and Möbius function. Application to arithmetic.
Graph theory
- Notion of graph. Degrees. Paths, chains, cycles. Connectedness.
- Eulerian and Hamiltonian graphs. Bipartite graphs.
- Isomorphisms, automorphism groups.
- Adjacency matrix, spectrum and properties.
- Trees, Cayley formula. Covering trees, Kruskal algorithm.
- Coloring, chromatic polynomial.
- Planarity, Euler's formula. Six-color theorem.
Necessary prerequisites
L1 and L2 algebra courses, in particular :
- HAX203X Arithmetic and enumeration
Recommended prerequisites: L2 maths
Further information
Hourly volumes :
CM: 18
TD : 18
TP: -
Land: -