Pages

Dénombrement ( maths)

Dénombrement


1- Ensemble fini - Ensemble infini dénombrable


On dit que l'Ensemble E est fini s'il est bide, ou s'il existe un entier naturel n et une bijection de [  1,n ] dans E.
Si E  ≠ ∅, n est appelé Cardinal de E. On note CardE = n.
CardE = n si, et seulement si, les éléments de E peuvent être notés e1, e2,.....en ,
ou les ek sont deux distincts.
Par convention Card ∅ = 0.

* Dénombrer un ensemble fini non vide E, c'est déterminer le Cardinal de E, c'est à dire
le nombre de ses éléments.

plusieurs méthodes sont souvent possibles.

Par exemple, pour compter le nombre n d'élèves d'une classe E, on peut :

- soit compter les élèves un par un,
- soit effectuer des groupements: si n = 30, on peut avoir cinq rangées de six élèves ou six colonnes de cinq élèves.

Trois conditions doivent être remplies pour que le dénombrement de E soit correct:

1) Il ne faut compter que des éléments de E
2) Il ne faut pas en oublier.
3) Il ne faut pas compter certains éléments plusieurs fois.
Néamoins, si par une méthode chaque élément de E est compté k fois; CardE est le quotient par k du nombre obtenu par cette méthode.

* On dit que l'ensemble E est infini dénombrable s'il existe une bijection de N dans E. Les éléments de E peuvent alors être notés e0,e1,....en,... ou les ek sont deux à deux distincts.

Exemples 1

N est dénombrable
N* est dénombrable : bijection N → N*
                                n→ n+1
Z est dénombrable : bijection N → Z
                                       2n → -n
                                       2n+1 → n + 1
On peut démontrer que R n'est pas dénombrable
De même, un intervalle [  a,b ] (avec a < b ) n'est pas dénombrable.


2) Propriétés des cardinaux


Proposition 1
Soit E un ensemble fini. si F est un ensemble tel qu'il existe une bijection de E dans F, alors F est un ensemble fini et Card E= Card F.

Démonstration

Si E est fini de cardinal n, alors par définition, il existe une bijection φ de [[  1, n ]] dans E
Si f est une bijection de E dans F, on a alors f ° φ bijection de [[  1, n ]] dans F.
Par suite F est fini de cardinal n, donc CardE = CardF

Proposition 2
Soit E un ensemble fini.
Toute partie A de E est finie et Card A ≤ Card E.
Si A est une partie de E, A = E ⟺ Card A = Card E.
Application:
Soit A et B deux ensembles finis.Pour montrer que A = B, on peut :
-soit montrer que A ⊂ B et B ⊂ A,
-soit montrer que A ⊂ B et Card A = Card B.
Proposition 3
Soit A et B deux partie d'un ensemble fini E.
1) Si A et B sont disjointes, Card ( A ∪ B ) = Card A + Card B.
2) Card (A - B ) = Card A - Card ( A∩B)
3) Card A(bar)= Card E - Card A( A(bar) designe complémentaire de A dans E)
4) Card( A ∪ B) = Card A + Card B - Card ( A∩B).

Démonstration

1) Les éléments de A peuvent être notés a1,....,aq ou les a1 sont 2 à 2 distincts.
Les éléments de B peuvent être notés b1,....,bp ou les bj sont 2 à 2 distincts.
Comme A ∩ B  est vide, les ai sont distincts des bj, donc les éléments de A   B peuvent
être notés c1,....,c p+q avec  i ∈ [[  1, q ]] , ci = ai
et pour ∈ [[  q+1, q+p ]] , ci = bi-q
Les ci sont 2 à 2 distincts, donc Card (A ∪ B) = Card A + Card B.
2) Utiliser 1) et A = ( A- B) ∪ ( A∩ B) en remarquant que ( A - B) ∩ ( A∩ B) =
3) Abar = E - A
4) A ∪ B = ( A - B ) ∪ B et ( A - B ) ∩ B = ∅.
Proposition 4

