Algèbre & Combinatoire · Fiche N°7 / 110

Dénombrement avec contraintes et restrictions

Définition, méthode rigoureuse, exemples corrigés et exercice type BAC.

📚 Terminale Spécialité Maths ⏱ Lecture : 5 min ✅ Programme officiel BO 2019

Définition

Le dénombrement est l'art de compter le nombre d'éléments d'un ensemble fini. Lorsqu'il y a des contraintes ou des restrictions, il s'agit de déterminer le nombre de façons de choisir ou d'ordonner des éléments en respectant des conditions spécifiques (par exemple, des éléments distincts, un ordre précis, des répétitions autorisées ou non). Les outils principaux sont les arrangements, les combinaisons et les permutations, souvent combinés avec le principe multiplicatif ou additif.

💡 Bon réflexe : Avant de calculer, posez-vous toujours ces deux questions : 'L'ordre est-il important ?' et 'Les répétitions sont-elles autorisées ?' pour choisir la bonne formule.
Contrainte : éléments distincts,ou répétitions autoriséesSans répétition : Aₙᵖ = n!/(n−p)!Avec répétition : nᵖSous-ensembles sans ordre :Sans répétition : CₙᵖAvec répétition : Cₙ₊ₚ₋₁ᵖ

Méthode — Dénombrement avec contraintes et restrictions

1

1. Identifier la nature du problème

Déterminer si l'ordre des éléments est important et si les répétitions sont autorisées. Cela permet de choisir l'outil de dénombrement approprié :

  • Si l'ordre est important et les répétitions sont autorisées : $n^k$ (nombre de $k$-uplets).
  • Si l'ordre est important et les répétitions ne sont pas autorisées : arrangements $A_n^k = \frac{n!}{(n-k)!}$ ou permutations $n!$ (cas $k=n$).
  • Si l'ordre n'est pas important et les répétitions ne sont pas autorisées : combinaisons $\binom{n}{k} = \frac{n!}{k!(n-k)!}$.

2

2. Décomposer le problème en étapes ou en cas

Si le problème est complexe, le diviser en sous-problèmes plus simples. Utiliser le principe multiplicatif si les étapes sont successives et indépendantes (le nombre total de possibilités est le produit des possibilités de chaque étape). Utiliser le principe additif si le problème peut être résolu par plusieurs cas disjoints (le nombre total de possibilités est la somme des possibilités de chaque cas).

3

3. Appliquer les formules de dénombrement

Pour chaque étape ou cas, appliquer la formule de dénombrement identifiée à l'étape 1. Par exemple, si l'on doit choisir 3 personnes parmi 10 pour former un comité (ordre non important), on utilisera $\binom{10}{3}$.

4

4. Gérer les contraintes et restrictions

Les contraintes peuvent réduire l'ensemble des choix possibles ou imposer un ordre.

  • Contraintes d'inclusion/exclusion : Si un élément doit être présent, on le choisit d'abord, puis on dénombre les autres. Si un élément ne doit pas être présent, on le retire de l'ensemble de départ.
  • Contraintes d'ordre : Si certains éléments doivent être adjacents ou dans un ordre particulier, on peut les considérer comme un seul 'bloc' à permuter.
  • Contraintes de position : Si des éléments doivent occuper des positions spécifiques, on fixe ces positions et on dénombre les autres.

5

5. Vérifier la cohérence et la validité

S'assurer que toutes les conditions du problème ont été prises en compte et qu'il n'y a pas de double comptage ou d'omission. Une bonne pratique est de tester avec un petit nombre d'éléments si possible.

Exemple résolu

Une association doit élire un bureau composé d'un président, d'un secrétaire et d'un trésorier. Il y a 12 membres, dont 5 femmes et 7 hommes. On souhaite déterminer le nombre de bureaux possibles sous différentes contraintes.

