Principes additif et mutiplicatif

Dénombrement : principes additif et multiplicatif

Dénombrement : principes additif et multiplicatif

 

En mathématique, dénombrer c’est compter le nombre d’objets d’un ensemble. 

 

  • Le principe additif

 

Lorsque l’on doit dénombrer un ensemble, on va procéder à une classification sur les objets de l’ensemble, et pour connaitre le nombre total d’objets, nous allons compter le nombre d’objets par classe de la classification.

dénombrement_principe_additif

Si on a une ensemble $\Omega$, on cherche à dénombrer le nombre d’éléments  de $\Omega$. On établit ainsi une classification. Ici il y a 3 classes : A, B, et C. Dans A il y a 4 éléments, dans B il y a 3 éléments et dans C il y en a 5. On note le nombre d’éléments de $\Omega$ (le cardinal de $\Omega$ ) de cette manière : $|\Omega |$

$|\Omega |=|A|+|B|+|C|$

Cette propriété est vraie à certaines conditions :

Il faut que tous les éléments soient comptés au moins une fois :

$A\cup B\cup C=\Omega$

On n’oublie aucun élément de $\Omega$

Il ne faut pas compter plusieurs fois le même élément :

$A\cap B=A\cap C=B\cap C=\varnothing$

La classification doit être non redondante : chaque élément doit être compté au plus une fois., ce qui signifie qu’il n’y a pas d’élément qui soit présent dans deux classes différentes.

 

Prenons un exemple de classification :

Dans une classe il y a 14 filles et 20 garçons. Donc au total 20+14=34 élèves.

 

Prenons maintenant un exemple ou il faut faire attention :

Dans un classe de 34 élèves, tous étudient au moins une LV anglais ou allemand : 23 étudient l’anglais, 20 étudient l’allemand. Combien étudient les 2 LV ?

denombrement_principe_additif

La classe correspond à $\Omega$. Les élèves qui étudient l’allemand correspondent à l’ensemble A et ceux qui étudient l’anglais correspondent à l’ensemble B.

Il y a des élèves qui étudient les deux langues.

Ainsi, si on dit que $|\Omega |=|A|+|B|$, on compte deux fois les élèves qui étudient les deux langues : on les compte en tant que germanistes et en tant qu’anglicistes. S’ils sont comptés deux fois, il faut enlever une fois les éléments qui se situent à l’intersection de A et B.

On obtient donc la formule suivante (très similaire à celle des probabilités) :

$|\Omega |=|A|+|B|-|A\cap B|$

Donc $|A\cap B|=|A|+|B|-|\Omega |=43-34=9$

Il y a donc 9 élèves qui étudient les deux langues.

Dans cette exemple, la condition d’unicité donnée plus haut n’est pas vérifiée car certains éléments sont dans les deux classes à la fois. On ne peut donc pas dire $|\Omega |=|A|+|B|$

 

 

  • Le principe multiplicatif

 

Prenons un exemple :

Un restaurant propose à sa carte 2 entrées, 4 plats principaux (PP) et 3 desserts. On constitue un menu avec une entrée, un PP et un dessert. Le but est de dénombrer le nombre de menus possibles.

Lors du premier choix on a deux branches car 2 entrées possibles, lors du deuxième on a 4 branches pour chaque premier choix (car 4 plats principaux possibles). Et enfin, pour chaque extrémité il y a 3 choix possibles pour les 3 desserts au choix.

Chaque branche correspond à un menu différent, il suffit maintenant de compter le nombre de branches, c’est-à-dire le nombre d’extrémités sur la dernière colonne.

On a donc $2\times 4\times 3=24$ menus possible avec 2 qui correspond au nombre de choix d’entrée, 4 au nombre de choix de PP et 3 au nombre de choix de dessert.

 

Écrivons le de manière plus théorique :

On considère les 3 ensembles suivants :

  • E : L’ensemble des entrées
  • P : L’ensemble des PP
  • D : l’ensemble des desserts

Un menu correspond donc à un triplet $(e, p, d)\in E\times P\times D$, avec e dans E, p dans P et d dans D.

$E\times P\times D$ correspond au produit cartésien des ensembles.

On a donc : $ E\times P\times D=|E|\times |P|\times |D|$

Une autre façon de voir la chose: le syndrome de l’autoroute

 Lorsque sur l’autoroute il y a 3 sorties principales et sur chaque sortie principale il y a 2 sortie secondaire, il n’y a pas 3+2 sorties totales mais 3×2 sorties totales.

 

  • Ensemble de k-uplets dans une ensemble E à n éléments

 

Prenons maintenant un cas particulier :

On prend tous les éléments du triplet dans le même ensemble. On cherche l’ensemble de

k-uplets dans une ensemble E à n éléments : [|1,n|]=E

On doit donc déterminer un k-uplet : (x,x,…,x,x)

Pour chaque x, il y a n choix possibles. D’après le principe multiplicatif, il y a $n^k$

Donc dans un produit cartésien, lorsque les ensembles sont répétés ($E\times E\times…\times E$) on peut écrire :

$|E^k|=|E|^k$

On est dans un modèle de tirage avec ordre (l’ordre importe) et avec répétition (on peut avoir plusieurs fois le même élément dans le k-uplet)

 

Prenons un exemple :

Un sac contient 8 jetons numérotés de 1 à 8.

On tire successivement (donc l’ordre compte) et avec remise (il peut donc y avoir des répétitions) 3 jetons.

Le but est de déterminer le nombre de résultats possibles : le nombre de triplet de la forme $(J_1,J_2,J_3)$ avec $J_1$ le numéro du premier jeton tiré, $J_2$ le numéro du deuxième jeton tiré, $J_3$ le numéro du troisième jeton tiré.

Comme il y a un ordre et répétition, il y a 8 choix pour le premier, 8 pour le deuxième et 8 pour le troisième : il y a $8^3=512$ choix possibles.

 

Il est donc nécessaire de se poser la question de l’ordre et de la répétition dans ce type d’exercice.

Tu veux réviser 2x plus vite ?

Découvre les offres des Bons Profs avec :