Formule du crible ou de Poincaré.
Si ( Ai) 1 ≤ i ≤ n          est une famille de parties de l'ensemble fini E, alors






Conséquence : 

Si ( Ai) 1≤i≤n        est une partition de l'ensemble fini E, c'est-à-dire 


i=1nAi=Eet(i,j)[1n]2,ijAiAj=
Alors

CardE=i=1nCard(Ai)




Démonstration

* Démontrons la formule du crible dans le cas ou n=3.

Card ( A1 ∪ A2 ∪ A3 ) = Card ( A1 ∪ A2 ) + Card ( A3) - Card ( A1 ∪ A2)∩ A3
                      = Card ( A1) + Card (A2) - Card (A1 ∩ A2) + Card (A3) - Card ( ( A1 ∩ A3 ) ∪ ( A2 ∩ A3))
et Card ( A1∩A3) ∪ ( A2 ∩ A3 )) = Card ( A1 ∩ A3 ) +  Card (A2 ∩ A3) - Card ( A1 ∩ A2 ∩ A3)
Donc :
Card ( A1 ∪ A2 ∪ A3 ) = Card(A1) + Card ( A2) + Card(A3) - Card ( A1∩ A2) - Card(A1∩A3) - Card(A2∩A3) + Card(A1 ∩ A2 ∩ A3).
La formule du crible pour n quelconque se démontre par récurrence.
Si ( A1)1≤i≤n      est une partition de E, toutes les intersections intervenant dans la formule sont vides.
Donc on a :




Card(i=1nAi)=i=1nCard(Ai)


et Comme 

E=i=1nAi

on en déduit : 


CardE=i=1nCardAi



Proposition 5

Soit E et F deux ensembles finis, On a :

Card( E x F ) = ( CardE ) * ( CardF)

Démonstration 

Soient E = ( e1,.....,en) et F = ( f1,.....,fp)

E x F = ( (ei,fj) /1 ≤ i ≤ n,1 ≤ j ≤ p )
=i=1nAi

avec Ai = ( (ei,fj) / 1  j   p).


--------------------------

 Essentiel : 
Si l'on veut dénombrer un ensemble fini E
on peut reconnaîtra des p-listes, des arrangements, des combinaisons, des permutations.

Exercice:
Soit A l'ensemble des nombres à 6 chiffres ne comportant aucun 0.
Déterminer les cardinaux des ensembles suivants:
1) A/
2) A1, l'ensemble des nombres de A ayant 6 chiffres différents.
3) A2, ensemble des nombres pairs de A.
4) A3, ensemble des nombres de A dont les chiffres forment une suite strictement croissante ( dans l'ordre ou ils sont écrits).

Solution :
1) un élément de A est une 6-liste d'éléments de E {1,2,3,4,5,6,7,8,9}
CardE = 9 
donc : 

CardA=96
PS : les chiffres des nombres de A ne sont pas nécessairement différents et leur ordre a de l'importance.
2) un élément de A1 est un arrangement de 6 éléments de E.
donc
CardA1=A69=9!6!

3) un élément de A est pair si, et seulement si, son chiffre des unités est 2,4,6 ou 8.
Il y a 4 façons de choisir un tel chiffre, puis, pour chacune d'elles : 9^5 façons de choisir la 5-liste des 5 premiers chiffres.

Donc :

CardA2=4.95


Il y a    C_{9}^{6}{ }    façons de choisir les 6 chiffres d'un nombre de A3 puis, pour chacune d'elles,  1  façon de les écrire dans l'ordre croissant.
Donc CardA3 = Il y a  C_{9}^{6}{ }


Commentaire : les 5 chiffres sont différents et on les considère das un premier temps sans ordre.


