Se connecter Inscription gratuite
L'appli tout-en-un pour réviser
4.8 • +11k évaluations
Plus de 3 millions de téléchargements
Télécharger
|
|
Combinatoire et dénombrement

T'es-tu déjà demandé quelles sont les chances de gagner à la loterie ? Pour répondre à cette question, nous devons connaître le nombre de résultats possibles. La réponse n'est pas si compliquée qu'elle ne paraît, il faut tout simplement étudier la thématique de combinatoire et dénombrement. Dans ce résumé de cours, nous allons d'abord présenter la notion de dénombrement. Par…

Content verified by subject matter experts
Free StudySmarter App with over 20 million students
Mockup Schule

Explore our app and discover over 50 million learning materials for free.

Combinatoire et dénombrement

Combinatoire et dénombrement

Sauvegarde ce cours maintenant et relis-le quand tu auras le temps.

Sauvegarder
Illustration

Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken

Jetzt kostenlos anmelden

Nie wieder prokastinieren mit unseren Lernerinnerungen.

Jetzt kostenlos anmelden
Illustration

T'es-tu déjà demandé quelles sont les chances de gagner à la loterie ? Pour répondre à cette question, nous devons connaître le nombre de résultats possibles. La réponse n'est pas si compliquée qu'elle ne paraît, il faut tout simplement étudier la thématique de combinatoire et dénombrement. Dans ce résumé de cours, nous allons d'abord présenter la notion de dénombrement. Par la suite, nous rentrerons dans les détails du dénombrement dans trois situations : les arrangements, les permutations et les combinaisons. À la fin, tu pourras mobiliser tes connaissances avec quelques exercices de dénombrement.

Dénombrement

Le dénombrement consiste à déterminer le nombre d'éléments dans un ensemble fini. Un ensemble fini est un ensemble dont le cardinal est fini.

Cardinal d'un ensemble

