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 \]

La photo de groupe du directeur

Un directeur (radin et un peu idiot) veut faire produire toutes les photos possibles de ses 7 employés pour ensuite choisir car il ne veut pas se déplacer au shooting.

a) Combien de photos son assistant (intelligent) lui dira de faire produire ?

Peu emballé, le directeur suggère de ne prendre qu'un "échantillon représentatif" de 3 employés.

b) Combien de photos son assistant lui dira de faire produire ?

Le directeur ne veut pas faire produire plus de 50 photos. Son assistant lui propose alors de ne pas prendre de photos de 3 mêmes employés.

c) Combien de photo l'assistant lui propose de produire ?

Le directeur réfléchis, puis demande combien de photos il faudrait prendre avec tous les employés sans tenir compte de leur place.

d) Combien de photos l'assistant lui dira de prendre pour ce dernier scénario ?

Les truffes

Lors d'un mariage, on veut offrir une petite boîte de truffes au chocolat à chacun des nnn invité. Il y a mmm truffes différentes proposées par le confiseur. Il y a plusieurs boîtes à choix. Une boîte ronde unie pouvent contenir 6 truffes. Une boîte rectangulaire pouvant contenir 5 truffes en une rangée de 3 et de 2. On veut un arrangement unique pour chaque invité.

\[ o! \] \[ \frac{o!}{o_1!~o_2!~...} \] \[ \gray{1} \] \[ \gray{0} \]
\[ \frac{o!}{(o-e)!} \] \[ o^e \] \[ \frac{o!}{e!(o-e)!} \] \[ \frac{(o+e-1)!}{e!(o-1)!} \]
\[ 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 \]
\[ 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 :

= - - - + + + -
Ce qui correspond à : \[ |S| = |\Omega| - |A_1| - |A_2| - |A_3| + |A \cap B| + |B \cap C| + |C \cap A| + |A \cap B \cap C| \]
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.
est l'ensemble des solutions possibles (sans dés dont une face vaut plus que 6).
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.

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
... ... ... ... ... ... ...
... ... a b ... ... ... ...
... ... ... a+b ... ... ... ... ...
... ... ... ... ... ... ... ... ... ...

Calcul combinatoire

\[ A(\vec{o}, e) = \sum_{\substack{ x_1 + x_2 + \cdots + x_k ~=~ e \\[0.5em] 0 ~\leq~ x_i ~\leq~ o_i }} \frac{e!}{\prod_{i=1}^k x_i!} = \sum_{\substack{ \mathbf{x} \in \mathbb{N}^k \\[0.5em] \mathbf{1}^\top \mathbf{x} ~=~ e \\[0.5em] 0 ~\leq~ x_i ~\leq~ o_i }} \frac{e!}{\prod_{i=1}^k x_i!} \]
\[ C_e^o = \frac{ o! }{ e! (o - e)! } \]
objets de objets de valeur
emplacements
- - - - - -

Exemple simple

Les trois koalas sont allés chercher des fruits pour en donner un à chacun des deux éléphants.
Chacun des koala a une seule sorte de fruit en une quantité qui lui est propre.
La répartition est la suivante :

koala fruit(s)
Amandine 3 bananes
Thor 1 cerise
Nikita 1 orange
\[\begin{aligned} & \vec{o} = (3,1,1) \quad;\quad e = 2 \\[2em] & A((3,1,1), 2) = \\[1em] & \sum_{\substack{ x_1 + x_2 + x_3 ~=~ 2 \\[0.5em] 0 ~\leq~ x_i ~\leq~ o_i }} \frac{2!}{\prod_{i=1}^3 x_i!} = \\[3.5em] & \frac{2!}{2!~0!~0!} + \frac{2!}{1!~1!~0!} + \frac{2!}{1!~0!~1!} + \frac{2!}{0!~1!~~1!} = \\[1em] & 1 + 2 + 2 + 2 = \underline{\underline{7}}\\[1em] \end{aligned}\]
Les trois koalas étudient les 7 solutions, mais n'arrivent pas à se concentrer assez longtemps et finissent par manger tous les fruits. (Il n'y a aucune morale à cette histoire si jamais.)

Exemple compliqué

