Combinatoire

Notation générale sur cette page

\[ \begin{aligned} & P \text{ : permutation} \quad A \text{ : arrangements} \quad C \text{ : combinaisons} \\[1em] & C_e^o \quad \text{remplace la notation générale} \quad C_k^n \\ & o \text{ : objets} \quad e \text{ : emplacements} \\[1em] & T \text{ : tous les éléments sont présents} \quad O \text{ : l'ordre compte} \quad R \text{ : avec répétitions} \\[1em] & \Omega \text{ : univers / tous les résultats possibles / événement certain} \\ & A \text{ : événement} \\ & \omega \text{ : événement élémentaire / éventualité (/ singleton)} \\ & \varnothing \text{ : événement impossible} \\ & \Omega \supseteq A \supseteq \omega \\[1em] \end{aligned} \]

Expérience aléatoire

\[ \begin{aligned} & \mathbb{P} \Bigg( \bigcup_{n \in \mathbb{N}} A_n \Bigg) && = && \sum_{n = 0}^{+ \infty} \Big( \mathbb{P} (A_n) \Big) \\[3em] & \mathbb{P} \Bigg( \bigcap_{n \in \mathbb{N}} A_n \Bigg) && = && \prod_{n = 0}^{+ \infty} \mathbb{P}(A_n) \end{aligned} \] \[ A_i \cup A_j = \varnothing \]
\[ O \] \[ R \]
\[ T \] \[ P_o \gray{= P_e} \] \[ 1 \] \[ \overline{P}_o (o_1, o_2,...) \] \[ 0 \]
\[ A_e^o \] \[ C_e^o \] \[ \overline{A}_e^o \] \[ \overline{C}_e^o \]
placements
sur photo
de groupe		 ensemble
/ tout le
monde		 lettres
du frigo
dont double(s)		 impossible
podium des
3 gagnants		 constituer
une équipe		 code PIN cornet
de glace
3 boules
\[ o! \gray{= e!} \] \[ 1 \] \[ \frac{o!}{o_1! \cdot o_2! \cdot...} \] \[ 0 \]
\[ \frac{o!}{(o-e)!} \] \[ \frac{o!}{e!(o-e)!} \] \[ o^e \] \[ \frac{(o+e-1)!}{e!(o-1)!} \]

Egalités

\[ \overline{C}_{e}^{o} = C_{e}^{o + e - 1} \]
\[ C_o^o = 1 \quad C_o^0 = 1 \quad C_1^o = o \]
\[ C_e^o + C_{e+1}^o = C_{e+1}^{o+1} \]

Partitions d'entiers avec répétition

\[ o_1 + o_2 + ... + o_n = e \quad ; \quad o_i \ge 0 \quad\quad \Rightarrow \quad\quad \overline{C}_e^o = \frac{(o + e - 1)!}{e!(o - 1)!} \]

Exemple 1

On tire 3 dés et on veut faire 9, on a donc :

\[ \begin{aligned} & dé_1 + dé_2 + dé_3 = 9 \quad && 1 \le dé \le 6 \quad && dé \ge 1 \\ & && && \orange{dé \ge 0} && \quad \Leftarrow \text{ mais c'est ça qu'on voudrait}\\ & o_1 + o_2 + o_3 = 6 && 0 \le o \le 5 \quad && o \ge 0 && \quad \Leftarrow \quad o = dé - 1 \\[1em] \end{aligned} \]

On peut alors poser :

\[ \overline{C}_6^3 = \frac{(6 + 3 - 1)!}{3!(6 - 1)!} = \underline{\underline{56}} \]

Exemple 2

On tire 3 dés et on veut faire 15, on a donc :

\[ \begin{aligned} & dé_1 + dé_2 + dé_3 = 15 \quad && 1 \le dé \le 6 \quad && dé \ge 1 \\ & && && \orange{dé \ge 0} && \quad \Leftarrow \text{ mais c'est ça qu'on voudrait} \\ & o_1 + o_2 + o_3 = 12 && 0 \le o \le 5 \quad && o \ge 0 && \quad \Leftarrow \quad o = dé - 1 \\[1em] \end{aligned} \]

On peut poser :

\[ \begin{aligned} & \overline{C}_{3}^{12} = \frac{(3 + 12 - 1)!}{12!(3 - 1)!} = 91 \\ \end{aligned} \]

Mais problème : y a des solutions comme 1 + 1 + 12 et ça existe pas comme face de dé, 12...

On peut dresser la liste des solutions de manières ensembliste :

= - - - + + + -
Où
est l'ensemble des solutions possibles (sans dés dont une face vaut plus que 6).
est l'ensemble de toutes les solutions (incluant les solutions impossibles comme 1 + 1 + 12) et dont le cardinal précédemment calculé vaut 91.
sont les ensembles de solutions avec au moins un dé qui vaut plus que 6, respectivement pour le dé 1, 2 et 3.
sont les ensembles de solutions avec au moins 2 dés qui valent plus que 6.
est l'ensemble avec les solutions où les 3 dés valent plus que 6. Pour ce dernier, on sait qu'il est vide car on aurait un résultat plus grand que 15 et on est dans un sous-ensemble de solutions où la somme vaut 15.

Formule :

\[ \begin{aligned} & |S| = |\Omega| - |A_1| - |A_2| - |A_3| + |A \cap B| + |B \cap C| + |C \cap A| + |A \cap B \cap C| \\ \end{aligned} \]

Calculer le cardinal des 3 premiers ensembles A :

\[ \begin{aligned} & \text{remarque :} \quad |A_1| = |A_2| = |A_3| \\ & dé_1 + dé_2 + dé_3 + 6 = 15 \quad && 1 \le dé \le 6 \quad && dé \ge 1 \\ & && && \orange{dé \ge 0} && \quad \Leftarrow \\ & o_1 + o_2 + o_3 + 6 = 12 && 0 \le o \le 5 \quad && o \ge 0 \\ & o_1 + o_2 + o_3 = 6 && 0 \le o \le 5 \quad && o \ge 0 \\ \end{aligned} \]

On peut poser :

\[ \begin{aligned} & |A_1| = \overline{C}_{3}^{6} = \frac{(3 + 6 - 1)!}{6!(3 - 1)!} = 28 \\ \end{aligned} \]

Calculer le cardinal des 3 ensembles suivants :

\[ \begin{aligned} & \text{même remarque :} \quad |A \cap B| = |B \cap C| = |C \cap A| \\ & dé_1 + dé_2 + dé_3 + 6 + 6 = 15 \quad && 1 \le dé \le 6 \quad && dé \ge 1 \\ & && && \orange{dé \ge 0} && \quad \Leftarrow \\ & o_1 + o_2 + o_3 + 6 + 6 = 12 && 0 \le o \le 5 \quad && o \ge 0 \\ & o_1 + o_2 + o_3 = 0 && 0 \le o \le 5 \quad && o \ge 0 \\ \end{aligned} \]

On peut poser :

\[ \begin{aligned} & |A \cap B| = \overline{C}_{3}^{0} = 1 \\ \end{aligned} \]
\[ \begin{aligned} & |\Omega| - |A_1| - |A_2| - |A_3| + |A \cap B| + |B \cap C| + |C \cap A| + |A \cap B \cap C| \\[1em] & \text{devient :} \\[1em] & 91 - 28 - 28 - 28 + 1 + 1 + 1 - 0 \quad = \quad \underline{\underline{10}} \end{aligned} \]

Très compliqué... ce résultat peut être vérifié de la manière suivante :

Il n'y a que ces 3 manières d'obtenir 15 avec 3D6:
  • 6 + 6 + 3, les permutations donnent 3 arrangements
  • 6 + 5 + 4, les permutations donnent 6 arrangements
  • 5 + 5 + 5, un seul arrangement
3 + 6 + 1 = 10, ce qui est bien juste.

Probabilité

\[ \begin{aligned} & \mathbb{P} = \frac{10}{6^3} \simeq 4,63 \% \end{aligned} \]

Binome de Newton

\[ (x + y)^n = \sum_{k=0}^n \binom{a}{b} x^{n-k} y^k \]

Coefficient biniomiale

\[ \binom{n}{k} = \frac{n!}{k!(n-k)!} \quad \gray{\binom{o}{e} = \frac{o!}{e!(o-e)!}} \]

Exemple

\[ (x + y)^5 \quad = \quad 1x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5xy^4 + 1y^5 \]

Triangle de Pascal

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1