Dénombrer un ensemble fini , c'est calculer son cardinal , le nombre de ses éléments, sans les écrire un par un. Pour choisir éléments parmi , deux questions décident de la formule : l'ordre compte-t-il, et un même élément peut-il revenir ? Avec ordre et répétition, on obtient listes ; avec ordre et sans répétition (), arrangements ; sans ordre ni répétition (), combinaisons. Exemple : parmi 13 candidats, on désigne un délégué et son suppléant de façons, mais deux représentants de même rôle de façons seulement.
Accès direct :
- résumé de cours en un tableau,
- principe fondamental du dénombrement,
- arrangements,
- combinaisons,
- triangle de Pascal,
- tirages,
- binôme de Newton.
Pour s'entraîner : les exercices corrigés de dénombrement, avec un problème type devoir surveillé.
Chapitre du semestre 2 de la 1re année du baccalauréat sciences mathématiques (option française BIOF), après la géométrie analytique de l'espace : il n'existe qu'en 1 bac SM, les sciences expérimentales ne rencontrent le dénombrement qu'en 2e année. Il utilise le vocabulaire des ensembles et applications (réunion, complémentaire, bijection) et le raisonnement par récurrence.
Sommaire11 parties
Résumé de cours : dénombrement en un tableau
est un ensemble fini à éléments, , , des parties de , et un entier naturel. Le lien de la première colonne mène à la section correspondante.
| Notion | À retenir |
|---|---|
| Réunion | |
| Trois ensembles | on ajoute les trois cardinaux, on retranche les trois intersections deux à deux, on ajoute le cardinal de l'intersection des trois |
| Principe fondamental du dénombrement | choix successifs à , …, possibilités, nombres indépendants des choix précédents : |
| Applications, parties | applications d'un ensemble à éléments dans un ensemble à éléments a éléments |
| Arrangements avec répétition | ordre compté, répétition permise, tout : |
| Arrangements sans répétition | ordre compté, sans répétition, : |
| Permutations | avec répétition : où |
| Combinaisons | parties à éléments, : |
| Symétrie et relation de Pascal | , pour , pour |
| Tirages | simultané () : ; successif sans remise () : ; successif avec remise (tout ) : |
| Binôme de Newton | pour : |
Ensembles finis et cardinal
Ensemble fini et cardinal
Un ensemble est fini s'il est vide ou s'il existe un entier et une bijection de sur : on numérote ses éléments de 1 à . L'entier est le cardinal de , noté , et . Deux ensembles finis ont le même cardinal lorsqu'il existe une bijection de l'un sur l'autre (admis) : compter , c'est souvent le mettre en bijection avec un ensemble plus simple à compter.
Cardinal d’une réunion, d’un complémentaire et d’une différence
Pour toutes parties et d'un ensemble fini :
- ;
- si , ;
- et, si , .
Démonstration : cardinal d’une réunion de deux ensembles
On admet le cas disjoint : en numérotant les éléments de puis ceux de , on numérote ceux de . Le complémentaire en découle, car est la réunion disjointe de et . Dans le cas général, est la réunion disjointe de et de , et celle de et de . Donc et . On remplace par dans la première égalité. Enfin, si , alors et la seconde égalité donne .
Exemple 1 : deux clubs dans une classe
Une classe de 1 bac SM compte 34 élèves : 19 sont inscrits au club d'échecs , 13 au club de robotique , et 6 aux deux. Le nombre d'élèves inscrits à au moins un club est
Il reste élèves sans club, et élèves font seulement des échecs.
Cardinal de la réunion de trois ensembles
Pour toutes parties , , d'un ensemble fini (formule de Poincaré) :
Démonstration : formule de Poincaré pour trois ensembles
On applique la formule de deux ensembles à et :
D'une part . D'autre part, par distributivité, , et l'intersection de ces deux parties est , donc . On remplace ces deux cardinaux dans l'égalité précédente.
Exemple 2 : entiers divisibles par 3, 4 ou 5
Dans , soient , , les multiples de 3, de 4 et de 5. Comme 3, 4, 5, 12, 15, 20 et 60 divisent 300, l'ensemble des multiples de a éléments. Les entiers multiples à la fois de 3 et de 4 sont les multiples de leur PPCM 12 ; de même, , et sont formés des multiples de 15, 20 et 60. Donc
Ainsi entiers de ne sont divisibles ni par 3, ni par 4, ni par 5.
Principe fondamental du dénombrement et produit cartésien
Principe fondamental du dénombrement
Une situation se décompose en choix successifs. Le premier choix se fait de façons ; puis, quel que soit ce premier choix, le deuxième se fait de façons, et ainsi de suite jusqu'au dernier, de façons. Le nombre total de résultats est alors . On l'appelle aussi principe multiplicatif et on le visualise par un arbre de choix.
En particulier, pour des ensembles finis et , le produit cartésien vérifie , et plus généralement .
Les possibilités d'une étape peuvent changer selon la branche de l'arbre ; seul leur nombre doit rester le même.
Exemple 3 : étiquettes des casiers d’un lycée
Une étiquette de casier est formée d'une lettre de A à F, suivie de deux chiffres distincts pris de 1 à 9 (par exemple C47). On choisit la lettre (6 façons), le premier chiffre (9 façons), puis le second parmi les 8 chiffres restants. Les chiffres restants dépendent du premier choix, mais leur nombre vaut toujours 8 :
Nombre d’applications et nombre de parties
Applications d’un ensemble fini dans un autre
- Si et , avec et , le nombre d'applications de dans est .
- Si , l'ensemble des parties de a éléments.
Démonstration : nombre d’applications et nombre de parties
Numérotons . Une application est déterminée par le choix de dans ( façons), puis de ( façons), jusqu'à : le principe multiplicatif donne . Pour les parties, on associe à chaque partie de l'application qui vaut 1 sur et 0 hors de . Cette correspondance est une bijection : une application de dans provient de la seule partie . Donc . Pour , a bien élément.
Exemple 4 : quatre élèves et six clubs
Le lycée propose 6 clubs. Quatre élèves choisissent chacun un club : un choix global est une application de l'ensemble des 4 élèves dans celui des 6 clubs, d'où possibilités. Si les quatre clubs choisis doivent être distincts, on compte les applications injectives : . Un élève qui peut s'inscrire à autant de clubs qu'il veut choisit une partie de l'ensemble des clubs : choix, la partie vide (aucun club) et l'ensemble des six clubs compris.
Arrangements avec répétition et sans répétition
Arrangements avec répétition (p-listes)
Soit un ensemble à éléments et . Un arrangement avec répétition de éléments de est une liste ordonnée d'éléments de , non nécessairement distincts. C'est un élément de : il y en a , et peut dépasser .
Factorielle d’un entier naturel
Pour , (« factorielle »), et l'on pose . Pour , ; par exemple .
Arrangements sans répétition
Soit . Un arrangement de éléments de est une liste ordonnée de éléments distincts de , autrement dit une application injective de dans . Leur nombre est
Le produit a facteurs décroissants à partir de . On pose .
Démonstration : nombre d’arrangements sans répétition
Le premier élément de la liste se choisit de façons ; quel que soit ce choix, le deuxième se choisit parmi les autres, et ainsi de suite : le -ième se choisit parmi les éléments non encore utilisés. Le principe multiplicatif donne . En multipliant et en divisant par , on complète le produit jusqu'à 1, d'où .
Exemple 5 : cadenas de vélo à quatre molettes
Chacune des 4 molettes d'un cadenas porte les chiffres 1 à 7. Un code est une liste ordonnée de 4 chiffres où un chiffre peut revenir : codes. Si l'on impose 4 chiffres distincts, ce sont des arrangements sans répétition : codes.
Permutations simples et permutations avec répétition
Permutations d’un ensemble fini
Une permutation d'un ensemble à éléments () est un arrangement de tous ses éléments : une façon de les ranger en ligne, ou encore une bijection de sur . Il y en a .
Exemple 6 : aligner les onze joueurs d’une équipe
Les 11 joueurs d'une équipe de football s'alignent pour la photo : alignements. Si le capitaine et le gardien doivent être côte à côte, ils forment un bloc : on range 10 objets, puis les deux joueurs dans le bloc, soit alignements.
Permutations avec répétition et anagrammes
On range en ligne objets de types : objets identiques du premier type, …, du dernier, avec . Le nombre de rangements distincts est
En effet, si l'on numérote les objets pour les distinguer, on obtient rangements. Chaque rangement sans numéros est alors obtenu fois, en permutant entre eux les objets d'un même type.
Exemple 7 : anagrammes de OUARZAZATE
Le mot OUARZAZATE a 10 lettres : trois A, deux Z, et O, U, R, T, E une fois chacune. Le nombre de mots de 10 lettres, ayant un sens ou non, formés avec exactement ces lettres est
Combinaisons : choisir une partie sans ordre
Combinaisons d’un ensemble à n éléments
Soit . Une combinaison de éléments de est une partie de à éléments : l'ordre n'intervient pas et il n'y a pas de répétition. Leur nombre est
On a (la partie vide et ) et (les singletons). On rencontre aussi la notation .
Démonstration : nombre de combinaisons
Soit . On fabrique un arrangement de éléments en deux étapes : on choisit la partie de ses éléments ( façons), puis on range cette partie en ligne ( façons). Chaque arrangement est obtenu une seule fois, car sa partie est l'ensemble de ses termes. Le principe multiplicatif donne . Pour , la formule donne , le nombre de parties vides.
Exemple 8 : commission ou bureau dans une classe de 17 élèves
Une commission de 3 élèves aux rôles identiques est une partie de la classe :
Un bureau formé d'un président, d'un secrétaire et d'un trésorier, trois élèves distincts, est une liste ordonnée : .
Symétrie, relation de Pascal et triangle de Pascal
Symétrie et relation de Pascal
- Pour : .
- Pour : (relation de Pascal).
Démonstration : symétrie et relation de Pascal
Symétrie : si a éléments, en a . L'application , des parties à éléments dans les parties à éléments, est une bijection : sa réciproque est , car le complémentaire du complémentaire d'une partie est cette partie. Les deux ensembles de parties ont donc le même cardinal. Pascal, pour , avec et , puis on réduit au même dénominateur :
Triangle de Pascal
La ligne donne , , …, , la colonne (en-tête de la table) contenant ; chaque nombre qui n'est pas au bout de sa ligne est la somme du nombre situé juste au-dessus et du voisin de gauche de ce dernier : c'est la relation .
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| 0 | 1 | ||||||
| 1 | 1 | 1 | |||||
| 2 | 1 | 2 | 1 | ||||
| 3 | 1 | 3 | 3 | 1 | |||
| 4 | 1 | 4 | 6 | 4 | 1 | ||
| 5 | 1 | 5 | 10 | 10 | 5 | 1 | |
| 6 | 1 | 6 | 15 | 20 | 15 | 6 | 1 |
Exemple 9 : lire et contrôler une valeur du triangle
Par symétrie, , et la relation de Pascal le confirme : . La somme de la ligne 6 vaut : on a compté les parties d'un ensemble à 6 éléments selon leur nombre d'éléments.
Tirages avec ou sans remise et tirages simultanés
On tire objets parmi objets discernables (boules numérotées, jetons, cartes). Le mode de tirage fixe l'objet que l'on compte.
Choisir le bon outil de dénombrement
Trois questions, posées dans cet ordre, donnent la formule :
- L'ordre compte-t-il ? Non : on choisit une partie, .
- Oui, et l'on range tous les objets : permutation, , ou si certains objets sont identiques.
- Oui, et l'on n'en prend que : avec répétition ; sans répétition , avec .
| Situation : ordre ? répétition ? | Nombre |
|---|---|
| tirages successifs avec remise : ordre oui, répétition oui | |
| tirages successifs sans remise, : ordre oui, répétition non | |
| rangement de tous les objets : ordre oui, répétition non | |
| tirages simultanés, : ordre non, répétition non | |
| rangement de tous les objets, , …, identiques entre eux |
Exemple 10 : huit jetons numérotés, trois modes de tirage
Un sac contient 8 jetons numérotés de 1 à 8 (quatre pairs, quatre impairs). On tire 3 jetons et l'on compte les tirages qui donnent exactement deux numéros pairs.
- Simultané : un tirage est une partie à 3 éléments, tirages. On choisit 2 pairs et 1 impair : .
- Successif sans remise : un tirage est un arrangement, . On choisit le rang de l'impair (3 façons), les deux pairs dans l'ordre (), puis l'impair (4) : .
- Successif avec remise : une liste avec répétition, . Même découpage : .
Contrôle : chaque tirage simultané se range de façons, d'où et .
Formule du binôme de Newton
Énoncé de la formule du binôme
Pour tous réels et et tout entier :
Les coefficients forment la ligne du triangle de Pascal. Avec , on obtient ; avec et , .
Démonstration : formule du binôme par récurrence
On raisonne par récurrence sur .
- Initialisation : pour , .
- Hérédité : soit un entier fixé tel que (hypothèse de récurrence). On écrit et l'on remplace grâce à l'hypothèse de récurrence : Dans la seconde somme, on pose ( va de 1 à ), puis on renomme en : elle devient . Le terme n'apparaît que dans la première somme et vaut ; le terme n'apparaît que dans la seconde et vaut ; pour , le coefficient de est par la relation de Pascal. Comme , on obtient la formule au rang .
- Conclusion : la formule est vraie pour tout entier .
Exemple 11 : développer une puissance cinquième
On prend , et la ligne 5 du triangle : 1, 5, 10, 10, 5, 1.
Contrôle avec : .