1.3 Addition: Le principe de la somme

En combinatoire, l’addition correspond à notre idée intuitive du OU. Ici, il faut cependant faire attention, car il existe en français deux types de OU. Le OU inclusif et le OU exclusif. Le principe de la somme s’applique uniquement dans le cas du OU exclusif. Aucun élément ne peut faire partie à la fois de la première tâche et de la seconde. Dans le langage de la théorie des ensembles, on dit que l’intersection est vide.

Essentiellement, ceci revient à affirmer que si une tâche peut être complétée de n1\displaystyle n_{1} façons ou de n2\displaystyle n_{2} façons, et aucune de ces méthodes n’est en commun, alors il y a n1+n2\displaystyle n_{1}+n_{2} façons de compléter la tâche. C’est la théorie des partitions qui nous permet d’énoncer le principe d’addition de manière plus élégante.

Définition 1.3.1.

Si A\displaystyle A est un ensemble et B1,B2,B3,…⁢Bn\displaystyle B_{1},B_{2},B_{3},...B_{n} sont des sous-ensembles de A\displaystyle A satisfaisant les deux propriétés suivantes :

  1. 1.
    ​

    ⋃i=1nBi=A\displaystyle\bigcup_{i=1}^{n}B_{i}=A.

  2. 2.
    ​

    Bi∩Bj=∅︀,∀i≠j\displaystyle B_{i}\cap B_{j}=\emptyset,\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \forall i\neq j.

Alors on dit que les ensembles B1,B2,B3,…⁢Bn\displaystyle B_{1},B_{2},B_{3},...B_{n} forment une partition de l’ensemble A\displaystyle A. Alternativement, on dit que ces ensembles partitionnent A\displaystyle A.

Théorème 1.3.1:

Principe de la somme. Si une collection d’objet A\displaystyle A peut être partitionné en sous-ensembles B1,B2,B3,…,Bn\displaystyle B_{1},B_{2},B_{3},...,B_{n}, alors le nombre d’élément dans A\displaystyle A est la somme du nombre d’élément de chacun des sous-ensembles. C’est à dire:

|A|=∑i=1n|Bi|\displaystyle|A|=\sum_{i=1}^{n}|B_{i}|
Exemple 1.3.1.

Si une classe est composé de 25 femmes et 20 hommes, alors il y a 20+25=45\displaystyle 20+25=45 façons de choisir un étudiant dans la classe.

Exemple 1.3.2.

Pour satisfaire les exigences de son programme d’étude, un étudiant doit choisir un cours d’informatique, de mathématiques ou de statistique. S’il y a 10 cours d’informatique, 20 cours de mathématiques et 15 cours de statistiques (tous accessible à l’étudiant), combien y a-t-il de façon pour l’étudiant de choisir son cours ? Ici on remarque que l’étudiant doit en fait choisir un cours d’informatique OU un cours de mathématiques OU un cours de statistique. En faisant l’hypothèse qu’aucun cours n’appartient à plus qu’une discipline, on remarque donc qu’il s’agit d’une application du principe de la somme. On a donc:

10+20+15=45⁢possibilités\displaystyle 10+20+15=45\leavevmode\nobreak\ \textrm{possibilit\'{e}s}

Truc: Compter le complément

En combinatoire, la soustraction peut apparaître de différentes façons. Le principe d’inclusion-exclusion que nous verrons dans la prochaine section en est un exemple particulièrement important. La soustraction peut cependant apparaître comme une application particulièrement utile du principe de la somme, ce que nous illustrons dans l’exemple ci-dessous.

Exemple 1.3.3.

Dans une classe de 30\displaystyle 30 étudiants, s’il y a 20\displaystyle 20 femmes, combien y a-t-il d’homme ? Posons H\displaystyle H l’ensemble des hommes et F\displaystyle F l’ensemble des femmes. Comme aucun étudiants n’est à la fois un homme et une femme, alors nous avons H∩F=∅︀\displaystyle H\cap F=\emptyset. Nous pouvons donc appliquer le principe de la somme:

|H∪F|=|H|+|F|\displaystyle|H\cup F|=|H|+|F|

En remplaçant les valeurs donnés dans le problème, nous avons donc:

30=|H|+20⇒|H|=30−20=10\displaystyle 30=|H|+20\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ |H|=30-20=10

Bien que l’exemple ci-dessus puisse sembler particulièrement simple, l’utilisation du complément peut nous permettre de résoudre une multitude de problèmes de combinatoire.