1.5 Égalité: Le principe de la bijection

En combinatoire, il est souvent pratique de démontrer que deux problèmes ont en fait la même solution. Ceci est accompli par le principe de la bijection. Ceci nous permet, entre autres, de résoudre un problème potentiellement difficile, puis d’utiliser ce résultat pour d’autres problèmes qui sont en apparence très différents, mais qui ont en fait la même solution. Ceci nous évite donc de devoir recommencer à zéro à chaque fois. Il est plus difficile de voir l’intérêt direct de ce principe que de ceux que nous avons vus précédemment, mais nous aurons à plusieurs reprises dans le cours l’occasion de l’utiliser.

Étant donné que le principe repose sur la notion de fonction bijective, nous allons donc premièrement rappeler certaines définitions:

Définition 1.5.1.

Si A\displaystyle A et B\displaystyle B sont des ensembles et f:A→B\displaystyle f:A\rightarrow B est une fonction, alors on dit que

  1. 1.
    ​

    f\displaystyle f est une fonction injective si f⁢(x)=f⁢(y)\displaystyle f(x)=f(y) implique que x=y\displaystyle x=y pour tout x,y∈A\displaystyle x,y\in A.

  2. 2.
    ​

    f\displaystyle f est une fonction surjective si, pour tout y∈B\displaystyle y\in B, il existe x∈A\displaystyle x\in A tel que f⁢(x)=y\displaystyle f(x)=y.

  3. 3.
    ​

    f\displaystyle f est une fonction bijective si f\displaystyle f est à la fois injective et surjective.

Théorème 1.5.1:

Principe de la bijection. Deux ensembles ont la même cardinalité si et seulement s’il existe une bijection entre les deux ensembles.

Notez que, bien que la plupart des problèmes de combinatoire que nous allons rencontrer dans le cours utilisent des ensembles de cardinalité finie, le principe est en fait applicable à n’importe quel ensemble, peu importe sa cardinalité. C’est d’ailleurs ce principe qui nous permet d’affirmer qu’il y a autant de nombres naturels que de nombres entiers et de nombres rationnels.

Exemple 1.5.1.

Si A\displaystyle A est un ensemble de n\displaystyle n éléments et k\displaystyle k un nombre naturel, alors il y a autant de sous-ensembles de A\displaystyle A ayant k\displaystyle k éléments que de sous-ensemble de A\displaystyle A ayant n−k\displaystyle n-k éléments. Pour pouvoir le montrer, il nous faut donc trouver une bijection entre les sous-ensembles de k\displaystyle k éléments, et les sous-ensembles de n−k\displaystyle n-k éléments. C’est à dire qu’il nous faut trouver une façon de transformer un ensemble de k\displaystyle k éléments en un ensemble de n−k\displaystyle n-k éléments de sorte que le processus soit inversible.

Sous-ensembles de k\displaystyle k éléments      ⟷\displaystyle\longleftrightarrow      Sous-ensembles de n−k\displaystyle n-k éléments

Pour ce faire, il suffit de remarquer que si B⊆A\displaystyle B\subseteq A est un ensemble de k\displaystyle k éléments, alors A\B\displaystyle A\backslash B sera un ensemble de n−k\displaystyle n-k éléments. Il est facile de voir que ce processus est inversible, il s’agit donc d’une bijection. On peut donc conclure qu’il y a autant de sous-ensemble de k\displaystyle k éléments que de sous-ensemble de n−k\displaystyle n-k éléments.

Truc: Méthode de l’élément distingué

Exemple 1.5.2.

Si A\displaystyle A est un ensemble de n\displaystyle n éléments, alors A\displaystyle A possède autant de sous-ensemble ayant un nombre pair d’élément que de sous-ensemble ayant un nombre impair d’éléments. Pour résoudre ce problème, nous allons utiliser la méthode de l’élément distingué. Pour ce faire, fixons un élément a∈A\displaystyle a\in A, et définissons la fonction suivante:

B\displaystyle B un sous-ensemble de A\displaystyle A ayant un nombre pair d’élément B={B′\{a}⁢ si ⁢a∈B′B′∪{a}⁢ si ⁢a∉B′\displaystyle B=\left\{\begin{array}[]{l}B^{\prime}\backslash\{a\}\textrm{ si % }a\in B^{\prime}\\ B^{\prime}\cup\{a\}\textrm{ si }a\not\in B^{\prime}\end{array}\right.      ⟷\displaystyle\longleftrightarrow      B′\displaystyle B^{\prime} un sous-ensemble de A\displaystyle A ayant un nombre impair d’élément B′={B\{a}⁢ si ⁢a∈BB∪{a}⁢ si ⁢a∉B\displaystyle B^{\prime}=\left\{\begin{array}[]{l}B\backslash\{a\}\textrm{ si % }a\in B\\ B\cup\{a\}\textrm{ si }a\not\in B\end{array}\right.

Il est facile de voir qu’il s’agit bien d’une bijection car le processus est inversible. On peut donc conclure qu’il y a autant de sous-ensembles ayant un nombre pair d’élément que de sous-ensembles ayant un nombre impair d’élément.