1.6 Division: Le principe d’équivalence

Nous avons déjà vu que l’addition, la soustraction et la multiplication peuvent s’interpréter de manière intéressante dans le contexte de la combinatoire. Nous allons maintenant voir qu’il en est de même pour la division. Ceci peut être obtenu à partir du principe de la somme et de la notion de relation d’équivalence.

Définition 1.6.1.

Si R\displaystyle R est une relation sur un ensemble A\displaystyle A, alors on dit que:

  1. 1.
    ​

    R\displaystyle R est une relation réflexive si x⁢R⁢x\displaystyle xRx pour tout x∈A\displaystyle x\in A.

  2. 2.
    ​

    R\displaystyle R est une relation symétrique si pour tout x,y∈A\displaystyle x,y\in A tel que x⁢R⁢y\displaystyle xRy, alors y⁢R⁢x\displaystyle yRx.

  3. 3.
    ​

    R\displaystyle R est une relation antisymétrique si pour tout x,y∈A\displaystyle x,y\in A tel que x⁢R⁢y\displaystyle xRy et y⁢R⁢x\displaystyle yRx, alors x=y\displaystyle x=y.

  4. 4.
    ​

    R\displaystyle R est une relation transitive si pour tout x,y,z∈A\displaystyle x,y,z\in A tel que x⁢R⁢y\displaystyle xRy et y⁢R⁢z\displaystyle yRz, alors x⁢R⁢z\displaystyle xRz.

  5. 5.
    ​

    R\displaystyle R est une relation d’équivalence si R\displaystyle R est une relation réflexive, symétrique et transitive.

  6. 6.
    ​

    R\displaystyle R est une relation d’ordre partielle si R\displaystyle R est une relation réflexive, antisymétrique et transitive.

Bien que pour le moment ce soit les relations d’équivalence qui nous intéressent, nous avons inclut la notion de relation d’ordre partielle dans la définition ci-dessus car ces dernière jouent aussi un rôle intéressant en combinatoire. Avant d’énoncer le principe d’équivalence, nous allons maintenant montrer que les relations d’équivalence sur un ensemble A\displaystyle A et les partitions d’un ensemble A\displaystyle A sont en fait deux interprétation d’un même concept.

Théorème 1.6.1:

Partition et relation d’équivalence. Si A\displaystyle A est un ensemble, alors il existe autant de relation d’équivalence sur A\displaystyle A que de partition de A\displaystyle A. En particulier, nous avons:

  1. 1.
    ​

    Si R\displaystyle R est une relation d’équivalence sur A\displaystyle A, alors les différents ensembles de la forme
    Ax={y∈A:x⁢R⁢y}\displaystyle A_{x}=\{y\in A:xRy\} forment une partition de A\displaystyle A. Les ensembles Ax\displaystyle A_{x} portent le nom de classe d’équivalence.

  2. 2.
    ​

    Si B1,B2,B3,…,Bn\displaystyle B_{1},B_{2},B_{3},...,B_{n} est une partition de A\displaystyle A, alors l’ensemble R={(a,b):a,b∈Bi⁢ pour un ⁢i}\displaystyle R=\{(a,b):a,b\in B_{i}\textrm{ pour un }i\} est une relation d’équivalence sur A\displaystyle A.

Démonstration.

Exercice. ∎

Théorème 1.6.2:

Principe d’équivalence. Si R\displaystyle R est une relation d’équivalence sur un ensemble A\displaystyle A et si chacune des classes d’équivalence contiennent exactement k\displaystyle k éléments, alors il y a |A|k\displaystyle\frac{|A|}{k} classes d’équivalence.

Démonstration.

Une relation d’équivalence R\displaystyle R sur un ensemble A\displaystyle A partitionne l’ensemble en classe d’équivalence A1,A2,A3,…⁢An\displaystyle A_{1},A_{2},A_{3},...A_{n} comme nous l’affirme le théorème précédent. Par définition d’une partition, nous avons donc Ai∩Aj=∅︀\displaystyle A_{i}\cap A_{j}=\emptyset pour tout i≠j\displaystyle i\neq j. Il nous est donc possible d’appliquer le principe de la somme, ce qui nous donne:

|A1|+|A2|+|A3|+…+|An|=|A|\displaystyle|A_{1}|+|A_{2}|+|A_{3}|+...+|A_{n}|=|A|

Comme par hypothèse chacune des classes d’équivalence contient exactement k\displaystyle k élément, ceci nous permet donc d’affirmer que n⁢k=|A|\displaystyle nk=|A|, c’est à dire n=|A|k\displaystyle n=\frac{|A|}{k}. ∎

Exemple 1.6.1.