1
Calculer le nombre total de bureaux possibles sans contrainte.
Le bureau est composé de 3 personnes avec des fonctions distinctes (président, secrétaire, trésorier). L'ordre est donc important et les répétitions ne sont pas possibles (une personne ne peut pas occuper deux postes). Il s'agit d'un arrangement de 3 personnes parmi 12. $A_{12}^3 = \frac{12!}{(12-3)!} = 12 × 11 × 10 = 1320$. Il y a 1320 bureaux possibles.
2
Calculer le nombre de bureaux où le président est une femme.
Il y a 5 femmes. Le président doit être une femme. Il y a 5 choix pour le président. Une fois le président choisi, il reste 11 membres pour les 2 postes restants (secrétaire et trésorier). L'ordre est important. C'est un arrangement de 2 personnes parmi 11. Le nombre de bureaux est $5 × A_{11}^2 = 5 × (11 × 10) = 5 × 110 = 550$. Il y a 550 bureaux où le président est une femme.
3
Calculer le nombre de bureaux où il y a exactement deux hommes.
Il y a 3 postes. Si exactement deux hommes sont élus, cela signifie qu'il y a une femme et deux hommes.
  • Étape 1 : Choisir les 2 hommes parmi 7. L'ordre n'est pas important pour le choix des personnes, donc $\binom{7}{2} = \frac{7 × 6}{2} = 21$ façons.
  • Étape 2 : Choisir la 1 femme parmi 5. $\binom{5}{1} = 5$ façons.
  • Étape 3 : Attribuer les postes aux 3 personnes choisies. Une fois les 3 personnes (2 hommes, 1 femme) choisies, il faut leur attribuer les 3 postes distincts. Il y a $3! = 3 × 2 × 1 = 6$ façons de les répartir.
Par le principe multiplicatif, le nombre de bureaux est $21 × 5 × 6 = 630$. Il y a 630 bureaux avec exactement deux hommes.
4
Calculer le nombre de bureaux où le président et le trésorier sont de sexe différent.
On peut décomposer en deux cas disjoints :
  • Cas 1 : Président homme et Trésorier femme. Il y a 7 choix pour le président (homme) et 5 choix pour le trésorier (femme). Il reste 10 membres pour le poste de secrétaire. Donc $7 × 5 × 10 = 350$ bureaux.
  • Cas 2 : Président femme et Trésorier homme. Il y a 5 choix pour le président (femme) et 7 choix pour le trésorier (homme). Il reste 10 membres pour le poste de secrétaire. Donc $5 × 7 × 10 = 350$ bureaux.
Par le principe additif, le nombre total de bureaux est $350 + 350 = 700$. Il y a 700 bureaux où le président et le trésorier sont de sexe différent.

En appliquant les principes de dénombrement et en gérant les contraintes, nous avons trouvé : 1320 bureaux sans contrainte, 550 bureaux avec une femme présidente, 630 bureaux avec exactement deux hommes, et 700 bureaux avec président et trésorier de sexe différent.

⚠️ Piège fréquent au BAC — Ordre et Répétition

  1. Confondre arrangement et combinaison : l'ordre est-il important ? Si oui, arrangement ($A_n^k$) ou permutation ($n!$). Si non, combinaison ($\binom{n}{k}$).
  2. Oublier de considérer les répétitions : si les répétitions sont autorisées, les formules changent (souvent $n^k$).
  3. Double comptage ou omission de cas : s'assurer que les cas sont disjoints lors de l'utilisation du principe additif et que toutes les possibilités sont couvertes.
  4. Mal appliquer le principe multiplicatif : il s'applique uniquement si les choix sont indépendants à chaque étape.

Exercice type BAC

