|
||||||||||||||||||||||||||||||||||||||||
|
Principe d'inclusion – exclusion (PIE) Lorsque les choses sont
partagées, comment compter ? En bref (les traits représentent le cardinal
de l'ensemble).
|
Anglais: The inclusion-exclusion principle
|
n(A) est la quantité d'éléments de A,
nommée le cardinal
de A. Le
cardinal de l'ensemble A est aussi noté |
|
|
||
|
5 objets
dans l'ensemble A. 6 objets
dans l'ensemble B. Mais il
n'y a pas 5 + 6 = 11 objets en tout Car, les
deux ensembles ont 2 objets en commun. Ceux-ci ont été comptés deux fois. n(A avec B) = n(A) + n(B) – n( A et B en commun). |
|
|
|
|
|||
|
Le nombre
d'objets dans une Union est égal à la somme des objets des deux
collectons diminué du nombre d'objets en commun, à l'intersection. |
Voir Probabilités
pour une formule analogue |
||
|
Exemple On connaît les goûts des amateurs de
pizzas. Mais, on ne sait pas combien ils sont. |
Il
y a 14 amateurs de pizzas. |
||
|
Exemple (notation avec barres)
|
|
||
|
Propriétés** A et B sont deux sous-ensembles de
l'ensemble fini U. |
Cardinal de A intersection
B
Cardinal de A à l'exclusion de B
Cardinal de A ou
exclusif B
|
||
|
|
||||
|
|
||||
|
Exemple On connaît la répartition des
étudiants (rose), on ne sait pas
combien ils sont (calcul en bleu). |
Il y a 80 étudiants
qui étudient au moins une langue. |
|||
|
À la télévision:
Combien regardent au moins un
programme ? |
T
(union) = 28 + 19 + 24 – (10 + 14 + 16) = 39 |
|||
|
Combien de nombres de 1 à 1000 sont
divisibles par 5, 6 ou 7 ? |
Divisibles par 5 : 1000/5 = 200 Divisibles par 6 : 1000/6 = 166,6… => 166 Divisibles par 7 : 1000/7 = 142,8…=> 142 Divisibles par 5 et 6 : 1000/30 = 33,3… => 33 Divisibles par 6 et 7 : 1000/42 = 23,8… => 23 Divisibles par 5 et 7 : 1000/35 = 28,5… => 28 Divisibles par 5, 6 et 7 : 1000/210 = 4,7… => 4 T
= 200 + 166 + 142 – 33 – 23 – 28 + 4 = 428 |
|||
|
|
||
|
Parmi les
nombres de 1 à 300 compris, combien sont-ils à être divisibles par au moins l'un de
ces nombres: 3, 5 ou 7? |
A = nombre divisibles par 3 B = nombre divisibles par 5 C = nombre divisibles par 7 |
|
|
La
question posée: |
|
|
|
Quantité de nombre divisible par 3 par 5 par 7 |
n(A) = plancher
(300/3) = 100 n(B) = plancher (300/5) = 60 n(C) = plancher (300/7) = 42 |
|
|
Les
nombres 3, 5 et 7 sont premiers entre eux Les
nombre divisibles par 3 et 5 le sont par 15; etc. |
|
|
|
Formule
inclusion-exclusion |
|
|
|
|
Commentaires Initialisation d'un compteur
(kt). Boucle d'analyse des nombres
n de 1 à 300. Si n est divisible par 3 ou
5 ou 7 alors incrémenter le compteur. Fin de boucle et imprimer la
valeur de kt. Ce programme Maple vérifie le calcul expliqué
ci-dessus. Autres fourchettes Pour n de 1 à 1000 : 543 10 000 : 5429 100 000 : 54286 1 000 000 : 542857 |
|
|
Exemple – Divisibilité par
3 ou 5 et pas par 7 |
|
|
|
Parmi les
nombres de 1 à 300 compris, combien sont-ils à être divisibles par 3 et par
5, mais pas par 7? |
= 20 -2 = 18 |
|
|
Divisible
par 5, mais pas par 3, ni par 7 |
= 60
– 20 – 8 +
2 = 34 |
|
|
|
||||
|
Formule Deux ensembles
A et B de cardinalité
m et n avec m Q est la
quantité de fonctions surjectives
de A sur B. |
|
|||
|
Exemple Combien
de possibilités de donner 4 bonbons différents
à trois enfants, chaque enfant recevant au moins un bonbon? |
A = ensembles des bonbons B = ensembles des enfants |
|||
|
Fonction de A sur B |
Donner un bonbon ai à un enfant
bj. Chaque enfant recevant un bonbon => la
fonction est surjective |
|||
|
Quantité |
= 81 – 3 x 16 + 3 x 1 = 81 – 48 + 3 = 36 |
|||
|
Explications |
Totalité des cas, les enfants recevant ou
pas des bonbons: 35 >>> Cas comportant avec enfants sans bonbons:
96 cas. Cas avec enfants ayant reçus 3 bonbons: 3. |
|||
|
Remarque |
Aves 5 bonbons identiques,
les trois enfants auraient d'abord reçus chacun 1 bonbon. Reste à distribuer
2 bonbons à 3 enfants. Soit 6 cas seulement. |
|||
|
Tableau montrant le décompte Les 36 cas demandés: distribution de 4 bonbons particuliers
(tous différents) à 3 enfants. (Équivalent à : distribution de 4 balles
numérotées dans 3 paniers numérotés). Exemple de lecture (première ligne
à gauche): |
|
|||
|
Suite du tableau: cas d'enfants
sans bonbons Les 45 cas où 1 des enfants au moins ne reçoit pas
de bonbon. Exemple de lecture (premières lignes
à gauche): Les
bonbons B1, B2, B3 et B4 sont donnés à l'enfant 1. En bleu:
ligne 1 à gauche: l'enfant 1 reçoit 4 bonbons, alors que l'enfant 2 comme
l'enfant 3 n'ont rien. |
|
|||
|
Cas de 5 bonbons pour 3 enfants |
= 243 – 3 x 32 + 3 x 1 = 243 – 96 + 3 = 150 |
|||
|
Cas de 6 bonbons pour 3 enfants |
= 729 – 3 x 64 + 3 x 1 = 729 – 192 + 3 =
540 |
|||
|
Suite |
|
|
Retour |
|
|
Voir |
|
|
|
