Preuve par bijection

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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

Si à toute partie X d'un ensemble E à n éléments on associe sa fonction caractéristique ${\displaystyle f_{X}}$ définie par ${\displaystyle f_{X}(x)=1}$ si ${\displaystyle 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 ${\displaystyle 2^{n}}$ applications de de E dans {0,1}, l'ensemble E possède ${\displaystyle 2^{n}}$ parties.

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

${\displaystyle {\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

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

Il s'agit de la relation, valable pour ${\displaystyle n\geqslant 1}$ :

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

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.

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.

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