Combinatoire et dénombrement

Le principe additif, aussi appelé règle de la somme, s'applique lorsque l'on peut choisir une option parmi plusieurs ensembles d'options, et que ces ensembles sont mutuellement exclusifs (c'est-à-dire qu'ils n'ont aucun élément en commun).

Key Concepts:

• Union d'ensembles disjoints: Si un événement peut se produire de $n_1$ façons ou de $n_2$ façons, et que ces façons sont incompatibles (on ne peut pas choisir des options des deux ensembles en même temps), alors le nombre total de façons est $n_1 + n_2$.
• Cas mutuellement exclusifs: Des événements sont mutuellement exclusifs si la réalisation de l'un empêche la réalisation de l'autre.
• Règle de la somme: Si une tâche peut être effectuée de $k$ manières distinctes, et que la $i$-ème manière peut être réalisée de $n_i$ façons différentes, et que toutes ces manières sont mutuellement exclusives, alors le nombre total de façons d'effectuer la tâche est $n_1 + n_2 + \dots + n_k$.

Un étudiant peut choisir un projet d'informatique parmi 3 sujets proposés, ou un projet de mathématiques parmi 4 sujets proposés. Combien de choix de projets a-t-il en tout ? Les choix sont mutuellement exclusifs (on ne peut pas faire un projet qui est à la fois info et maths). Nombre total de choix = $3 \text{ (info)} + 4 \text{ (maths)} = 7$ choix.

Le principle multiplicatif, ou règle du produit, est utilisé lorsque l'on effectue une séquence de choix indépendants.

Key Concepts:

• Séquence de choix indépendants: Si une tâche se compose de plusieurs étapes successives, et que le nombre de façons d'effectuer chaque étape ne dépend pas des choix faits aux étapes précédentes, alors le nombre total de façons d'effectuer la tâche est le produit du nombre de façons de réaliser chaque étape.
• Produit cartésien: Ce principe est lié à la taille du produit cartésien de plusieurs ensembles. Si on a un ensemble $A$ de $n_A$ éléments et un ensemble $B$ de $n_B$ éléments, alors le nombre de paires $(a, b)$ où $a \in A$ et $b \in B$ est $n_A \times n_B$.
• Règle du produit: Si une procédure peut être décomposée en $k$ étapes successives, et s'il y a $n_1$ façons d'effectuer la première étape, $n_2$ façons d'effectuer la deuxième étape (indépendamment du premier choix), ..., et $n_k$ façons d'effectuer la $k$-ième étape, alors le nombre total de façons d'effectuer la procédure est $n_1 \times n_2 \times \dots \times n_k$.

Un restaurant propose 3 entrées, 5 plats principaux et 2 desserts. Combien de menus différents peut-on composer si l'on choisit une entrée, un plat et un dessert ? Choix d'entrée : 3 options Choix de plat : 5 options Choix de dessert : 2 options Nombre total de menus = $3 \times 5 \times 2 = 30$ menus différents.

Les diagrammes en arbre et les tableaux sont des outils visuels très utiles pour représenter et organiser les différentes possibilités, surtout lorsque le nombre de choix n'est pas trop grand.

Key Concepts:

• Visualisation des choix: Ces outils permettent de voir toutes les combinaisons possibles étape par étape.
• Chemins possibles: Dans un diagramme en arbre, chaque "chemin" de la racine aux feuilles représente une séquence unique de choix.
• Organisation des résultats: Les tableaux sont particulièrement efficaces pour les situations à deux étapes, tandis que les arbres sont plus polyvalents pour un nombre d'étapes quelconque.

Exemple de diagramme en arbre (simplifié) : On lance une pièce de monnaie deux fois. Quelles sont les issues possibles ?

• 1er lancer : Pile (P) ou Face (F)
• 2ème lancer (après P) : Pile (P) ou Face (F)
• 2ème lancer (après F) : Pile (P) ou Face (F)

        Début
       /     \
      P       F
     / \     / \
    P   F   P   F

Les chemins possibles sont : (P, P), (P, F), (F, P), (F, F). Il y a $2 \times 2 = 4$ issues possibles.

On lance deux dés à six faces et on s'intéresse à la somme.

Une permutation est une disposition de tous les éléments d'un ensemble dans un certain ordre.