Exercice :
On tire simultanément 5 cartes d'un jeu de 32 cartes.
a) Combien de tirages différents peut-on obtenir ?
b) Combien de tirages différents peut-on obtenir contenant :
  1) 5 carreaux ou 5 coeurs :
  2) 2 coeurs et 3 piques
  3) au mois 1 roi :
  4) au plus 1 roi:;
  5) 2 rois et 3 coeurs:

Solution:
a) Un tirage est une combinaison de 5 cartes prises parmi 32. il y a donc n = C_{32}^{5}{ } = 201 376 tirages différents.
On aurait pu écrire aussi: il y a 32 façons de choisir une carte parmi 32, puis, pour chacune d'elles, 31 façons de choisir une 2Ecarte,puis, .... puis 28 façons de choisir la 5eme carte. Mais en procédant ainsi chaque tirage est obtenu dans tous les ordres possibles et donc compté 5! fois, d'ou

n=32x31x30x29x285!

b) On note ni le nombre de tirages correspondant à la i(ème) question.
1) ni = nombre de tirages contenant 5 carreaux
                                                       + nombre de tirages contenant 5 coeurs.
Un tirage contenant 5 carreaux est une combinaison de 5 cartes prises parmi les 8 carreaux; il y a donc C_{8}^{5}{ }tirages contenant 5 carreaux. On a le même résultat pour 5 coeurs. Donc : n1 = 2C_{8}^{5}{ } = 112.

2) Il y a C_{8}^{2}{ } façons de choisir une combinaison de 2 coeurs pris parmi 8 puis, pour chacune d'elles, C_{8}^{3}{ }façons de choisir une combinaison de 3 piques pris parmi 8. Donc  n2= C_{8}^{2}{ } X C_{8}^{3}{ }= 1568.
3)
1e méthode : n3 = \sum_{k=1}^4{}mk ou mk désigne le nombre de tirages contenant exactement k rois.

il y a C_{8}^{k}{ }façons de choisir une combinaison de k rois pris parmi 4 puis, pour chacune d'elles, C_{32-4}^{5-k}{ } combinaisons de ( 5 - k ) cartes prises parmi les ( 32 - 4 ) cartes qui ne sont pas des rois.
Donc mk = C_{4}^{k}{ }C_{28}^{5-k}{ }  et n3 =  \sum_{k=1}^{}C_{4}^{k}{ }C_{28}^{5-k}{ } = 103 096.

Attention : le raisonnement suivant est incorrect!!
Il ya 4 façons de choisir 1 roi, puis chacune d'elles, C_{31}^{5}{ } façons de choisir une combinaison de 4 cartes prises parmi les 31 restantes/
D'ou : n3 = 4C_{31}^{4}{ }
En effet, par exemple, le tirage contenant le roi de trèfle, le roi de pique et les 7,8 et 9 de coeurs est compté 2 fois.
1e fois : choix du roi de trèfle, puis choix du complément.
2e fois: choix du roi de pique,puis choix du complément,
Alors que par exemple le tirage constitué du roi de trèfle et des 7,8,9,10 de coeur n'est compté qu'une fois.
4) Avec la notation du 3), n4 =    \sum_{k=0}^{1}mk   = \sum_{k=0}^{1}C_{4}^{k}{ }C_{28}^{5-k}{ } , d'ou   n4 = C_{28}^{5}{ } + 4C_{28}^{4}{ } = 180 180.

5) n5 = n'5 + n''5 ou n'5 ( resp. n''5 ) est le nombre de tirages répondant à 5) contenant le roi de coeur ( resp. ne contenant pas le roi de coeur).
Il y a 3 façons de choisir 2 rois dont le roi de coeur puis, pour chacune d'elles, C_{7}^{2}{ } façons de choisir une combinaison de 2 coeurs différents du roi de coeur, puis, pour chacune d'elles C_{7}^{3}{ }
façons de choisir une combinaison de 3 coeurs pris parmi les 7 coeurs différents du roi de coeur.
Donc : n''5 = C_{3}^{2}{ }C_{7}^{3}{ }.
Finalement n5 = 3 x C_{7}^{2}{ } x 21 +  C_{3}^{2}{ }C_{7}^{3}{ } = 1428.



