Combinatoire énumérative

Dans une première partie, approfondir les notion de base du dénombrement vues en L1 et L2.

Dans une seconde partie, introduire l’étude combinatoire des graphes.

Cette UE abordera les points suivants :

Dénombrement

    - Notion de cardinal. Nombre d’applications entre deux ensembles finis, nombre de parties d’un ensemble fini. Nombre d’arrangements, nombre de permutations. Coefficients binomiaux.

    - Formule du crible générale et applications.

    - Nombres de Stirling de première et seconde espèce.

    - Ensembles partiellement ordonnés et fonction de Möbius. Application à l’arithmétique.

Théorie des graphes

    - Notion de graphe. Degré. Chemins, chaînes, cycles. Connexité.

    - Graphes eulériens et hamiltoniens. Graphes bipartites.

    - Isomorphismes, groupes d’automorphismes.

    - Matrice d’adjacence, spectre et propriétés.

    - Arbres, formule de Cayley. Arbres couvrants, algorithme de Kruskal.

    - Coloriage, polynôme chromatique.

    - Planarité, formule d’Euler. Théorème des six couleurs.

Les UE d’algèbre de L1 et L2, en particulier :

- HAX203X Arithmétique et dénombrement

Pré-requis recommandés : L2 maths

Volumes horaires :

            CM : 18

            TD : 18

            TP : -

            Terrain : -