Key Concepts:

• Ordre des éléments: L'ordre dans lequel les éléments sont arrangés est important. Par exemple, ABC est différent de ACB.
• Arrangement de n objets distincts: Le nombre de façons d'ordonner $n$ objets distincts est donné par la factorielle de $n$.
• Factorielle n!: Pour un entier naturel $n$, la factorielle de $n$, notée $n!$, est le produit de tous les entiers positifs inférieurs ou égaux à $n$. $n! = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1$ Par convention, $0! = 1$.

De combien de façons différentes peut-on organiser 3 livres distincts sur une étagère ? Les livres sont A, B, C. Les arrangements possibles sont : ABC, ACB, BAC, BCA, CAB, CBA. Il y a $3! = 3 \times 2 \times 1 = 6$ façons.

Lorsque certains objets ne sont pas distincts (il y a des répétitions), la formule des permutations simples doit être ajustée.

Key Concepts:

• Objets non distincts: Si, parmi $n$ objets, il y a $n_1$ objets identiques d'un premier type, $n_2$ objets identiques d'un deuxième type, ..., $n_k$ objets identiques d'un $k$-ième type (où $n_1 + n_2 + \dots + n_k = n$), alors le nombre de permutations distinctes est réduit.
• Formule de permutation avec répétitions: Le nombre de permutations distinctes de $n$ objets dont $n_1$ sont identiques, $n_2$ sont identiques, ..., $n_k$ sont identiques est : $\frac{n!}{n_1! n_2! \dots n_k!}$
• Exemples concrets (mots, anagrammes): Cette formule est souvent utilisée pour calculer le nombre d'anagrammes d'un mot.

Combien d'anagrammes peut-on former avec les lettres du mot "MATHS" ? Toutes les lettres sont distinctes (M, A, T, H, S). Il y a 5 lettres. Nombre d'anagrammes = $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$.

Combien d'anagrammes peut-on former avec les lettres du mot "ANANAS" ? Il y a 6 lettres au total. Lettre A : 3 fois Lettre N : 2 fois Lettre S : 1 fois Nombre d'anagrammes = $\frac{6!}{3! \times 2! \times 1!} = \frac{720}{6 \times 2 \times 1} = \frac{720}{12} = 60$.

Une permutation circulaire est un arrangement d'objets autour d'un cercle. Dans ce cas, il n'y a pas de "début" ou de "fin" absolu.

Key Concepts:

• Arrangement en cercle: Les rotations d'un même arrangement sont considérées comme identiques.
• Point de référence: Pour éviter de compter les arrangements identiques, on fixe souvent un des objets comme point de référence.
• Formule spécifique: Le nombre de permutations circulaires de $n$ objets distincts est $(n-1)!$.

De combien de façons 4 personnes peuvent-elles s'asseoir autour d'une table ronde ? Si les personnes sont A, B, C, D. L'arrangement (A, B, C, D) est le même que (B, C, D, A) ou (C, D, A, B) ou (D, A, B, C) si la table est ronde. On fixe une personne (par exemple A). Les 3 autres personnes peuvent être arrangées de $3!$ façons autour d'elle. Nombre de permutations circulaires = $(4-1)! = 3! = 3 \times 2 \times 1 = 6$.

On choisit $k$ objets parmi $n$ objets distincts, et l'ordre dans lequel ils sont choisis compte. De plus, un objet ne peut être choisi qu'une seule fois (sans répétition).

Key Concepts:

• Choix ordonné de k objets parmi n: On sélectionne un sous-ensemble ordonné.
• Formule A(n, k): Le nombre d'arrangements de $k$ objets parmi $n$ objets distincts est noté $A_n^k$ ou $P(n, k)$ ou $nPk$. $A_n^k = \frac{n!}{(n-k)!}$ où $0 \le k \le n$.
• Importance de l'ordre: Si l'on choisit A puis B, c'est différent de B puis A.

Dans une course de 10 athlètes, combien y a-t-il de podiums possibles (1er, 2ème, 3ème place) ? Il s'agit de choisir 3 athlètes parmi 10, et l'ordre est important. $n=10$, $k=3$. $A_{10}^3 = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 \times 9 \times 8 = 720$. Il y a 720 podiums possibles.