- On peut scinder E en plusieurs parties E1 .... Ep

Si E1,...., Ep sont 2 à 2 disjointes,  CardE = \sum_{i=1}^{p}CardEi ;
sinon, utiliser la formule du crible.
Voir Exercice 2 et 4

- On peut dénombrer le complémentaire de E
Voir exercice 2, et 4

- On peut détailler les étapes qui permettraient d'écrire tous les éléments de E. S'il y a p étapes et si pour chacune d'elles il y a nk choix possibles ce nombre de choix étant indépendant des choix précédents, alors E contient n1 x n2 x ... x np éléments.
Voir exercices 1, 2 et 3.
Si au cours du dénombrement, chaque élément de E est compté k fois, ne pas oublier de diviser le résultat final par k .
voir exercice 2 .

Exercice 3 :   Il faut ranger une étagère 4 livres de mathématiques distincts, 6 livres de philosophie distincts et 2 livres de géographie distincts.
De combien de façons peut-on effectuer ce rangement dans les cas suivants :
1) Les livres doivent être groupés par matières.
2) Les livres de mathématiques seulement doivent être groupés.

Solution :
1) Pour ranger les 12 livres, je choisis l'ordre des 3 groupes de livres ( 3! choix possibles ),puis pour chacun de ces choix, il y a 4! façons de ranger les livres de mathématiques entre eux, puis 6! façons de ranger les livres de philosophie et 2! façons de ranger les livres de géographie.

Donc  n1 = 3!4!6!2! .
2 ) Il ya 9 façons de choisir le nombre de livres rangés avant ceux de mathématiques, puis pour chacun de ces choix, 4! façons de ranger les livres de mathématiques, puis 8! façons de ranger les autres livres entre eux .
Donc  n2 = 9 x 4!8! .

Commentaire :
Il peut y avoir 0,1,....8 livres placés avant ceux de mathématiques.
On peut également choisir la place du 1er livre de mathématiques, qui peut être 1,2,......,9 il y a donc 9 choix.


Exercice 4 :  Dans une entreprise, il y a 800 employés. 300 sont des hommes, 352 sont d'un syndicat, 424 sont mariés, 188 sont des hommes syndiqués, 166 sont des hommes mariés, 208 sont syndiqués et mariés, 144 sont des hommes mariés syndiqués.
Combien y a-t-il de femmes célibataires non syndiquées ?

Solution :
Notions E , H, M , S les ensembles constitués respectivement des employés, des employés hommes, des employés mariés, des employés syndiqués.
L'énoncé donne :

CardE = 800 , CardH= 300 , CardS = 352 , CardM = 424
Card ( H \cap S ) = 188 , Card ( H \cap M ) = 166  , Card ( S \cap M) = 208,
Card ( H \cap M \cap S ) = 144 .

On cherche Card ( H(bar) \cap M(bar) \cap S(bar) )

H(bar) \cap M(bar) \cap S(bar) = \overline{H\cup M \cup S}

D'après la formule du crible,
Card ( H \cup M \cup S ) = CardH + CardM + CardS - Card ( H \cap M ) - Card( H \cap S ) - Card ( M \cap S ) + Card ( H \cap M \cap S ).

D'ou


Card ( H \cup M \cup S )  = 300 + 424 + 352 - 166 - 188 - 208 + 144 = 658.

et  Card ( H(bar) \cap M(bar) \cap S(bar) ) = 800 - 658 = 142.

Il y a donc 142 femmes célibataires et non syndiquées.

Commentaire : Dans ce type d'exercice la 1er chose à faire est de donner un nom à chacun des ensembles ( de base ) qui apparaissent, puis d'exprimer les autres en fonction de ceux-ci.



95