Dans une école, il y a 60\displaystyle 60 élèves de 5e année qui doivent être réparti entre 3\displaystyle 3 classes contenant toutes le même nombre d’élève. Combien y aura-t-il d’élève dans chacune des trois classes ? Ici, il est facile de remarquer qu’il s’agit d’une application directe du principe d’équivalence. Le fait de répartir les étudiants en 3 classes revient à faire une partition de l’ensemble des étudiants car aucun étudiant ne peut faire parti de deux classes en même temps, et l’union de l’ensemble des trois classes nous donne l’ensemble de tous les étudiants. Par le théorème nous savons qu’une partition nous permet de définir une relation d’équivalence. Dans ce cas la relation d’équivalence nous dit que des étudiants x\displaystyle x et y\displaystyle y sont équivalent s’il appartiennent à la même classe. De plus, nous savons que toutes les classes d’équivalence possèdent le même nombre d’élément, car le nombre d’étudiants dans chacune des trois classes doit être le même. Par le principe d’équivalence, si k\displaystyle k dénote le nombre d’étudiant dans chaque classe, alors nous avons 60k=3\displaystyle\frac{60}{k}=3. C’est à dire nous avons k=603=20\displaystyle k=\frac{60}{3}=20 élèves dans chacune des classes.

Exemple 1.6.2.

De combien de façon différente un groupe de n\displaystyle n personnes peuvent s’assoir autour d’une table ronde ? À première vu, le problème est une application directe du principe du produit et nous avons n!\displaystyle n! façons d’assoir les n\displaystyle n personnes. Par contre, il faut remarquer que l’emplacement exacte d’une personne n’a pas vraiment d’importance pour le problème. Tout ce qui compte est de savoir quel personne est à notre gauche, et quel personne est à notre droite. En d’autre mot, faire une rotation de la table ne change rien à la configuration. Il s’agit donc d’une application du principe d’équivalence. Comme chacune des configurations possède en fait n\displaystyle n configuration équivalence (Les n\displaystyle n rotations de la table), la solution du problème est donc: n!n=(n−1)!\displaystyle\frac{n!}{n}=(n-1)! façon d’assoir les n\displaystyle n personnes autour d’une table ronde.

Exemple 1.6.3.

De combien de façon différente peut-on choisir 3\displaystyle 3 billes parmi 10\displaystyle 10 billes toutes de couleurs différentes ? Premièrement, remarquons que d’après le principe du produit il y a 10⋅9⋅8=720\displaystyle 10\cdot 9\cdot 8=720 façons de choisir une première bille, puis une deuxième et finalement une troisième (c’est à dire avec ordre…). Par contre, on remarque que changer l’ordre des trois billes nous donne une configuration équivalente. Pour chaque choix ordonné de trois bille, nous avons donc 3!\displaystyle 3! configuration qui sont équivalente. Le principe d’équivalence nous permet donc d’affirmer qu’il y a 10⋅9⋅83!\displaystyle\frac{10\cdot 9\cdot 8}{3!} façons de choisir les trois billes (Sans ordre).

Exemple 1.6.4.

De combien de façon différente une classe de 10\displaystyle 10 étudiants peut être divisé en 5\displaystyle 5 équipes de 2\displaystyle 2 personnes ? Premièrement, remarquons que d’après le principe du produit il y a 10!\displaystyle 10! façons d’ordonnés les 10\displaystyle 10 étudiants. On forme ensuite les 5\displaystyle 5 équipes en groupant les deux premiers étudiants ensembles, les deux suivants, etc.

x1,x2⏟,x3,x4⏟,x5,x6⏟,x7,x8⏟,x9,x10⏟\displaystyle\underbrace{x_{1},x_{2}},\underbrace{x_{3},x_{4}},\underbrace{x_{% 5},x_{6}},\underbrace{x_{7},x_{8}},\underbrace{x_{9},x_{10}}

Maintenant, remarquons qu’échanger l’ordre des deux premiers étudiants nous donne une configuration équivalence, de même si on change l’ordre des deux suivants, etc. De plus, échanger l’ordre de deux groupes nous donne aussi une configuration équivalente. On a donc que chaque configuration nous donne une classe contenant 25⋅5!\displaystyle 2^{5}\cdot 5! éléments. Le principe d’équivalence nous permet donc d’affirmer qu’il y a 10!25⋅5!\displaystyle\frac{10!}{2^{5}\cdot 5!} façons différentes de diviser une classe de 10\displaystyle 10 étudiants en 5\displaystyle 5 groupes de deux étudiants.

Comme pour le cas du principe d’inclusion-d’exclusion, le principe d’équivalence sera aussi généralisé dans le cours de combinatoire 2. Ici, c’est la théorie des groupes qui nous permet de compter selon une relation d’équivalence dans toute sa généralité. Le point clé est la notion d’action de groupe, qui nous permet de démontrer le théorème de Burnside, et ainsi de construire la théorie de Polya. Un problème type de la théorie de Polya est de compter le notre de collier différent que l’on peut faire avec des billes de différentes couleurs.