On choisit $k$ objets parmi $n$ objets distincts, l'ordre compte, et un objet peut être choisi plusieurs fois (avec répétition).

Key Concepts:

• Choix ordonné avec remise: Après chaque choix, l'objet est "remis" dans l'ensemble des choix possibles.
• Formule n^k: Le nombre d'arrangements avec répétition de $k$ objets parmi $n$ est $n^k$. Chaque position peut être occupée par l'un des $n$ objets, indépendamment des autres positions.
• Exemples (codes, numéros): Typique pour les codes PIN, les numéros de téléphone, etc.

Combien de codes PIN à 4 chiffres peut-on former ? (Les chiffres vont de 0 à 9, et peuvent se répéter). Il y a 10 chiffres possibles pour chaque position. Le choix du premier chiffre est indépendant du choix du second, etc. $n=10$ (chiffres disponibles), $k=4$ (longueur du code). Nombre de codes = $10^4 = 10 \times 10 \times 10 \times 10 = 10\,000$.

Il est crucial de bien comprendre la différence entre permutations et arrangements.

Key Concepts:

• Tous les objets vs une partie:
  • Les permutations utilisent tous les $n$ objets ($k=n$). C'est un arrangement de $n$ objets parmi $n$.
  • Les arrangements sélectionnent une partie des objets ($k < n$). C'est un arrangement de $k$ objets parmi $n$.
• Ordre toujours important: Dans les deux cas (permutations et arrangements), l'ordre des éléments sélectionnés est fondamental.
• Cas limites: Une permutation de $n$ objets est un cas particulier d'arrangement où $k=n$. $A_n^n = \frac{n!}{(n-n)!} = \frac{n!}{0!} = \frac{n!}{1} = n!$.

Récapitulatif:

• Permutation de $n$ objets distincts: On ordonne tous les $n$ objets. Nombre = $n!$.
• Arrangement de $k$ objets parmi $n$ distincts (sans répétition): On ordonne $k$ objets choisis parmi $n$. Nombre = $A_n^k = \frac{n!}{(n-k)!}$.

On choisit $k$ objets parmi $n$ objets distincts, et l'ordre dans lequel ils sont choisis n'a pas d'importance. Un objet ne peut être choisi qu'une seule fois (sans répétition).

Key Concepts:

• Choix non ordonné de k objets parmi n: On sélectionne un sous-ensemble, la composition du sous-ensemble est ce qui compte, pas l'ordre interne de ses éléments.
• Coefficient binomial C(n, k): Le nombre de combinaisons de $k$ objets parmi $n$ objets distincts est noté $C_n^k$, $\binom{n}{k}$, ou $nCk$. Il est souvent lu "n parmi k".
• Formule et notation: $C_n^k = \binom{n}{k} = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!}$ où $0 \le k \le n$.

Dans une classe de 20 élèves, on doit choisir 3 délégués. Combien de groupes de 3 délégués différents peut-on former ? L'ordre n'a pas d'importance (être le premier délégué choisi ou le troisième ne change rien au fait d'être délégué). $n=20$, $k=3$. $C_{20}^3 = \binom{20}{3} = \frac{20!}{3!(20-3)!} = \frac{20!}{3!17!} = \frac{20 \times 19 \times 18}{3 \times 2 \times 1} = 10 \times 19 \times 6 = 1140$. Il y a 1140 groupes de délégués possibles.

Les coefficients binomiaux possèdent plusieurs propriétés intéressantes et utiles.

Key Concepts:

• Symétrie C(n, k) = C(n, n-k): Choisir $k$ objets à retenir parmi $n$ est équivalent à choisir $n-k$ objets à rejeter parmi $n$. $\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n!}{(n-k)!(n-(n-k))!} = \binom{n}{n-k}$ Exemple: $\binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$. Et $\binom{10}{7} = \frac{10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4}{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$.

• Valeurs particulières:

  • $\binom{n}{0} = 1$ (Il n'y a qu'une seule façon de choisir 0 objet : ne rien choisir).
  • $\binom{n}{n} = 1$ (Il n'y a qu'une seule façon de choisir $n$ objets : tous les prendre).
  • $\binom{n}{1} = n$ (Il y a $n$ façons de choisir 1 objet parmi $n$).

• Relation de Pascal: Elle permet de calculer les coefficients binomiaux de manière récursive et est la base de la construction du Triangle de Pascal. $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

• Triangle de Pascal: Un tableau triangulaire où chaque nombre est la somme des deux nombres directement au-dessus de lui. Il représente les coefficients binomiaux.

                    1            (n=0)
                   1 1           (n=1)
                  1 2 1          (n=2)
                 1 3 3 1         (n=3)
                1 4 6 4 1        (n=4)
               1 5 10 10 5 1     (n=5)
  

C'est le cas où l'on choisit $k$ objets parmi $n$ types d'objets, l'ordre n'a pas d'importance, et un même type d'objet peut être choisi plusieurs fois (avec remise).

Key Concepts:

• Choix non ordonné avec remise: Imaginez que vous piochez des boules dans une urne, puis vous les remettez avant de piocher à nouveau.
• Formule spécifique C(n+k-1, k): Le nombre de combinaisons avec répétition de $k$ objets parmi $n$ types d'objets est donné par : $\Gamma_n^k = \binom{n+k-1}{k} = \binom{n+k-1}{n-1}$
• Exemples (choix de bonbons): Typique pour la distribution d'objets identiques dans des catégories distinctes.

Un magasin vend 4 types de bonbons différents (chocolat, caramel, fraise, menthe). Vous voulez acheter 5 bonbons. Combien de combinaisons différentes de bonbons pouvez-vous acheter ? Ici, $n=4$ (types de bonbons) et $k=5$ (nombre de bonbons à choisir). L'ordre n'importe pas, et les bonbons du même type sont "répétés". Nombre de combinaisons = $\binom{4+5-1}{5} = \binom{8}{5} = \frac{8!}{5!3!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 8 \times 7 = 56$. Il y a 56 façons d'acheter les bonbons.

La distinction entre arrangements et combinaisons est la plus importante en dénombrement.

Key Concepts:

• Ordre important ou non:
  • Arrangements: L'ordre des éléments sélectionnés est important. (Ex: 1er, 2ème, 3ème place ; code PIN).
  • Combinaisons: L'ordre des éléments sélectionnés n'est PAS important. (Ex: un groupe de délégués ; une main de cartes).
• Quand utiliser quelle formule:
  • Si l'ordre compte, utilisez les formules d'Arrangements (ou Permutations si tous les objets sont utilisés).
  • Si l'ordre ne compte pas, utilisez les formules de Combinaisons.
• Exemples comparatifs:
  • Course : Choisir 3 médaillés parmi 8 (or, argent, bronze) → arrangement $A_8^3$.
  • Loto : Choisir 6 numéros parmi 49 → combinaison $C_{49}^6$.
  • Équipe : Choisir un capitaine et un vice-capitaine parmi 10 joueurs → arrangement $A_{10}^2$.
  • Équipe (bis) : Choisir 2 joueurs parmi 10 pour former une paire → combinaison $C_{10}^2$.

La formule utilise les coefficients binomiaux pour exprimer le développement de $(a+b)^n$.

Key Concepts:

• Coefficients binomiaux: Les coefficients de chaque terme dans le développement sont précisément les coefficients binomiaux $\binom{n}{k}$.
• Puissances de a et b: Pour chaque terme, la puissance de $a$ diminue de $n$ à $0$, et la puissance de $b$ augmente de $0$ à $n$.
• Somme des exposants: La somme des exposants de $a$ et $b$ dans chaque terme est toujours égale à $n$.

La formule du binôme de Newton est : $(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$ où $\binom{n}{k}$ sont les coefficients binomiaux.

Développons $(x+y)^3$ en utilisant la formule : $n=3$. Pour $k=0$: $\binom{3}{0} x^3 y^0 = 1 \cdot x^3 \cdot 1 = x^3$ Pour $k=1$: $\binom{3}{1} x^2 y^1 = 3 \cdot x^2 \cdot y = 3x^2y$ Pour $k=2$: $\binom{3}{2} x^1 y^2 = 3 \cdot x \cdot y^2 = 3xy^2$ Pour $k=3$: $\binom{3}{3} x^0 y^3 = 1 \cdot 1 \cdot y^3 = y^3$ Donc, $(x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3$.

La formule du binôme de Newton a des applications variées.

Key Concepts:

• Calcul de termes spécifiques: On peut trouver le coefficient d'un terme particulier sans développer toute l'expression.
• Démonstrations d'identités: Elle est utilisée pour prouver diverses identités combinatoires.
  • Exemple: En posant $a=1$ et $b=1$, on obtient $(1+1)^n = 2^n = \sum_{k=0}^{n} \binom{n}{k} 1^{n-k} 1^k = \sum_{k=0}^{n} \binom{n}{k}$. Cette identité signifie que le nombre total de sous-ensembles d'un ensemble à $n$ éléments est $2^n$.
• Applications en probabilités: Elle apparaît dans la distribution binomiale.

Quel est le coefficient de $x^2 y^4$ dans le développement de $(x+y)^6$ ? Ici $n=6$. On cherche le terme $a^{n-k} b^k$ tel que $n-k=2$ et $k=4$. C'est bien $n=6$ ($2+4=6$). Le coefficient est $\binom{6}{4} = \frac{6!}{4!2!} = \frac{6 \times 5}{2 \times 1} = 15$. Le terme est donc $15x^2y^4$.

Les problèmes de tirages (souvent avec des urnes et des boules) sont des classiques pour illustrer les différentes techniques de dénombrement.

Key Concepts:

• Tirage avec ou sans remise:
  • Avec remise: L'objet tiré est remis dans l'urne. Chaque tirage est indépendant. Possible d'avoir des répétitions.
  • Sans remise: L'objet tiré n'est pas remis. Le nombre d'objets disponibles diminue à chaque tirage. Pas de répétitions.
• Tirage ordonné ou non ordonné:
  • Ordonné: L'ordre dans lequel les objets sont tirés est important.
  • Non ordonné: L'ordre n'est pas important, seule la composition finale du groupe compte.
• Urnes et boules: Modèle standard pour ces problèmes.

Une urne contient 10 boules numérotées de 1 à 10.

1. On tire 3 boules successivement avec remise, en notant l'ordre. (Ordonné, avec remise) $10^3 = 1000$ possibilités.
2. On tire 3 boules successivement sans remise, en notant l'ordre. (Ordonné, sans remise) $A_{10}^3 = 10 \times 9 \times 8 = 720$ possibilités.
3. On tire 3 boules simultanément (l'ordre n'importe pas). (Non ordonné, sans remise) $C_{10}^3 = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$ possibilités.

Ces problèmes concernent la distribution d'objets ou l'affectation de personnes à des postes.

Key Concepts:

• Distribution d'objets: Comment distribuer $k$ objets à $n$ personnes/boîtes.
• Placement de personnes: Comment placer des personnes dans des sièges.
• Cas des objets identiques/distincts: La nature des objets (identiques ou distincts) et des récipients (identiques ou distincts) est cruciale.

• Objets distincts dans des boîtes distinctes: On distribue 5 lettres différentes dans 3 boîtes aux lettres différentes. Pour chaque lettre, il y a 3 choix de boîte. Donc $3^5$ façons.
• Objets identiques dans des boîtes distinctes: On distribue 5 bonbons identiques à 3 enfants. C'est une combinaison avec répétition (les bonbons sont les "k" objets, les enfants les "n" types). $\binom{3+5-1}{5} = \binom{7}{5} = 21$ façons.

Pour aborder un problème de dénombrement, une approche méthodique est essentielle.

Key Concepts:

• Identifier le type de dénombrement:
  1. L'ordre des éléments est-il important ? (Oui → Permutation/Arrangement ; Non → Combinaison)
  2. Les répétitions sont-elles permises ? (Oui → avec répétition ; Non → sans répétition)
  3. Toutes les entités sont-elles utilisées ou seulement une partie ? (Toutes → Permutation ; Partie → Arrangement/Combinaison)
• Décomposer le problème: Si le problème est complexe, le diviser en sous-problèmes plus simples et appliquer les principes additif et multiplicatif.
• Vérification des résultats: Est-ce que le résultat a du sens ? Est-il trop grand ou trop petit ? Utiliser des cas plus simples pour vérifier la logique.
• Utiliser les diagrammes en arbre ou les tableaux: Pour les problèmes de petite taille, ces outils peuvent aider à visualiser et à ne rien oublier.