title: Preuve par bijection
text: # 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.
  
  ## 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 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.
  