Présentation rigoureuse du dénombrement
Note : Toute mes excuses pour l'absence d'accents : contrairement à mon habitude, j'utilise aujourd'hui un clavier anglais. [merci AD]
Bonjour
Dans la lignée de mes deux derniers messages sur le forum combinatoire (raisonnement faux ; combinatoire axiomatique), j'envisage d’écrire un polycopié qui présente le dénombrement de façon rigoureuse.
Concrètement, établir les résultats classiques sur le nombre de fonctions injectives, surjectives, bijectives, etc. en utilisant des preuves d’algèbre. Puis faire le lien le plus rigoureusement possible avec les raisonnements types de la combinatoire (tirages avec ou sans remise, nombre de choix, etc.).
L'objectif est d'obtenir une liste exhaustive de "transitions" que l'on peut utiliser sur un problème de combinatoire pour se ramener à un problème connu. Le tout en étant certain de ne pas se tromper grâce à la rigueur.
Connaissez-vous un ou des livres qui utilisent déjà cette approche ?
Merci d'avance,
Julien
Bonjour
Dans la lignée de mes deux derniers messages sur le forum combinatoire (raisonnement faux ; combinatoire axiomatique), j'envisage d’écrire un polycopié qui présente le dénombrement de façon rigoureuse.
Concrètement, établir les résultats classiques sur le nombre de fonctions injectives, surjectives, bijectives, etc. en utilisant des preuves d’algèbre. Puis faire le lien le plus rigoureusement possible avec les raisonnements types de la combinatoire (tirages avec ou sans remise, nombre de choix, etc.).
L'objectif est d'obtenir une liste exhaustive de "transitions" que l'on peut utiliser sur un problème de combinatoire pour se ramener à un problème connu. Le tout en étant certain de ne pas se tromper grâce à la rigueur.
Connaissez-vous un ou des livres qui utilisent déjà cette approche ?
Merci d'avance,
Julien
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
J'ai aussi exploré beaucoup de livres (anglophones) traitant de mathématiques discrètes mais aucun ne fait de preuve algébrique.
Il y a les compléments du livre de Candelpergher (chez C&M) et du livre De l'intégration aux probabilités, qui sont bien faits, mais c'est trop succinct à mon gout, même si celui du second est déjà assez complet. En fait, il faut regarder dans les Ramis-Deschamps-Odoux pour avoir de vraies preuves en partant de 0.
Ce que je voudrais surtout, c'est une méthode explicite du genre :
1. Modélisation du problème en termes de nombres de choix, de tirages ou de construction d'un mot avec les lettres d'un alphabet
2. Transitions types pour se rapporter aux cas connus et expression en terme d'ensembles et d'applications
3. Bijections et résultats de cours
4. Résultat final
edit : peut-etre qu'il faut que je me lance dans ce projet pour comprendre où est mon blocage...
edit 2 : quand je parle de "transitions types", il s'agit en quelque sorte d'un dictionnaire de méthodes
L'objectif du dénombrement est le calcul du cardinal ( à définir) d'un ensemble fini
Le Théorème fondamental : Deux ensembles ont même cardinal s'ils sont en bijection entre eux
On peut généraliser et dans ce cas , on parlera des ensemles infinis : Cantor ....
Peut être que c'est un poil hors sujet, mais il y a le livre Analysis of Algorithms de Sedgewick et Flajolet. Il y a tout un chapitre sur les fonctions génératrices et l'analyse combinatoire, et en fait, modulo deux théorème de correspondance entre ces séries et des "classes" de dénombrement, eh bien, on peut retrouver à peu près tous les résultats classiques... Nombre de permutations, nombre de cycles, exercice de l'anniversaire identique dans une même classe, etc... L'analyse combinatoire complète le tableau avec les structures arbres, arbres binaires, et les dénombrements associés.
C'est un chemin détourné par rapport à ton objectif que je comprends autour de la rigueur avec les notions connues au début du cycle universitaire mais cela montre la profonde unité de toute la thématique. On y comprend également, avec les séries génératrices, pourquoi certains dénombrements sont beaucoup plus difficiles que d'autres ou qu'il n'y paraît au premier abord.