Denombrement et Analyse Combinatoire

---

Combinaison sans répétition

---

• Une combinaison sans répétition de \( p \) éléments parmi \( n \) est une partie de \( p \) éléments de \( E \) (card(E) = \( n \)).

• Attention : Ici, l'ordre des éléments ne compte pas.

• Il y a \( C_n^p = \frac{n!}{p! \cdot (n - p)!} \) combinaisons sans répétition de \( p \) éléments parmi \( n \).

Exemple

• Il y a \(C_{52}^3 = \frac{52!}{3! \cdot (52 - 3)!}\) manières possibles de prendre une poignée de 3 boules dans un sac de 52 boules, sans tenir compte de l'ordre.

Formule de symétrie de Pascal

---

• \(C_n^p = \frac{n!}{p! (n - p)!} = C_n^{n - p}\)
• \( (a + b)^n = \sum_{k=0}^{n} C_n^k a^k b^{n - k}\)
• \( C_n^1 = n \quad | \quad C_n^n = 1 \quad | \quad C_n^0 = 1\)

Formule de Pascal

---

• \( C_n^p = C_{n-1}^{p-1} + C_{n-1}^p \)

Petite Formule

---

• \(C_n^p = \frac{n}{p} C_{n-1}^{p-1}\)
• \(p \, C_n^p = n \, C_{n-1}^{p-1}\)


• \(\sum_{k=0}^{n} C_n^k = 2^n\)
• \(\sum_{k=0}^{n} C_n^k (-1)^k = 0\)

Partie d'un ensemble

---

• \( P_k(E) = \{ A \subset E \;|\; \text{card} \, A = k \} \)
• \( P(E) = \bigcup_{k=0}^{n} P_k(E) \)
• \( \text{card} \, P(E) = \sum_{k=0}^{n} \text{card} \, P_k(E) = \sum_{k=0}^{n} C_n^k = 2^n \)

Somme d'entiers des carrés, des cubes, des puissances 4

---

• \( 1 + 2 + \ldots + n = \sum_{k=0}^{n} k = \frac{n(n+1)}{2} \)
• \( 1^2 + 2^2 + \ldots + n^2 = \sum_{k=0}^{n} k^2 = \frac{n(n-1)(2n+1)}{6} \)
• \( 1^3 + 2^3 + \ldots + n^3 = \sum_{k=0}^{n} k^3 = \left( \frac{n(n-1)}{2} \right)^2 \)
• \( 1^4 + 2^4 + \ldots + n^4 = \sum_{k=0}^{n} k^4 = \frac{n(n-1)(2n+1)(3n^2 + 3n - 1)}{30} \)

Formule de Vandermonde

---

• \( n \leq a + b \)
• \( \sum_{k=0}^{n} C_a^k C_b^{n-k} = C_{a+b}^n \)

Exemple

• On veut choisir un sous-ensemble de 15 personnes parmi un total de 200 étudiants, qui sont divisés en deux groupes :

  • 120 femmes (F)
  • 80 hommes (H)

• Le calcul du nombre de façons de choisir 15 personnes parmi 200 (avec des groupes de tailles différentes) est donné par :

  \( C_{200}^{15} = C_{120}^0 C_{80}^{15} + C_{120}^1 C_{80}^{14} + C_{120}^2 C_{80}^{13} + \ldots + C_{120}^{15} C_{80}^0 \)

• • \( C_{120}^k \) : Le nombre de façons de choisir \( k \) femmes parmi 120.
  • \( C_{80}^{15-k} \) : Le nombre de façons de choisir \( 15-k \) hommes parmi 80.

  Le calcul total consiste à additionner toutes les façons possibles de sélectionner \( k \) femmes et \( 15-k \) hommes pour toutes les valeurs de \( k \) de 0 à 15.

Arrangement avec répétition

---

• On appelle arrangement ou p-liste de \( p \) éléments parmi \( n \) toute liste ordonnée de \( p \) éléments avec répétition parmi \( n \) éléments de \( E \).

Exemple

