Preuve bijective

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, une preuve bijective (ou démonstration par bijection) est une technique de démonstration qui consiste à démontrer l'égalité de deux expressions entières en exhibant une bijection entre deux ensembles et en dénombrant chacun d'eux, pour montrer que les expressions obtenues sont égales. 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.

La branche de la combinatoire qui étudie particulièrement les démonstrations bijectives s'appelle la combinatoire bijective[1].

Exemples[modifier | modifier le code]

Symétrie des coefficients binomiaux[modifier | modifier le code]

La symétrie des coefficients binomiaux s'exprime par la formule :

C_n^k = C_n^{n-k}.

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 parmi n.

Preuve bijective

C_n^k est le nombre de sous-ensembles de k éléments d'un ensemble E de n éléments, tandis que C_n^{n-k} est le nombre de sous-ensembles de n − k éléments de ce même ensemble. Il y a une bijection simple entre les deux familles Fk et Fn − k de sous-ensembles de E, qui associe à chaque sous-ensemble à k éléments son complémentaire, lequel contient précisément les n − k éléments restants de S. Par exemple, dans l'ensemble E = {a, b, c, d, e}, on peut associer au sous-ensemble {a, c} son complémentaire {b, d, e}. Comme Fk et Fn − k ont autant d'éléments l'un que l'autre, les coefficients binomiaux correspondants sont égaux.

Autres exemples[modifier | modifier le code]

Les exemples classiques de preuves bijectives en analyse combinatoire comprennent :

Notes et références[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Source[modifier | modifier le code]

Article connexe[modifier | modifier le code]

  • Preuve par double dénombrement : dans le cas particulier où la bijection est l'identité sur un ensemble, la preuve bijective revient à compter le nombre d'éléments de l'ensemble de deux façons différentes, pour établir une égalité entre les expressions résultantes.