Preuve bijective

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

ExemplesModifier

Symétrie des coefficients binomiauxModifier

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

Preuve bijective

  est le nombre de sous-ensembles de k éléments d'un ensemble E de n éléments, tandis que   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 exemplesModifier

Les exemples classiques de preuves bijectives en analyse combinatoire comprennent :

Notes et référencesModifier

(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 connexeModifier

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.