Un code PIN est composé de 4 chiffres. Les chiffres peuvent être répétés.

  1. Combien de codes PIN différents peut-on former ?
  2. Combien de codes PIN contiennent au moins un chiffre '0' ?
  3. Combien de codes PIN sont composés de 4 chiffres distincts ?
  4. Combien de codes PIN sont composés de 4 chiffres distincts et contiennent le chiffre '7' ?

  1. Chaque chiffre peut être choisi parmi 10 possibilités (0 à 9). Puisque les chiffres peuvent être répétés et l'ordre est important (un code 1234 est différent de 4321), il s'agit d'un $4$-uplet de 10 éléments.

    Le nombre de codes PIN est $10 × 10 × 10 × 10 = 10^4 = 10000$.

  2. Pour trouver le nombre de codes PIN contenant au moins un chiffre '0', il est plus simple de calculer le nombre total de codes PIN (question 1) et de soustraire le nombre de codes PIN qui ne contiennent aucun chiffre '0'.

    • Nombre total de codes PIN : $10^4 = 10000$.
    • Nombre de codes PIN ne contenant aucun '0' : Chaque chiffre doit être choisi parmi les 9 chiffres restants (1 à 9). Donc $9 × 9 × 9 × 9 = 9^4 = 6561$.

    Le nombre de codes PIN contenant au moins un '0' est $10000 - 6561 = 3439$.

  3. Les 4 chiffres doivent être distincts et l'ordre est important. Il s'agit d'un arrangement de 4 chiffres parmi 10.

    Le nombre de codes PIN est $A_{10}^4 = 10 × 9 × 8 × 7 = 5040$.

  4. Les 4 chiffres doivent être distincts et le code doit contenir le chiffre '7'.

    • Étape 1 : Placer le chiffre '7'. Le chiffre '7' peut être placé à 4 positions différentes (1ère, 2ème, 3ème ou 4ème). Il y a 4 choix pour la position du '7'.
    • Étape 2 : Choisir et placer les 3 autres chiffres. Les 3 autres chiffres doivent être distincts entre eux et distincts de '7'. Il reste 9 chiffres possibles (0, 1, 2, 3, 4, 5, 6, 8, 9). L'ordre est important pour ces 3 chiffres. Il s'agit d'un arrangement de 3 chiffres parmi les 9 restants. $A_9^3 = 9 × 8 × 7 = 504$.

    Par le principe multiplicatif, le nombre de codes PIN est $4 × 504 = 2016$.

Questions fréquentes

Quelle est la différence entre un arrangement et une combinaison ?
La différence fondamentale est l'importance de l'ordre. Un arrangement ($A_n^k$) est un choix de $k$ éléments parmi $n$ où l'ordre compte (par exemple, un podium 1er, 2ème, 3ème). Une combinaison ($\binom{n}{k}$) est un choix de $k$ éléments parmi $n$ où l'ordre ne compte pas (par exemple, un groupe de 3 personnes pour un comité).
Quand utilise-t-on le principe multiplicatif et le principe additif ?
Le principe multiplicatif est utilisé lorsque le processus de dénombrement peut être décomposé en une séquence d'étapes indépendantes. Le nombre total de façons est le produit du nombre de façons pour chaque étape. Le principe additif est utilisé lorsque le problème peut être résolu en considérant plusieurs cas disjoints. Le nombre total de façons est la somme du nombre de façons pour chaque cas.
Comment gérer les contraintes de répétition ?
Si les répétitions sont autorisées et l'ordre est important, le nombre de façons de choisir $k$ éléments parmi $n$ est $n^k$. Si les répétitions ne sont pas autorisées, on utilise les arrangements ($A_n^k$) ou les combinaisons ($\binom{n}{k}$) selon que l'ordre est important ou non.
Qu'est-ce qu'une permutation ?
Une permutation est un arrangement de tous les éléments d'un ensemble. Si on a $n$ éléments distincts, le nombre de façons de les ordonner est $n!$ (factorielle $n$). C'est un cas particulier d'arrangement où $k=n$, donc $A_n^n = n!$.

Pour aller plus loin

Vous bloquez sur ce chapitre ?

Adil accompagne les lycéens en Terminale Spécialité, en ligne ou à domicile dans le Val d'Oise. Résultats en 1 séance.

📞 Appeler Cours Terminale →