• Il y a \( 5^4 \) manières d'écrire un nombre comprenant 4 chiffres avec remise dans \(\{1, 2, 3, 4, 5\}\).
• Cela signifie que l'on souhaite former un nombre composé de 4 chiffres, en utilisant les éléments de l'ensemble \(\{ 1, 2, 3, 4, 5 \}\). Ici, "avec remise" signifie que chaque chiffre peut être réutilisé à chaque position dans le nombre. Autrement dit, il n'y a aucune restriction quant au nombre de fois qu'un chiffre peut apparaître dans le nombre à 4 chiffres.

Modèle

• Tirages successifs de \( p \) éléments parmi \( n \) avec remise.

Arrangement sans répétition ou p-liste d'élèments distincts

---

• Soit un entier \( p \leq n \), on appelle arrangement sans répétition (ou p-liste distincte) de \( p \) éléments parmi \( n \) toute liste ordonnée et sans répétition de \( p \) éléments choisis parmi \( n \) de \( E \).

• Il y a \( A_n^p = n (n - 1) \ldots (n - p + 1) = \frac{n!}{(n - p)!} \) arrangements sans répétition de \( p \) éléments parmi \( n \).
• Si \( n = p \) :
  \[ A_n^0 = \frac{n!}{0!} = n! \]

Définition

• On appelle permutation de \( E = \{ x_k \;|\; k \in ⟦1, n⟧ \} \) (\( \text{card} \, E = n \)) toute bijection de \( E \longrightarrow E \). Le nombre de permutations est \( n! \).

\[ = A_n^k \]

Resumé

---

Arrangement	Avec répétition	Sans répétition
Ordonnée	\(n^p\)	\(A_n^p\)
Non ordonnée	??	\(C_n^p\)

Remarques

---

• \( n^p \) arrangements avec répétition : un arrangement de \( p \) éléments choisis parmi \( n \) est assimilé à une application \(\{1, 2, \ldots, p\} \to \{1, 2, \ldots, n\}\).
  Il y a \( n^p \) applications.
• Arrangement sans répétition : c'est un arrangement de \( p \) éléments parmi \( n \) assimilé à une application injective de \(\{1, 2, \ldots, p\} \to \{1, 2, \ldots, n\}\).
  Il y a \( A_n^p \) injections.

Cardinaux

---

• \(\text{card } E\) : le nombre d'éléments
• \(\text{card } \emptyset = 0\)
• \(A \subseteq B \implies \text{card } A \leq \text{card } B\)
• \(A \subset E\)
\( \overline{A} = C_E^A \)
• \(\text{card } \overline{A} = \text{card } E - \text{card } A\)
• Si A et B sont disjoints
• \(A \cap B = \emptyset\)
• \(\text{card } (A \cup B) = \text{card } A + \text{card } B\)
• Si non
• \(\text{card } (A \cup B) = \text{card } A + \text{card } B - \text{card } (A \cap B)\)
• \(\text{card } (A \cup B \cup C) = \text{card } (A \cup B) + \text{card } C - \text{card } ((A \cup B) \cap C)\)
• \(\text{card } (A \cup B \cup C) = \text{card } A + \text{card } B - \text{card } (A \cap B) + \text{card } C - \text{card } (A \cap C) - \text{card } (B \cap C) + \text{card } (A \cap B \cap C)\)
• On note \( A - B \) ou bien \( A \cap \overline{B} \).
• \( A \setminus B = A \cap \overline{B}\)
• \(\text{card}(A \setminus B) = \text{card}(A) - \text{card}(A \cap B)\)
• \( A \setminus B = A \cap \overline{B} \)
• \(\text{card}(A \cap \overline{B}) + \text{card}(A \cap B) = \text{card}((A \cap B) \cup (A \cap \overline{B}))\)

\(= \text{card}(A \cap (B \cup \overline{B}))\)

\(= \text{card}(A \cap E)\)

\(= \text{card}(A)\)

• \(\text{card}(A \cap \overline{B}) - \text{card}(A \setminus B) = \text{card}(A) - \text{card}(A \cap B)\)
• \(A \times B = \{(x, y) \mid x \in A, \, y \in B\}\)
• \(\text{card}(A \times B) = \text{card}(A) \times \text{card}(B)\)