Le cardinal d'un ensemble est le nombre d'éléments qu'il contient. Nous pouvons noter le cardinal d'un ensemble \(E\) comme \(\text{card(E)}\), \(\#E\) ou encore \(|E|\).

Le cardinal de l'ensemble \(\{2,3,4,10,11\}\) est \(5\). Il s'agit donc d'un ensemble fini.

Le cardinal de l'ensemble \(\{-\infty, +\infty\}\) est \(2\). Il s'agit également d'un ensemble fini.

Il y a deux principes clés du dénombrement dont tous les autres découlent : le principe additif et le principe multiplicatif. Le principe additif du dénombrement précise que le cardinal d'une réunion d'ensembles disjoints est la somme des cardinaux de ces ensembles. Autrement dit, si \(E_1, E_2, ..., E_n\) est une famille d'ensembles deux à deux disjoints, alors \[\text{card}(E_1 \cup ... \cup E_n) = \text{card}(E_1) + ... + \text{card}(E_n)\]

Considère les ensembles \(E_1 = \{2,3,4\}\), \(E_2 = \{-\infty, +\infty\}\) et \(E_3 = \{a,b,c,d\}\).

Comme il s'agit d'ensembles disjoints, nous pouvons appliquer le principe additif.

Les cardinaux des ensembles sont \(\text{card}(E_1) = 3\), \(\text{card}(E_2) = 2\) et \(card(E_3) = 4\)

Ainsi, le cardinal de l'ensemble \(E_1 \cup E_2 \cup E_3\) est \(3+2+4 = 9\)

Pour énoncer le principe multiplicatif du dénombrement, il est d'abord nécessaire de définir le produit cartésien d'ensembles.

Produit cartésien

Le produit cartésien de deux ensembles contient tous les couples composés d'éléments de deux ensembles.

Le produit cartésien de deux ensembles \(A\) et \(B\) est \(A \times B = \{(a,b) | a \in A, b \in B\}\).

Considère les ensembles \(A = \{1,0\}\) et \(B = \{x, y\}\). Leur produit cartésien \(A \times B\) contient les éléments \((1,x)\), \((1,y)\), \((2,x)\) et \((2,y)\).

L'ordre est important pour le produit cartésien. L'ensemble \(A \times B\) n'est pas le même que l'ensemble \(B \times A\). Cela est logique comme le point \((0,1)\) n'est pas le même que le point \((1,0)\). De plus, nous pouvons définir le produit cartésien de plusieurs ensembles.

Le produit cartésien des ensembles \(E_1, ..., E_n\) est \(E_1 \times ... \times E_n = \{(e_1, ..., e_n | e_1 \in E_1, ... ,e_n \in E_n\}\). L'élément \((e_1, ..., e_n)\) est appelé un n-uplet.

Nous pouvons alors énoncer le principe multiplicatif du dénombrement. Il précise que le cardinal du produit cartésien d'ensembles est le produit des cardinaux de ces ensembles. \[\text{card}(E_1 \times ... \times E_n) = \text{card}(E_1) \times ... \times \text{card}(E_n)\]

Considère les ensembles \(E_1 = \{2,3,4\}\), \(E_2 = \{-\infty, +\infty\}\) et \(E_3 = \{a,b,c,d\}\).

Les cardinaux des ensembles sont \(\text{card}(E_1) = 3\), \(\text{card}(E_2) = 2\) et \(card(E_3) = 4\)

Ainsi, le cardinal de l'ensemble \(E_1 \times E_2 \times E_3\) est \(3 \times 2 \times 4 = 24\)

Le principe multiplicatif du dénombrement nous permet de compter (ou plutôt calculer) le nombre de permutations d'un ensemble.

Arrangement en maths

Un arrangement en maths est une sélection ordonnée d'objets, où la répétition n'est pas permise.

RAT est un arrangement de lettres dans le mot ARRANGEMENT.

Nous pouvons définir un arrangement plus rigoureusement à l'aide des informations présentées dans la section précédente sur le produit cartésien.

Soient \(n\) et \(p\) des entiers naturels tels que \(1 \leq p \leq n\). Un arrangement de \(p\) éléments de \(E\) est un p-uplet d'éléments distincts de \(E\).

Pour compter le nombre d'arrangements, nous exploitons le principe multiplicatif du dénombrement. Soit \(E\) un ensemble dont le cardinal est \(n\). Après avoir sélectionné le premier élément de l'arrangement, il nous reste \(n-1\) choix, car il n'y a pas de répétition permise dans un arrangement. De même, après avoir sélectionné le deuxième élément de l'arrangement, il nous reste \(n-2\) choix. Si nous continuons ainsi, après le (p-1)-ième élément, il y a donc \(n-(p-1) = n-p +1\) choix pour le p-ième et dernier élément de l'arrangement. D'où, le nombre d'arrangements de p éléments d'un ensemble de cardinal \(n\) est : \[n \times n-1 \times ... \times n-p +1\] L'expression ci-dessus peut être reformulée à l'aide des factorielles.

La factorielle d'un entier naturel \(n\) est égale à \(n \times n-1 \times ... \times 1\). Elle se note \(n!\).

Pour en connaître plus sur la factorielle d'un nombre, n'hésite pas à consulter notre résumé de cours à ce sujet.

Si tu veux calculer la factorielle de \(5\), il faut faire le produit \(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\)

Nous obtenons donc une autre expression pour le nombre d'arrangements de \(p\) éléments d'un ensemble de cardinal \(n\) : \[\frac{n!}{(n-p)!}\]

Pour jouer à la loterie, il faut choisir cinq numéros sur une grille de 49 numéros et un numéro complémentaire parmi dix. Peux-tu calculer le nombre de résultats possibles à la loterie ?

Pour les numéros non-complémentaires, il s'agit d'un arrangement où \(n = 49\) et \(p = 5\).

Il y a donc \(\frac{49!}{(49-5)!} = \frac{49!}{44!} = 228826080\) arrangements de cinq numéros.

Pour prendre en compte le numéro complémentaire, il faut utiliser le principe de multiplication du dénombrement. Comme il y a dix possibilités pour le numéro complémentaire, il y a \(10 \times 228826080 = 2288260800\) résultats possibles du loto.

Pour un arrangement en maths, l'ordre est important et nous ne pouvons pas répéter des éléments. Une permutation est un type spécial d'arrangement.

Permutation en maths

Une permutation est un arrangement de tous les éléments dans un ensemble.

ART est une permutation de RAT.

Nous pouvons en déduire le nombre de permutations à l'aide de la formule pour le nombre d'arrangements. Il faut remplacer \(p\) avec \(n\) : \[ \frac{n!}{(n-n)!} = \frac{n!}{0!}\] Or, \(0! = 1\).

Un site internet requiert à ses clients d'avoir un mot de passe composé de tous les chiffres entre 0 et 9 compris. Chaque chiffre ne doit apparaître qu'une seule fois dans le mot de passe. Saurais-tu calculer le nombre de mots de passe possibles ?

Chaque mot de passe serait une permutation des chiffres entre 0 et 9. Comme il y a dix chiffres, il peut y avoir \(10! = 3628800\) mots de passe possibles.

Pour les arrangements et les permutations, l'ordre est important. Alors, qu'en est-il si l'ordre nous indiffère ? Dans ce cas, il s'agirait plutôt d'une combinaison.

Combinaisons

Une combinaison est une sélection de \(k\) éléments parmi \(n\). L'ordre des éléments n'est pas important.

Soient \(n\) et \(k\) des entiers naturels tels que \(1 \leq k \leq n\). Une combinaison de \(k\) éléments est un sous-ensemble de \(E\).

BON est une combinaison des lettres de COMBINAISON.

Pour déterminer le nombre de combinaisons, nous utilisons la formule suivante : \[ \binom{n}{k} = \frac{n!}{k!(n-k)!} \] Le symbole \( n \choose k\) se lit « \(k\) parmi \(n\) ». Il se note également \(C^k_n\)

Imagine que tu dois constituer un groupe de cinq personnes pour travailler sur un devoir commun. S'il y a \(30\) personnes dans ta classe, combien de façons y-a-t-il pour former le groupe ?

Si tu dois former une équipe de cinq personnes et tu fais partie du groupe en plus, alors \(k\) correspond à \(4\).

Comme il y a \(30\) personnes dans la classe, alors \(n\) correspond à \(29\).

Appliquons maintenant la formule pour le nombre de combinaisons.

\( \binom{29}{4} = \frac{29!}{4!25!} = 23751\)

Il y a donc \(23751\) façons pour former le groupe.

Les principes du dénombrement servent à resoudre de nombreux problèmes. Il faut donc savoir identifier si le contexte contient un arrangement, une permutation ou une combinaison à l'aide de divers exercises de dénombrement.

Exercices de dénombrement

Voici quelques exercices de dénombrement qui t'aideront à pratiquer les différents concepts abordés dans ce résumé de cours. Les corrigés de ces exercices sont fournis dans les flashcards associés en bas de page.

Il sera parfois nécessaire d'appliquer plusieurs concepts à un problème pour pouvoir le résoudre. De plus, tu devrais relire l'énoncé pour bien comprendre ce qui est demandé.

1. Combien il y a d'arrangements de trois lettres distinctes du mot ARRANGEMENT ?

2. Dans ta cuisine, il y a du poulet, du boeuf, du poisson, des épinards, des courgettes, des asperges, des tomates, du riz et des pâtes. Pour créer un plat équilibré, tu choisiras une viande, un légume et un féculent. Combien de possibilités de plats y-a-t-il ?

3. Trouve le nombre d'agencements possibles avec les lettres du mot LICORNE sans séparer les voyelles.

4. À chaque cours de maths ton professeur choisit trois élèves au hasard pour les interroger à l'oral. S'il y a 30 élèves dans ta classe, quelle est la probabilité qu'il t'interroge ?

( Tu trouveras les réponses dans la série de flashcards ci-dessous ! )

Combinatoire et dénombrement - Points clés

  • Le combinatoire et le dénombrement concerne les diverses méthodes utilisées pour déterminer le cardinal d'un ensemble fini.
  • Il y a deux principes clés du dénombrement :
    • le principe additif : pour une famille d'ensembles deux à deux disjoints \(E_1, E_2, ..., E_n\), nous avons \(\text{card}(E_1 \cup ... \cup E_n) = \text{card}(E_1) + ... + \text{card}(E_n)\) ;
    • le principe multiplicatif : pour une famille d'ensembles quelconques \(\text{card}(E_1 \times ... \times E_n) = \text{card}(E_1) \times ... \times \text{card}(E_n)\)
  • Un arrangement en maths est une liste ordonnée d'objets non-répétés. Le nombre d'arrangements de \(p\) éléments d'un ensemble de cardinal \(n\) est donné par \(\frac{n!}{(n-p)!}\).
  • Une permutation est un arrangement qui contient chaque élément d'un ensemble. Le nombre d'arrangements d'un ensemble de cardinal \(n\) est donné par \(n!\).
  • Une combinaison est un choix non-ordonné de \(k\) éléments parmi \(n\). Le nombre de combinaisons de \(k\) éléments d'un ensemble de cardinal \(n\) est donné par \( \binom{n}{k} = \frac{n!}{k!(n-k)!} \)

Questions fréquemment posées en Combinatoire et dénombrement

Pour calculer le nombre de combinaisons, nous utilisons la formule n!/(k!(n-k)!), où n! = 1*2*...*n

Le but du dénombrement est de déterminer le nombre d'éléments dans un ensemble donné, qui est souvent utile dans le calcul de probabilités.

Le dénombrement consiste à déterminer le nombre d'éléments dans un ensemble. 

Pour comprendre l'analyse combinatoire, il faut d'abord apprendre les principes additifs et multiplicatifs du dénombrement. Même s'il y a des formules plus sophistiquées, la majorité des problèmes de combinatoire peuvent être résolus à l'aide de ces principes de base. 

Évaluation finale de Combinatoire et dénombrement

Combinatoire et dénombrement Quiz - Teste dein Wissen

Question

Qu'est-ce que le dénombrement ?

Montrer la réponse

Réponse

Le dénombrement consiste à déterminer le nombre d'éléments dans un ensemble fini.

Montrer la question

Question

Qu'est-ce que le cardinal d'un ensemble ? 

Montrer la réponse

Réponse

Le cardinal d'un ensemble est le nombre d'éléments qu'il contient. Nous pouvons noter le cardinal d'un ensemble \(E\) comme \(\text{card(E)}\), \(\#E\) ou encore \(|E|\)

Montrer la question

Question

Quel est le principe additif du dénombrement ?

Montrer la réponse

Réponse

Le principe additif du dénombrement précise que le cardinal d'une réunion d'ensembles disjoints est la somme des cardinaux de ces ensembles. Autrement dit, si \(E_1, E_2, ..., E_n\) est une famille d'ensembles deux à deux disjoints, alors \[\text{card}(E_1 \cup ... \cup E_n) = \text{card}(E_1) + ... + \text{card}(E_n)\]

Montrer la question

Question

Quel est le principe multiplicatif du dénombrement ? 

Montrer la réponse

Réponse

Le principe multiplicatif précise que le cardinal du produit cartésien d'ensembles est le produit des cardinaux de ces ensembles. \[\text{card}(E_1 \times ... \times E_n) = \text{card}(E_1) \times ... \times \text{card}(E_n)\] 

Montrer la question

Question

Qu'est-ce que le produit cartésien de deux ensembles ? 

Montrer la réponse

Réponse

Le produit cartésien de deux ensembles \(A\) et \(B\) est \(A \times B = \{(a,b) | a \in A, b \in B\}\). 

Montrer la question

Question

Donne la définition d'un arrangement. 

Montrer la réponse

Réponse

Soient \(n\) et \(p\) des entiers naturels tels que \(1 \leq p \leq n\). Un arrangement de \(p\) éléments de \(E\) est un p-uplet d'éléments distincts de \(E\). 

Montrer la question

Question

Qu'est-ce qu'une permutation ? 

Montrer la réponse

Réponse

Une permutation est un arrangement de tous les éléments dans un ensemble.

Montrer la question

Question

Donne la définition d'une combinaison.

Montrer la réponse

Réponse

Soient \(n\) et \(k\) des entiers naturels tels que \(1 \leq k \leq n\). Une combinaison de \(k\) éléments est un sous-ensemble de \(E\). 

Montrer la question

Question

Quelle formule faut-il utiliser pour calculer le nombre d'arrangements de \(p\) objets parmi \( n\) ?

Montrer la réponse

Réponse

\(\frac{n!}{(n-p)!}\)

Montrer la question

Question

Quelle formule faut-il utiliser pour calculer le nombre de combinaisons de \(k\) objets parmi \(n\) ?

Montrer la réponse

Réponse

\( \binom{n}{k} = \frac{n!}{k!(n-k)!} \)

Montrer la question

Question

Quelle formule faut-il utiliser pour calculer le nombre de permutations de \(n\) objets ?

Montrer la réponse

Réponse

\(n!\) 

Montrer la question

Question

Trouve le nombre de façons que nous pouvons réordonner les lettres du mot LICORNE sans séparer les voyelles.

Montrer la réponse

Réponse

Puisque les voyelles doivent rester collées, nous pouvons les considérer comme un bloc. 


Comme il y a trois voyelles, il y a \(3! = 6\) permutations des lettres dans ce bloc. 


Comme il y a quatre consonnes et un bloc de voyelles, il y a donc \(5! = 120\) permutations de ces éléments.


Nous utiliserons enfin le principe multiplicatif pour trouver le nombre de façons de réordonner les lettres de LICORNE : \(6 \times 120 = 720\)

Montrer la question

Question

Chaque cours de maths ton professeur choisit trois élèves au hasard pour les interroger à l'oral. Quelle est la probabilité qu'il t'interrogera ?

Montrer la réponse

Réponse

Pour calculer cette probabilité, nous pouvons calculer le nombre de combinaisons de trois élèves quelconques et le nombre de combinaisons de trois élèves avec toi. 


Le nombre de combinaisons de trois élèves quelconques est \( \binom{30}{3} = \frac{30!}{3!27!} = 4060\)


Calculer le nombre de combinaisons de trois élèves où nous avons déjà décidé qu'un(e) élève sera inclus(e) revient à déterminer le nombre de combinaisons avec un(e) élève de moins \(\binom{29}{2} = \frac{29!}{2!27!} = 406\) 


La probabilité qu'il t'interrogera est donc \(\frac{1}{10}\)

 

Montrer la question

Question

Dans ta cuisine, il y a du poulet, du boeuf, du poisson, des épinards, des courgettes, des asperges, des tomates, du riz et des pâtes. Pour créer un plat équilibré, tu choisiras une viande, un légume et un féculent. Combien de possibilités de plats y-a-t-il ?

Montrer la réponse

Réponse

Ici, nous utilisons le principe multiplicatif.


En effet, il y a trois possibilités pour la viande, quatre pour le légume et deux pour le féculent. 


Il y a donc \(3 \times 4 \times 2 = 24\) possibilités. 

Montrer la question

Question

Combien il y a d'arrangements de trois lettres distinctes du mot ARRANGEMENT ?

Montrer la réponse

Réponse

Il y a sept lettres distinctes dans ce mot. 


Il y a donc \(\frac{7!}{3!} = \frac{49!}{44!} = 840\) arrangements de cinq numéros.

Montrer la question

AUTRES THÈMES LIÉS Combinatoire et dénombrement
60%

des utilisateurs ne réussissent pas le test de Combinatoire et dénombrement ! Réussirez-vous le test ?

lancer le quiz

How would you like to learn this content?

Creating flashcards
Studying with content from your peer
Taking a short quiz

How would you like to learn this content?

Creating flashcards
Studying with content from your peer
Taking a short quiz

Free mathematiques cheat sheet!

Everything you need to know on . A perfect summary so you can easily remember everything.

Access cheat sheet

Complète tes cours avec des thèmes et sous-thèmes disponibles pour chaque matière!

Inscris-toi gratuitement et commence à réviser !

StudySmarter: la seule application d’apprentissage qu’il te faut pour tout savoir.

Inscris-toi ici gratuitement
Illustration