1.2 Multiplication: Le principe du produit

En combinatoire, la multiplication correspond à notre idée intuitive du ET. Il s’agit probablement du principe le plus simple, mais aussi le plus utile. Essentiellement, il nous affirme que s’il y a $\displaystyle n_{1}$ façons de compléter la tâche 1 et $\displaystyle n_{2}$ façons de compléter la tâche 2, alors il y a $\displaystyle n_{1}n_{2}$ façons de compléter la tâche 1 et la tâche 2. Il est cependant plus pratique de l’énoncer dans le langage de la théorie des ensembles. Pour ce faire, nous devons nous rappeler la notion de produit cartésien, ce que nous allons faire immédiatement.

Définition 1.2.1.

Si $\displaystyle A$ et $\displaystyle B$ sont des ensembles, alors on définit le produit cartésien $\displaystyle A\times B$ comme étant:

\displaystyle A\times B=\{(x,y):x\in A\textrm{ et }y\in B\}

Exemple 1.2.1.

Si $\displaystyle A=\{1,2,3\}$ , alors $\displaystyle A\times A$ est l’ensemble suivant:

\displaystyle A\times A=\{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}

Exemple 1.2.2.

Si $\displaystyle A=\{a,b\}$ et $\displaystyle B=\{1\}$ , alors $\displaystyle A\times B$ et $\displaystyle B\times A$ sont les ensembles suivants:

\displaystyle A\times B=\{(a,1),(b,1)\}

\displaystyle B\times A=\{(1,a),(1,b)\}

Un point important à noter dans la définition du produit cartésien est que l’ordre des éléments dans un couple $\displaystyle(a,b)$ est important. En effet, les couples $\displaystyle(1,2)$ et $\displaystyle(2,1)$ sont différents. Le produit cartésien introduit donc une notion d’ordre.

Théorème 1.2.1:

Principe du produit. Si $\displaystyle A$ et $\displaystyle B$ sont deux ensembles, alors le nombre de façon de choisir un éléments de l’ensemble $\displaystyle A$ et un élément de l’ensemble $\displaystyle B$ est le produit du nombre d’élément de chacun de ces deux ensembles. C’est à dire:

\displaystyle|A\times B|=|A|\leavevmode\nobreak\ |B|

Exemple 1.2.3.

Si une classe est composé de 25 femmes et 20 hommes, alors il y a $\displaystyle 25\times 20=500$ façons de choisir un homme et une femme parmi les étudiants de la classe. Pour l’interpréter en terme de théorie des ensembles, nous pouvons considérer l’ensemble $\displaystyle F$ de toutes les femmes comme étant $\displaystyle F=\{F_{1},F_{2},F_{3},...,F_{25}\}$ l’ensemble $\displaystyle H$ des hommes comme étant $\displaystyle H=\{H_{1},H_{2},H_{3},...,H_{20}\}$ . L’ensemble de tout les couples formé d’une femme et d’un homme est donc:

\displaystyle F\times H=\{(F_{1},H_{1}),(F_{1},H_{2}),(F_{1},H_{3}),...,(F_{25% },H_{20})\}

Le nombre de couple est donc: $\displaystyle|F\times H|=|F|\cdot|H|=25\times 20=500$ .

Exemple 1.2.4.

Dans une grande compagnie, on attribue à chaque employé un code d’identification. Ce code est formé de 2 lettres, suivi de 3 chiffres. Combien de code différent peut-on attribuer ? Pour ce faire, remarquons que le problème revient à choisir une lettre ET une lettre ET un chiffre ET un chiffre ET un chiffre. Il s’agit donc d’une application du principe du produit.

LETTRE - LETTRE - CHIFFRE - CHIFFRE - CHIFFRE

Comme il y a 26 lettres et 10 chiffres, on obtient donc:

\displaystyle 26\times 26\times 10\times 10\times 10=26^{2}\times 10^{3}=676% \leavevmode\nobreak\ 000\leavevmode\nobreak\ \textrm{possibilit\'{e}s}

Remarquez qu’ici nous utilisons le principe du produit, car chaque code d’identification peut être vu comme un élément du produit cartésien $\displaystyle L\times L\times C\times C\times C$ , où $\displaystyle L$ est l’ensemble des 26 lettres de l’alphabet, et $\displaystyle C=\{0,1,2,3,4,5,6,7,8,9\}$ .