Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Preuve par bijection
Résumé
En mathématiques, une preuve par bijection (ou démonstration par bijection) est une technique de démonstration qui consiste à obtenir l'égalité de deux expressions entières en exhibant une bijection entre deux ensembles dont les deux expressions sont les cardinaux. Autrement dit, on examine deux ensembles finis X et Y, on les dénombre et au moyen d'une bijection de X sur Y, on en déduit que les résultats des comptages sont égaux.
On présente souvent la démonstration en disant qu'on a transformé le problème de dénombrement en un problème équivalent.
La branche de la combinatoire qui étudie particulièrement les démonstrations par bijection s'appelle la combinatoire bijective.
Si à toute partie X d'un ensemble E à n éléments on associe sa fonction caractéristique définie par si , = 0 sinon, on obtient une bijection entre les parties de E et les applications de E dans {0,1}. Comme il y a applications de de E dans {0,1}, l'ensemble E possède parties.
La symétrie des coefficients binomiaux s'exprime par la formule :
En d'autres termes, il y a exactement autant de combinaisons de k éléments parmi n qu'il y a de combinaisons de n − k éléments parmi n.
Preuve par bijection
est le nombre d'éléments de l'ensemble des parties à k éléments d'un ensemble E à n éléments. Or Il y a une bijection simple entre et , celle qui associe à chaque partie à k éléments son complémentaire, lequel contient précisément les n − k éléments restants de E. Par exemple, dans l'ensemble E = {a, b, c, d, e}, on peut associer à la partie {a, c} son complémentaire {b, d, e}. On en déduit qu'il y a autant de parties à k éléments que de parties à n-k éléments, et les coefficients binomiaux correspondants sont donc égaux.
Il s'agit de la relation, valable pour :
La première somme est le nombre de parties de E , ensemble à n éléments ayant un nombre pair d'éléments et la deuxième celui des parties en ayant un nombre impair.
Ayant fixé un élément a de E on obtient une bijection entre les parties paires et les parties impaires en associant à une partie paire X la partie obtenue en ajoutant a si X ne le contient pas, et la lui retirant si elle le contient.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.