MATHEMATIQUES DISCRETES ET COMBINATOIRE

SOMMAIRE De l'abaque au boulier / Racines grecques, boulets / Le mauchecar de la combinoraticenne Dossier 1 : Dénombrements élémentaires Dénombrer c'est bien plus que compter! Si l'on sait réciter en une monotone litanie la suite des entiers 1,2,3,4... jusqu'à l'épuisement, on ne connaît pas toujours les subtilités que recèlent les combinaisons, les arrangements, les permutations et autres dérangements. De la théologie à la combinatoire moderne/ Dénombrements élémentaires / Dénombrer les mains au poker / Histoires de dérangements / Chemins faisant / Les nombres de Catalan (1) / La bijection pour dénombrer / Les permutations Dossier 2 : Secrets et méthodes Les outils mobilisés pour dénombrer sont parfois complexes : combien d'essais infructueux avant de trouver l'analogie ou la bijection lumineuse d'où va jaillir la solution! Quelques principes "magiques", simples et féconds, vont aider à manipuler les objets "discrets". Le principe des tiroirs / Induction, récurrence et récursivité / Les nombres de Catalan (2) / Le crible de Poincaré / Les fonctions génératrices / Le principe de l'extremum Dossier 3 : Graphes et optimisation Que ce soit pour visualiser les positions gagnantes d'un jeu et découvrir les stratégies qui y mènent, ou pour optimiser un processus sous contrainte, la théorie des graphes s'avère souvent salutaire. Le calcul booléen / Optimisation combinatoire / Le très discret groupe tétraédrique / La programmation en nombres entiers / La théorie des jeux / Mathématiques discrètes Dossier 4 : Jouer avec la combinatoire Par nature, les mathématiques discrètes sont facilement représentables : des grilles de sudoku aux problèmes de coloriage en passant par l'assemblage des pièces d'un puzzle, les interprétations visuelles et ludiques ne manquent pas pour décrire les propriétés du monde discret. Problème de coloriages / Théorème des quatre couleurs / Les parallélépipèdes parfaits / Le rangement de ma boîte de cubes / Décomposition d'un carré / Guitarpèges / Un théorème qui tombe à Pick / Le stomachion d'Archimède Dossier 5 : Problèmes de maths discrètes L'histoire de l'analyse combinatoire et des mathématiques discrètes n'est pas ancienne, en comparaison avec celle de la géométrie ou de l'arithmétique. il en résulte qu'un grand nombre de problèmes sont récents, et pas toujours encore résolus. La combinatoire hier et aujourd'hui / Combien existe-t-il de grilles de sudoku’