Enumerative Combinatorics

In the first part, explore in greater depth the basic concepts of counting covered in L1 and L2.

In the second part, introduce the combinatorial study of graphs.

This lesson will cover the following topics:

Census

    - The concept of cardinality. The number of applications between two finite sets; the number of elements in a finite set. The number of arrangements; the number of permutations. Binomial coefficients.

    - General sieve formula and applications.

    - Stirling numbers of the first and second kind.

    - Partially ordered sets and the Möbius function. Applications to arithmetic.

Graph Theory

    - The concept of a graph. Degree. Paths, chains, cycles. Connectivity.

    - Eulerian and Hamiltonian graphs. Bipartite graphs.

    - Isomorphisms, groups of automorphisms.

    - Adjacency matrix, spectrum, and properties.

    - Trees, Cayley's formula. Spanning trees, Kruskal's algorithm.

    - Coloring, chromatic polynomial.

    - Planarity, Euler's formula. The six-color theorem.

The algebra courses in the first and second years of undergraduate studies, specifically:

- HAX203X Arithmetic and Counting

Recommended prerequisites: L2 Math

Hourly volumes:

            CM: 18

            TD: 18

            Practical Work: -

            Land: -