Preuve par bijection

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[1].

Exemples

Nombre de parties d'un ensemble fini

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.

Symétrie des coefficients binomiaux

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.

Égalité de la somme des coefficients binomiaux de rang pair avec celle de rang impair

Il s'agit de la relation, valable pour  :

.

Preuve par bijection

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. Ceci prouve la relation.

Autres exemples

Voici quelques exemples classiques de preuves par bijection en analyse combinatoire :

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bijective proof » (voir la liste des auteurs).

Article connexe

Une preuve par double dénombrement consiste à compter le nombre d'éléments d'un même ensemble de deux façons différentes, pour établir une égalité entre les expressions résultantes.

  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.