Aujourd'hui nous nous intéressons de manière plus poussée aux combinaisons.
Rappelez-vous que nous avons toujours notre ensemble de rotations $\{r_{1}; r_{2}; r_{3}; r_{4}\}$ (ensemble de 4 éléments). Dans le dernier article je vous ai exposé la raison pour laquelle nous cherchons maintenant à déterminer puis calculer toutes les combinaisons possibles parmi $\{r_{1}; r_{2}; r_{3}; r_{4}\}$.
Afin de procéder par étapes successives, je vous propose de dessiner un tableau permettant de rassembler à la fois le nombre d'éléments (rotations) entrant dans la combinaison, ainsi que l'élément "de départ". Par habitude, le nombre d'éléments est appelé k, ici variant de 1 à 4.
\[ \begin{tabular}{l|cccc} & \( 1 \) & \( 2 \) & \( 3 \) & \( 4 \) \\ \hline \( r_{1} \) & \( \ldots \) & \( \ldots \) & \( \ldots \) & \( \ldots \) \\ \( r_{2} \) & \( \ldots \) & \( \ldots \) & \( \ldots \) & \( \ldots \) \\ \( r_{3} \) & \( \ldots \) & \( \ldots \) & \( \ldots \) & \( \ldots \) \\ \( r_{4} \) & \( \ldots \) & \( \ldots \) & \( \ldots \) & \( \ldots \) \\ \end{tabular} \]
Nous détaillerons le cas où r4 est notre élément de départ.
Ainsi, la première case requiert 1 élément (k = 1), en partant de r4, à savoir... r4. Edifiant, vous ne trouvez pas ??? ;o)
Je continue. La seconde case (k = 2) ajoute du piment : 2 élements parmi $\{r_{1}; r_{2}; r_{3}; r_{4}\}$. La troisième case (k = 3) nécessite 3 éléments, et la quatrième (k = 4) 4 éléments. Une seule main suffit pour compter sur ses doigts.
Mais lorsque vient le moment de présenter l'ensemble des résultats, nous nous rendons compte que ce qui était amusant peut vite devenir infernal à gérer. Voyez par vous-mêmes... (je vous rappelle qu'il ne s'agit que d'une ligne du tableau, et que nous n'avons que 4 rotations possibles).
\[ \begin{tabular}{l|cccc} & $1$ & $2$ & $3$ & $4$ \\ \hline $r_{1}$ & \ldots & \ldots & \ldots & \ldots \\ $r_{2}$ & \ldots & \ldots & \ldots & \ldots \\ $r_{3}$ & \ldots & \ldots & \ldots & \ldots \\ $r_{4}$ & $r_{4}$ & $r_{4}\left\{\begin{array}{c}r_{1}\\r_{2}\\r_{3}\end{array}\right.$ & $r_{4}\left\{\begin{array}{c} r_{1}\left\{\begin{array}{c} r_{2}\\r_{3}\end{array}\right.\\\\r_{2}\left\{\begin{array}{c}r_{1}\\r_{3}\end{array}\right.\\\\r_{3}\left\{\begin{array}{c}r_{1}\\r_{2}\end{array}\right.\end{array}\right. $& $r_{4}\left\{\begin{array}{c}r_{1}\left\{\begin{array}{c}r_{2}\left\{r_{3}\right.\\ r_{3}\left\{r_{2}\right.\end{array}\right.\\\\r_{2}\left\{\begin{array}{c}r_{1}\left\{r_{3}\right.\\r_{3}\left\{r_{1}\right.\end{array}\right.\\\\r_{3}\left\{\begin{array}{c}r_{1}\left\{r_{2}\right.\\r_{2}\left\{r_{1}\right.\end{array}\right.\end{array}\right. $ \\ \\ \end{tabular} \]
C'est très bien, me direz-vous, mais qu'est-ce que j'en fais, de toutes ces solutions possibles ?
Je vais mettre le doigt sur un point très important de l'analyse combinatoire (puisque c'est ce que nous faisons). Il s'agit à présent d'être plus rigoureux sur le terme "combinaison", et appliquer sa définition mathématique.
Les solutions présentées dans le tableau précédent sont toutes différentes, si l'on se base sur l'ordre des rotations. C'est ce qui est utilisé au tiercé, par exemple : le 1 arrivera avant le 4, suivi du 3 puis du 2. Nous appelons ceci un arrangement. Une combinaison est plus simple : que l'ordre soit 1-4-3-2 ou 4-2-3-1, il n'y a pas de différence ! Une combinaison gère la présence ou non d'un élément dans un ensemble d'éléments. Nos chances de remporter le tiercé seraient augmentées si le PMU acceptait les combinaisons ! :o) Le Loto, quant à lui, est basé sur le principe des combinaisons.
Qu'ai-je donc présenté dans le tableau alors ? Des arrangements, bien entendu.
Mais pourquoi s'embêter à chercher encore plus loin ? Je vais vous le montrer.
Le nombre d'arrangements possibles est noté $A^{k}_{n}$, où k est le nombre d'éléments que nous prenons en compte dans l'ensemble final, et n le nombre total d'éléments disponibles. Nous le calculons ainsi : $$A^{k}_{n} = \frac{n!}{(n-k)!}$$. Le point d'exclamation "!" est appelé "factorielle", et est une multiplication : 4! = 4 x 3 x 2 x 1. Ainsi n! = n x (n-1) x (n-2) x (n-3) x ... x 1. Plus concrètement, le nombre d'arrangements possibles pour une valeur de k et n est le nombre total d'arrangements auquel l'on soustrait le complémentaire de notre nombre d'arrangements à k et n éléments.
Dans les faits, si nous voulons dénombrer le nombre de solutions possibles pour $\{r_{1}; r_{2}; r_{3}; r_{4}\}$ et k=3 (c'est-à-dire la colonne entière k=3), nous avons $$A^{3}_{4} = \frac{4!}{(4-3)!}= \frac{4\times3\times2\times1}{1} = 4\times3\times2 =24$$.
Le nombre total d'arrangements possibles pour $\{r_{1}; r_{2}; r_{3}; r_{4}\}$ et toutes les valeurs de k est alors :
\[A^{1}_{4}+A^{2}_{4}+A^{3}_{4}+A^{4}_{4} = \sum_{k=1}^{4} A^{k}_{4} = 64.\]
Les plus courageux d'entre vous ne seront sans doute pas effrayés par ce nombre de solutions. Or, si vous décidez de passer à 10 rotations, $\sum_{k=1}^{10} A^{k}_{10} = 9 864 100$ et là c'est franchement plus douloureux.
L'intérêt des combinaisons est donc de réduire considérablement le nombre de solutions, en éliminant toutes les redondances !
Grâce à la formule $$C^{k}_{n} = \frac{n!}{k!(n-k)!}$$, nous pouvons calculer :
\[C^{1}_{4}+C^{2}_{4}+C^{3}_{4}+C^{4}_{4} = \sum_{k=1}^{4} C^{k}_{4} = 15.\]
Pour comparaison, $\sum_{k=1}^{10} C^{k}_{10} = 1023$. ;o)
Ainsi, pour résumer :
\[ \begin{tabular}{ll|cccc|c} \(n=4\) & \(k \Rightarrow \) & \( 1 \) & \( 2 \) & \( 3 \) & \( 4 \) & Somme des solutions\\ \hline Arrangements & \( A^{k}_{n} = \frac{n!}{(n-k)!} \) & \( 4 \) & \( 12 \) & \( 24 \) & \( 24 \) & 64 \\ \hline Combinaisons & \( C^{k}_{n} = \frac{n!}{k!(n-k)!}} \) & \( 4 \) & \( 6 \) & \( 4 \) & \( 1 \) & 15 \\ \end{tabular}\]
Prendre son courage à deux mains, une belle feuille de papier et son plus beau criterium ne seront pas suffisants pour parvenir à résoudre ce problème de combinaisons possibles pour un nombre de rotations réaliste. C'est pourquoi après vous avoir détaillé le principe du schmilblick dans l'article précédent puis démontré aujourd'hui que le nombre de combinaisons augmente exponentiellement avec le nombre n (vous ne me croyez pas ? J'ai fait le calcul pour vous), je vous donne rendez-vous dans le prochain article pour faire bouillir les neurones en tentant de résoudre le problème posé. ;oP
Rappelez-vous que nous avons toujours notre ensemble de rotations $\{r_{1}; r_{2}; r_{3}; r_{4}\}$ (ensemble de 4 éléments). Dans le dernier article je vous ai exposé la raison pour laquelle nous cherchons maintenant à déterminer puis calculer toutes les combinaisons possibles parmi $\{r_{1}; r_{2}; r_{3}; r_{4}\}$.
Afin de procéder par étapes successives, je vous propose de dessiner un tableau permettant de rassembler à la fois le nombre d'éléments (rotations) entrant dans la combinaison, ainsi que l'élément "de départ". Par habitude, le nombre d'éléments est appelé k, ici variant de 1 à 4.
\[ \begin{tabular}{l|cccc} & \( 1 \) & \( 2 \) & \( 3 \) & \( 4 \) \\ \hline \( r_{1} \) & \( \ldots \) & \( \ldots \) & \( \ldots \) & \( \ldots \) \\ \( r_{2} \) & \( \ldots \) & \( \ldots \) & \( \ldots \) & \( \ldots \) \\ \( r_{3} \) & \( \ldots \) & \( \ldots \) & \( \ldots \) & \( \ldots \) \\ \( r_{4} \) & \( \ldots \) & \( \ldots \) & \( \ldots \) & \( \ldots \) \\ \end{tabular} \]
Nous détaillerons le cas où r4 est notre élément de départ.
Ainsi, la première case requiert 1 élément (k = 1), en partant de r4, à savoir... r4. Edifiant, vous ne trouvez pas ??? ;o)
Je continue. La seconde case (k = 2) ajoute du piment : 2 élements parmi $\{r_{1}; r_{2}; r_{3}; r_{4}\}$. La troisième case (k = 3) nécessite 3 éléments, et la quatrième (k = 4) 4 éléments. Une seule main suffit pour compter sur ses doigts.
Mais lorsque vient le moment de présenter l'ensemble des résultats, nous nous rendons compte que ce qui était amusant peut vite devenir infernal à gérer. Voyez par vous-mêmes... (je vous rappelle qu'il ne s'agit que d'une ligne du tableau, et que nous n'avons que 4 rotations possibles).
\[ \begin{tabular}{l|cccc} & $1$ & $2$ & $3$ & $4$ \\ \hline $r_{1}$ & \ldots & \ldots & \ldots & \ldots \\ $r_{2}$ & \ldots & \ldots & \ldots & \ldots \\ $r_{3}$ & \ldots & \ldots & \ldots & \ldots \\ $r_{4}$ & $r_{4}$ & $r_{4}\left\{\begin{array}{c}r_{1}\\r_{2}\\r_{3}\end{array}\right.$ & $r_{4}\left\{\begin{array}{c} r_{1}\left\{\begin{array}{c} r_{2}\\r_{3}\end{array}\right.\\\\r_{2}\left\{\begin{array}{c}r_{1}\\r_{3}\end{array}\right.\\\\r_{3}\left\{\begin{array}{c}r_{1}\\r_{2}\end{array}\right.\end{array}\right. $& $r_{4}\left\{\begin{array}{c}r_{1}\left\{\begin{array}{c}r_{2}\left\{r_{3}\right.\\ r_{3}\left\{r_{2}\right.\end{array}\right.\\\\r_{2}\left\{\begin{array}{c}r_{1}\left\{r_{3}\right.\\r_{3}\left\{r_{1}\right.\end{array}\right.\\\\r_{3}\left\{\begin{array}{c}r_{1}\left\{r_{2}\right.\\r_{2}\left\{r_{1}\right.\end{array}\right.\end{array}\right. $ \\ \\ \end{tabular} \]
C'est très bien, me direz-vous, mais qu'est-ce que j'en fais, de toutes ces solutions possibles ?
Je vais mettre le doigt sur un point très important de l'analyse combinatoire (puisque c'est ce que nous faisons). Il s'agit à présent d'être plus rigoureux sur le terme "combinaison", et appliquer sa définition mathématique.
Les solutions présentées dans le tableau précédent sont toutes différentes, si l'on se base sur l'ordre des rotations. C'est ce qui est utilisé au tiercé, par exemple : le 1 arrivera avant le 4, suivi du 3 puis du 2. Nous appelons ceci un arrangement. Une combinaison est plus simple : que l'ordre soit 1-4-3-2 ou 4-2-3-1, il n'y a pas de différence ! Une combinaison gère la présence ou non d'un élément dans un ensemble d'éléments. Nos chances de remporter le tiercé seraient augmentées si le PMU acceptait les combinaisons ! :o) Le Loto, quant à lui, est basé sur le principe des combinaisons.
Qu'ai-je donc présenté dans le tableau alors ? Des arrangements, bien entendu.
Mais pourquoi s'embêter à chercher encore plus loin ? Je vais vous le montrer.
Le nombre d'arrangements possibles est noté $A^{k}_{n}$, où k est le nombre d'éléments que nous prenons en compte dans l'ensemble final, et n le nombre total d'éléments disponibles. Nous le calculons ainsi : $$A^{k}_{n} = \frac{n!}{(n-k)!}$$. Le point d'exclamation "!" est appelé "factorielle", et est une multiplication : 4! = 4 x 3 x 2 x 1. Ainsi n! = n x (n-1) x (n-2) x (n-3) x ... x 1. Plus concrètement, le nombre d'arrangements possibles pour une valeur de k et n est le nombre total d'arrangements auquel l'on soustrait le complémentaire de notre nombre d'arrangements à k et n éléments.
Dans les faits, si nous voulons dénombrer le nombre de solutions possibles pour $\{r_{1}; r_{2}; r_{3}; r_{4}\}$ et k=3 (c'est-à-dire la colonne entière k=3), nous avons $$A^{3}_{4} = \frac{4!}{(4-3)!}= \frac{4\times3\times2\times1}{1} = 4\times3\times2 =24$$.
Le nombre total d'arrangements possibles pour $\{r_{1}; r_{2}; r_{3}; r_{4}\}$ et toutes les valeurs de k est alors :
\[A^{1}_{4}+A^{2}_{4}+A^{3}_{4}+A^{4}_{4} = \sum_{k=1}^{4} A^{k}_{4} = 64.\]
Les plus courageux d'entre vous ne seront sans doute pas effrayés par ce nombre de solutions. Or, si vous décidez de passer à 10 rotations, $\sum_{k=1}^{10} A^{k}_{10} = 9 864 100$ et là c'est franchement plus douloureux.
L'intérêt des combinaisons est donc de réduire considérablement le nombre de solutions, en éliminant toutes les redondances !
Grâce à la formule $$C^{k}_{n} = \frac{n!}{k!(n-k)!}$$, nous pouvons calculer :
\[C^{1}_{4}+C^{2}_{4}+C^{3}_{4}+C^{4}_{4} = \sum_{k=1}^{4} C^{k}_{4} = 15.\]
Pour comparaison, $\sum_{k=1}^{10} C^{k}_{10} = 1023$. ;o)
Ainsi, pour résumer :
\[ \begin{tabular}{ll|cccc|c} \(n=4\) & \(k \Rightarrow \) & \( 1 \) & \( 2 \) & \( 3 \) & \( 4 \) & Somme des solutions\\ \hline Arrangements & \( A^{k}_{n} = \frac{n!}{(n-k)!} \) & \( 4 \) & \( 12 \) & \( 24 \) & \( 24 \) & 64 \\ \hline Combinaisons & \( C^{k}_{n} = \frac{n!}{k!(n-k)!}} \) & \( 4 \) & \( 6 \) & \( 4 \) & \( 1 \) & 15 \\ \end{tabular}\]
Prendre son courage à deux mains, une belle feuille de papier et son plus beau criterium ne seront pas suffisants pour parvenir à résoudre ce problème de combinaisons possibles pour un nombre de rotations réaliste. C'est pourquoi après vous avoir détaillé le principe du schmilblick dans l'article précédent puis démontré aujourd'hui que le nombre de combinaisons augmente exponentiellement avec le nombre n (vous ne me croyez pas ? J'ai fait le calcul pour vous), je vous donne rendez-vous dans le prochain article pour faire bouillir les neurones en tentant de résoudre le problème posé. ;oP
Bye for now...
édition : Hourra ! Après près de deux semaines de bataille quasi-quotidienne, je suis enfin parvenu à remettre sur pieds le script d'affichage LaTeX (il s'agit de l'affichage des tableaux, équations, etc.). Rien que pour la syntaxe du tableau des combinaisons, il m'aura fallu une soirée pour tout remettre à jour...
Aucun commentaire:
Enregistrer un commentaire