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, si on examine deux ensembles finis $X$ et $Y$, la connaissance du dénombrement de $X$ et d'une bijection de $X$ sur $Y$ permet d'obtenir le dénombrement de $Y$.

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 (bijective combinatorics en anglais).

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 $f_{X}$ définie par $f_{X}(x)=1$ si $x\in X$, = 0 sinon, on obtient une bijection entre les parties de $E$ et les applications de $E$ dans {0,1}. Comme il y a $2^{n}$ applications de $E$ dans {0,1}, l'ensemble $E$ possède $2^{n}$ parties.

Symétrie des coefficients binomiaux

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

${\binom {n}{k}}={\binom {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$ éléments parmi $n$.

Preuve par bijection

${\binom {n}{k}}$ est le nombre d'éléments de l'ensemble ${\mathcal {P}}_{k}(E)$ des parties à $k$ éléments d'un ensemble $E$ à $n$ éléments. Or Il y a une bijection simple entre ${\mathcal {P}}_{k}(E)$ et ${\mathcal {P}}_{n-k}(E)$, 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 $n\geqslant 1$ :

$\sum _{0\leqslant 2k\leqslant n}{\binom {n}{2k}}=\sum _{0\leqslant 2k+1\leqslant n}{\binom {n}{2k+1}}$.

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 :

• Plusieurs calculs du nombre de combinaisons avec répétition utilisent une démonstration par bijection.
• Les nombreux dénombrements conduisant aux nombres de Catalan s’obtiennent par diverses bijections.
• Le codage de Prüfer, bijection permettant de démontrer la formule de Cayley donnant le nombre d'arbres « décorés ».
• La correspondance de Robinson-Schensted, bijection qui permet de démontrer la formule de Burnside pour le groupe symétrique.
• La conjugaison des tableaux de Young, qui permet d'obtenir une preuve de la formule du nombre de partitions d'un entier.
• La preuve par bijection du théorème des nombres pentagonaux.

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

Articles connexes

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.