Les 11 koalas sont allés chercher des fruits pour en donner un à chacun des 8 éléphants.
Chacun des koala a une seule sorte de fruit en une quantité qui lui est propre.
La répartition est la suivante :

\[\begin{aligned} & \vec{o} = (3,6,2,1,1,4,2,1,1,1,2) \quad;\quad e = 8 \\[1em] & A((3,6,2,1,1,4,2,1,1,1,2), 11) = \underline{\underline{64'887'802}} \end{aligned}\]
Les 11 koalas n'étudient pas les 64'887'802 solutions, ils prennent simplement la première. (Il n'y a toujours pas de morale à cette histoire si jamais.)

Exemple compliqué calculable à la main

Les 4 koalas sont allés chercher des fruits pour en donner un à chacun des 3 éléphants.
Chacun des koala a une seule sorte de fruit en une quantité qui lui est propre.
La répartition est la suivante :

koala fruit(s)
Amandine 5 bananes
Thor 3 cerise
Nikita 1 orange
Will Smith 1 tomate
Note 1 :
Amandine a 5 bananes, mais elle ne pourra jamais en donner plus que 3, vu qu'il y a 3 éléphants et que chacun n'aura droit qu'à un seul fruit. De manière générale, on plafonne les éléments du vecteur à e. \[ \vec{o} = (\pink{5},3,1,1) \quad;\quad e = 3 \] devient \[ \vec{o} = (\pink{3},3,1,1) \quad;\quad e = 3 \]
Note 2 :
On va avoir plusieurs équations valides. Avant de se lancer tête baissée dans le calcul, on peut calculer le nombre de solutions avec la formule du "coefficient multinomial".
Ici je vend la mèche, c'est 12, mais explication plus bas de comment trouver 12.
\[\begin{aligned} & \vec{o} = (3,3,1,1) \quad;\quad e = 3 \quad\Rightarrow \\[2em] & A((3,3,1,1), 2) = \\[1em] & \sum_{\substack{ x_1 + x_2 + x_3 ~=~ 3 \\[0.5em] 0 ~\leq~ x_i ~\leq~ o_i }} \frac{3!}{\prod_{i=1}^4 x_i!} = \\[3.5em] & \orange{ \frac{3!}{3!~0!~0!~0!} + \frac{3!}{0!~3!~0!~0!} } \blue{ + \frac{3!}{2!~1!~0!~0!} + \frac{3!}{2!~0!~1!~0!} + \frac{3!}{2!~0!~0!~1!} + \frac{3!}{1!~2!~0!~0!} + \frac{3!}{0!~2!~1!~0!} + \frac{3!}{0!~2!~0!~1!} } \green{ + \frac{3!}{1!~1!~1!~0!} + \frac{3!}{1!~1!~0!~1!} + \frac{3!}{1!~0!~1!~1!} + \frac{3!}{0!~1!~1!~1!} } = \\[1em] & \orange{ 2 \frac{3!}{3!} } \blue{ + 6 \frac{3!}{2!1!} } \green{ + 4 \frac{3!}{1!1!1!} } \quad=\quad 2 + 18 + 24 \quad=\quad \underline{\underline{44}} \\[1em] \end{aligned}\]

Coefficient multinomial

Formule brutale :
\[\begin{aligned} & bN(e) = [z^e] \prod_{i=1}^{n} \frac{1-z^{o_i+1}}{1-z} \\[2em] \end{aligned}\]
Le nombre de termes à multiplier est donné par le coefficient de z^e. Pour chaque nombre entier dans le vecteur de base, on en fait une équation de degré correspondant et on les multiplie.
\[\begin{aligned} bN(e) = (1 + z + z^2 + z^3) (1 + z + z^2 + z^3) (1 + z) (1 +z) \end{aligned}\]
On a pas besoin de tout distribuer pour trouver le coefficient de z^e.
il y a 4 manières d'arriver à z^3 avec z * z * z * 1
il y a 6 manières d'arriver à z^3 avec z^2 * z * 1 * 1
il y a 2 manières d'arriver à z^3 avec z^3 * 1 * 1 * 1
Donc 12 solutions au total, ce qui est gérable ici.