Combinatoire et dénombrement
I- Principe additif et multiplicatif :
1) Ensemble fini et cardinal :
Définition :
Soit n un entier naturel.
Lorsqu’un ensemble E a n éléments, on dit que E est un ensemble fini.
Le nombre d’éléments de E est appelé cardinal de E et noté Card E
Ex : L’ensemble des voyelles de l'alphabet est l'ensemble : E a ; e ; i ; o ; u ; y . Il a 6 éléments.
On a donc : Card E 6 .
Remarques :
Card 0
Certains ensembles ne sont pas finis : l’ensemble des entiers naturels , l’ensemble des réels ,
l’intervalle 0;1 , …etc.
2) Principe additif :
Propriété :
Si A1 , A2 , …, Ap sont p ensembles finis deux à deux disjoints, alors :
Card A1 A2 Ap Card A1 Card A2 Card Ap
Cas particuliers :
Soient A une partie d’un ensemble fini E et A le complémentaire de A
dans E .
On a :
Card A Card E Card A
En effet :
A et A son disjoints donc Card A A Card A Card A
Or A A E d’où Card E Card A Card A
On en déduit que : Card A Card E Card A
D’après la propriété précédente, siA et B sont 2 parties disjointes, on a :
Card A B Card A Card B
Mais, dans le cas général, on a :
Card A B Card A Card B Card A B
En effet : A B est la réunion des ensembles disjoints A et B A donc :
Card A B Card A Card B A
B est la réunion des ensembles disjoints B A et B A donc :
Card B Card B A Card B A d’où Card B A Card B Card B A
On en déduit que : Card A B Card A Card B Card A B
3) Principe multiplicatif :
Définition et propriété :
On considère E et F deux ensembles non vides.
Le produit cartésien de E par F , noté E F , est l’ensemble des couples x ; y avec x E et
yF .
Lorsque les ensembles E et F sont finis, on a : Card E F Card E Card F
Remarque : Card E F Card E Card F
désigne le produit Multiplication
cartésien de 2 entiers
(se lit E croix F )
Ex : Soient E a ; b ; c et F 1; 2 ;
E F a ;1 ; a ; 2 ; b ;1 ; b ; 2 ; c ;1 ; c ; 2
F E 1; a ; 2; a ; 1; b ; 2; b ; 1; c ; 2; c
On vérifie bien que : Card E F Card F E 2 3 6
On généralise cette notion de produit cartésien à plus de deux ensembles :
Définition :
On considère k un entier supérieur ou égal à 2 et E1 , E2 , …, Ek k ensembles non vides.
Toute liste ordonnée x 1 ; x2 ;; xk avec xi Ei pour i allant de 1 à k est appelée :
k -uplet (ou k -liste).
Remarque :
un 2 -uplet est un couple un 3 -uplet est un triplet
Propriété :
Le produit cartésien E1 E2 Ek , est l’ensemble des k -uplets x1 ; x2 ;; xk avec xi Ei
pour i allant de 1 à k .
Lorsque les ensembles E1 , E2 , …, Ek sont finis, on a :
Card E1 E2 Ek Card E1 Card E2 Card Ek
II- k -uplets d’un ensemble fini :
1) Nombre de k -uplets d’un ensemble fini :
Définition :
Soit k un entier naturel et E un ensemble non vide.
Un k -uplet ou k -liste d’éléments de E est une liste ordonnée x1 ; x2 ; ; xk de k éléments de E ,
distincts ou non.
L’ensemble de tous les k -uplets de E
E est le produit cartésien
E E . On le note E k .
k fois
Ex : a ; c ; e ; a ; m ; p ; e est un 7 -uplet de E 7 où E est
l'ensemble des 26 lettres E a ; b ; c ;; z .
Ex : Etablir la liste des triplets de l’ensemble E a ; b
On peut s’aider d’un arbre.
Les triplets de E sont donc : a ; a ; a , a ; a ; b , a ; b ; a ,
a ; b ; b , b ; a ; a , b ; a ; b , b ; b ; a , b ; b ; b .
Ils sont au nombre de 8 .
Propriété :
Si E est un ensemble fini de cardinal n .
Le nombre de k -uplets de E k est : n k
En effet :
Card E k Card E Card E Card E Card E Card E
k
E
E
k fois k fois
Ex :
1) Combien de mots de trois lettres (ayant un sens ou non) peut-on former à l’aide des lettres A, E, I, O
et U ?
2) Une grille est quadrillée avec 60 carreaux rectangulaires. On colorie chaque carreau en rouge, vert ou
bleu. Combien de grilles différentes peut-on ainsi réaliser ?
3) Les numéros de téléphones commençant par 06 sont constitués du couple 0;6 que l’on complète
par un 8 -uplet de l’ensemble 0;1; 2;;9 .
a- Déterminer le nombre de numéros de téléphone possibles commençant par 06 .
b- Combien de numéros de téléphone commençant par 06 ou 07 sont possibles ?
Cela revient à chercher le nombre de 3 -uplets dans l’ensemble A ; E ; I ; O ;U à 5 éléments
Il y en a : 53 125 .
Cela revient à chercher le nombre de 60 -uplets dans l’ensemble rouge ; vert ; bleu à 3 éléments.
Il y en a : 360 .
Le nombre de numéros de téléphone commençant par 06 est donc le nombre de 8 -uplet dans
l’ensemble 0;1; 2;;9 à 10 éléments.
Il y en a : 108 .
De la même façon, il y a 108 numéros de téléphone commençant par 07
Par le principe additif, il y a donc 108 108 2 108 numéros de téléphones commençant par 06
ou 07 .
2) k -uplets distincts d’un ensemble fini :
Ex : Prenons les lettres a , b , c , d , e et f . On note E a ; b ; c ; d ; e ; f .
a ; b ; c ; d , a ; c ; f ; e , c ; e ; b ; f … sont des 4 -uplets d’éléments distincts de E .
Quel est le nombre de 4 -uplets d’éléments distincts de E possibles ?
case 1 case 2 case 3 case 4
Liste : Le nombre de choix
possibles est :
6 5 4 3 360
6 choix 5 choix 4 choix 3 choix
possibles possibles possibles possibles
Propriété :
Soit n un entier naturel et k un entier naturel tel que 1 k n .
Le nombre de k -uplets d’éléments distincts d’un ensemble E à n éléments est :
n n 1 n k 1
Démonstration :
Choisir un k -uplet d’éléments distincts de E revient à remplir k cases avec des éléments distincts de E .
Il y a n choix pour la 1ère case.
Un choix étant fait, il y a n 1 choix pour la 2
ème
case.
Il y a donc n n 1 choix pour remplir les cases 1 et 2.
…
Les cases 1 , 2 , … k 1 étant complétées, il reste pour la k ème case : n k 1 n k 1 choix.
Le nombre de k -uplets d’éléments distincts de E est donc : n n 1 n k 1
Ex :
Une compétition de jeux vidéo en ligne oppose six joueurs.
A la fin, un classement est établi et il n’y a pas d’ ex æquo. Le meilleur joueur reçoit une médaille d’or, le
deuxième une médaille d’argent et le troisième une médaille de bronze.
Combien y a-t-il de podiums possibles ?
On note E l’ensemble des 6 joueurs : E J1 ; J 2 ; J 3 ; J 4 ; J 5 ; J 6 .
Comme il n’y a pas d’ex æquo, un podium correspond à un triplet d’éléments distincts de l’ensemble E
à 6 éléments.
Il y a 6 choix possibles pour la médaille d’or, puis 5 pour la médaille d’argent et 4 pour la médaille de
bronze.
Il y a donc 6 5 4 120 podiums possibles.
3) Permutations :
Définition :
On considère E un ensemble fini à n éléments.
Une permutation des éléments de E est un n -uplet d’éléments distincts de E.
Remarque : lister toutes les permutations de E , c’est écrire tous les éléments de E dans tous les ordres
possibles.
Ex : Les permutations de l'ensemble E a ; b ; c sont :
a ; b ; c , a ; c ; b , b ; a ; c , b ; c ; a , c ; a ; b et c ; b ; a .
Propriété et définition :
Le nombre de permutations d’un ensemble fini à n éléments est :
n n 1 2 1
On note ce nombre n ! (qui se lit "factorielle n " ou " n factorielle")
On a donc : n ! n n 1 2 1 .
Par convention : 0! 1
Ex :
1) Combien peut-on former de mots (ayant un sens ou non) de sept lettres distinctes avec des lettres du
mot « produit ».
2) Parmi ces mots, combien commencent par une voyelle ?
« produit » ayant 7 lettres, chercher tous les mots que l’on peut former avec ces 7 lettres revient à
chercher toutes les permutations des lettres du mot « produit ».
On peut en former 7! 7 6 2 1 5 040 .
Parmi les mots obtenus il y a ceux qui commencent par une voyelle « o », « u » ou « i ».
Dans chacun des trois cas, il faut compléter les six dernières lettres du mot par les six lettres restantes,
ce qui constitue à chaque fois une permutation de six lettres :
Il y a donc 6! 6 2 1 720 façon de le faire.
Le nombre de mots commençant par une voyelle est donc 3 6! 3 720 2160 .
voyelle 2ème lettre 3ème lettre 4ème lettre 5ème lettre 6ème lettre 7ème lettre
3 choix 6 choix 5 choix 4 choix 3 choix 2 choix 1 choix
possibles possibles possibles possibles possibles possibles possible
6 5 ... 3 2 1 6 ! choix
III- Parties d’un ensemble et combinaisons :
1) Nombre de parties d’un ensemble :
Définition :
Une partie F de E est un ensemble d’éléments de E .
On dit aussi que F est un sous-ensemble de E ,
ou bien que F est inclus dans E (et on note F E ).
Remarques :
L’ordre n’intervient pas : a ; b b ; a
Il n’y a pas de répétition : a ; a a
Ex : Cherchons le nombre de parties de l’ensemble E a ; b ; c .
Partie à 0 élément :
Parties à a ; b ; c .
1 éléments :
Parties à 2 éléments : a ; b ; b ; c ; a ; c .
Parties à 3 éléments : a ; b ; c .
Il y a donc 8 parties de l’ensemble E a ; b ; c .
Propriété :
Soit n un entier naturel.
Le nombre de parties d’un ensemble à n éléments est égal au nombre de n -uplets de l’ensemble
0;1 , c’est-à-dire : 2 .n
Remarque : Dans l’exemple précédent, on a bien dénombré 23 8 parties de l’ensemble E a ; b ; c
à 3 éléments.
Démonstration :
Soit E x1 ; x2 ;; xn un ensemble à n éléments.
A chaque partie A de E correspond un unique n -uplet de l’ensemble 0;1 , et inversement.
En effet :
Si x1 appartient à A , on affecte 1 en 1ère position du n -uplet et 0 sinon.
Si x2 appartient à A , on affecte 1 en 2ème position du n -uplet et 0 sinon.
…
Si xn appartient à A , on affecte 1 en n ème position du n -uplet et 0 sinon.
Par exemple, le n -uplet 1; 0 ;1; 0; ; 0 correspond à la partie x1 ; x3 .
le n -uplet 1;1; ;1 correspond à E x1 ; x2 ;; xn .
le n -uplet 0 ; 0 ; ; 0 correspond à .
Ainsi, il y a autant de parties de l’ensemble E que de n -uplets de l’ensemble 0;1 , c’est-à-dire : 2n .
2) Combinaisons :
Définition :
Soit E est un ensemble à n éléments et k un entier naturel tel que : 0 k n .
On appelle combinaison de k éléments de E , toute partie (ou sous-ensemble) de E ayant k
éléments.
Ex : E a ;b ;c .
Les combinaisons de 2 éléments de E sont les parties : a ; b , b ; c ; a ; c .
3) Nombre de combinaisons :
Définition :
n
Le nombre de combinaison de k éléments d’un ensemble à n éléments est noté :
k
et se lit « k parmi n ».
Remarque : D’après l’exemple précédent, le nombre de parties à 2 éléments parmi l’ensemble E à 3
3
éléments est 3 donc 3 .
2
Propriété :
Pour tout entier n1 , et tout entier k tel que : 0 k n , on a :
n n n 1 n k 1 n!
.
k k! k ! n k !
En effet :
n! n n 1 2 1 n n 1 n k 1 n k n k 1 2 1
k ! n k ! k ! n k n k 1 2 1 k ! n k n k 1 2 1
n! n n 1 n k 1
Donc, on a bien :
k ! n k ! k!
Cas particuliers :
Dans un ensemble E x1 ; x2 ;; xn à n éléments :
n
Il y a n parties à 1 élément ( x1 , x2 ,… xn ) : n .
1
n
Il y a 1 partie à n éléments (l’ensemble E lui-même) : 1.
n
n
Il y a 1 partie à 0 élément (l’ensemble vide) : 1.
0
n n n 1 n n 1
Le nombre de parties à 2 éléments est :
2 2! 2
8 6
Ex : A l’aide de la formule, calculer et .
3 4
8 8 7 6 8 7 6 6 65 4 3 6 5 43 65
8 7 56 et 15
3 3! 3 2 1 4 4! 4 3 2 1 2
Calcul du nombre de combinaisons à la calculatrice :
20
Calculer à l’aide de la calculatrice
12
Casio Graph 35+ Ti 83
puis et puis et
Ex : Dans un jeu de 32 cartes, une « main » est constituée de 5 cartes.
1) Combien y a-t-il de mains possibles ?
2) Combien de mains contiennent le valet de pique ?
Le nombre de mains de 5 cartes dans ce jeu de 32 cartes est le nombre de combinaisons à 5
éléments dans un ensemble à 32 . (éléments choisis sans ordre et sans répétition).
32
Le nombre de mains possibles est : 201376 .
5
4 cartes dans les 31 restantes pour
Le valet de pique étant choisi, il ne reste plus qu’à choisir
31
constituer une main. Le nombre de mains cherché est donc : 31465 .
4
Propriété :
n
n n n n
Pour tous entiers naturels n , on a : 2
n
k 0 k 0 1 n
Démonstration : (exigible)
n
Par définition, pour tout entier k tel que 0 k n , est le nombre de combinaison de k éléments de
k
E , ensemble fini à n éléments.
n
n
Ainsi, d’après le principe additif, k est égal au nombre total de parties de E (les parties de 0 à n
k 0
éléments).
Or, on a vu que le nombre total de parties de E est 2n . (voir paragraphe III)1) )
n
n
Par conséquent : 2 .
k
n
k 0
4) Symétrie des nombres de combinaisons :
Propriété :
n n
Pour tous entiers naturels n et k tels que 0 k n , on a :
k n k
10 10
Ex : .
7 3
Il y a donc autant de façons de choisir 7 objets parmi 10 que 3 objets parmi 10 .
5
Ex : Sans calculatrice, calculer pour tout entier k tel que 0 k n .
k
5 5
1 ; 1
0 5
5 5
5 ; Par symétrie : 5
1 4
5 5 4 20 5
1 0 ; Par symétrie : 1 0
2 2 2 3
5) La relation de Pascal :
Propriété : Relation de Pascal
n n 1 n 1
Pour tous entiers naturels n et k tels que 0 k n 1 , on a :
k k 1 k
Démonstration : (exigible)
E est un ensemble à n éléments. On note a un élément fixé de E .
Pour dénombrer les parties à k éléments de E , on peut distinguer les parties qui contiennent a et celles
qui ne contiennent pas cet élément :
Parties ne contenant pas a :
Ce sont les parties à k éléments de E choisis parmi les n1 éléments de E , différents de a .
n 1
Il y en a : .
k
Parties contenant a :
Puisque l’élément a est déjà choisi, il reste à choisir k 1 éléments parmi les n1 éléments différents
n 1
de a . Il y en a : .
k 1
D’après le principe additif, on en déduit que le nombre de parties à k éléments de E est :
n 1 n 1
.
k 1 k
n
E est aussi :
Par définition, le nombre de parties à k éléments de
k
n n 1 n 1
On en déduit donc que :
k k 1 k
6) Le triangle de Pascal
n
On peut calculer les de proche en proche à l’aide du triangle de Pascal :
k
n
A l’intersection de la ligne n et de la colonne k , on lit la valeur de .
k
0
Par convention, on pose 1.
0
n
1 pour toute entier n , on commence par écrire des « 1 » sur la 1 colonne.
ère
Comme
0
n
Comme 1 pour toute entier n , on commence par écrire des « 1 » sur la diagonale.
n
n 1 n 1
k 1 k
On utilise la relation de Pascal pour compléter le « reste » du tableau :
n
k
