« Combinatoire/Introduction » : différence entre les versions

Bonjour à tous, et bienvenue dans le cours consacré à la '''combinatoire'''. Ce cours va en quelque sorte vous faire revenir au tout début de votre parcours en mathématiques; en effet, nous allons faire ici ce que font tous les enfants lorsqu'ilsau découvrentdébut cede ''mondeleur merveilleux''parcours scolaire : nous allons apprendre à '''compter des objets'''.<br /> Et des objets entiers. Nous serons donc dans un monde où les nombres négatifs et les fractions n'existent pas (et ne parlons même pas des <math>\pi</math>, <math>\sqrt{2}</math> et autres nombres irrationnels), seulement les bons vieux entiers naturels. Rien de très compliqué donc!

Heureusement, contrairement à nos chers têtes blondes, vous savez qu'en mathématiquemathématiques on peut utiliser des formules (plus ou moins) simples pour résoudre des problèmes (plus ou moins) rapidement. Et c'est donc ce qui nous occupera durant l'ensemble de ce cours : trouver des formules qui permettent de compter certains types d'objets, même quand leur nombre est très grand.

Dans ce premier chapitre cependant, nous allons cependant nous contenter de la première approche. Je vais ici vous présentez quelques problèmes relativement simples ; nous listerons l'ensemble des objets possibles et nous les compterons. Ces problèmes nous serviront de référence pour les prochains chapitres et vous donneront une idée de ce dont ce cours va parler, du genre de chose qu'on apprend à « compter ».

Je suppose que vous savez ce qu'est une loterie : vous choisissez un ensemble de nombre parmi une liste prédéfinie et vous espérez que, lors d'un tirage au sort, ce seront les mêmes qui sortiront. Il y, par exemple, cinq nombres tirés parmi 50. On peut se poser la question de savoir combien de tirages sont possibles.

Combien de tirage au sort différents sont-ils possibles ? Il s'agit de trouver toutes les combinaisons possibles de deux chiffres allant de 0 à 3. Essayez d'en faire la liste par vous même avant de continuer.

*Soit l'ordre dans le tirage à de l'importance, soit il n'en a pas. Dans le premier cas, (1;2) et (2;1) sont deux tirages différents ; dans le second, on ne le compte qu'une fois. Évidemment, l'une et l'autre règle donneront des résultats différents. <br /><u>Spoiler de la suite du cours</u> : Dans le cas où l'ordre de tirage à de l'importance, on parlera d''''arrangements''' ; dans le cas contraire, il s'agit de '''combinaisons'''.

*Soit les nombres ne peuvent pas apparaître plusieurs fois, soit ils peuvent. Dans le premier cas on parle de tirage '''sans répétitionremise''', dans le second cas de tirage '''avec répétitionremise'''; il faut imaginer que dans le premier cas, la personne qui tire au sort laisse le premiers chiffre tiré sur le coté tandis que dans le second, il le remet avec les autres. (2;2) par exemple est possible seulement dans le cas d'un tirage àavec répétitionremise.

Cependant, uneUne remarque s'impose ici. Cela va vous peut-être paraître évident, mais touttous ce qu'onles acalculs fait ici n'aont rienaucun à voirrapport avec le hasard. Leen jeu lors du tirage deà la loterie. estIl s'agit juste d'un exemple : on peut imaginer des situations tout à fait analogueanalogues qui ne font pas appel au hasard. Par exemple, on peut se demander combien de manièremanières différentedifférentes on a de choisir 2 élus au parlement parmi 4 candidats. Les réponses seront parfaitement analogues.

Certes, on peut aussi se poser la question : quelquelle est la probabilité de chaque tirage ? Mais once n'est plus alors dans le domaine de la combinatoire ; c'est la théorie des probabilités qui s'occupentoccupe de ce genre de questions.

Avançons avec notre deuxième exemple. Imaginons qu'on ait cinqquatre objets (qu'on va appeler objets 1, 2, 3, 4 ) et deux boîtes (Boîte A et Boîte B). De combien de façons peut-on ranger les premiers dans les seconds ?

*Est-ce que les objets sont '''discernables''' ? En autred'autres motmots, est-ce que ce sont tous les mêmes – et dans ce cas, seul le nombre d'objet qu'on met dans chaque boîte à de l'importance – où est-ce qu'ils sont tous différents ? <br />Par exemple, si on considère les objets comme '''indiscernables''', les dispositions<br />''Boîte A contient {1, 2, 3} et Boîte B contient {4}'' <br />ou bien <br />''Boîte A contient {2, 3, 4} et Boîte B contient {1}''<br />sont considérées comme identiques et ne sont comptés qu'une fois. Ce n'est pas le cas si on considère que les objets sont discernables.

*Est-ce que les boîtes sont discernables ? La distinction est la même que dans le cas des objtesobjets. Par exemple, les dispositions <br />''Boîte A contient {1, 2, 3} et Boîte B contient {4}''<br />ou bien<br />''Boîte B contient {1, 2, 3} et Boîte A contient {4}''<br />sont identiques si les boîtes sont considérées comme indiscernables et différentes si elles sont considérées comme discernables.

Ici, occupons nous du cas où et les objets et les boîtes sont discernables. Essayez de faire la liste vous mêmes avant de regarder la réponse.
Voici l'ensemble des réponses :

(Faire ici jolie imageun oupetit tableaudessin)

La théorie des ensembles offre le cadre théorique idéal, d'une part pour démontrer formellement les différentes formules, d'autres part pour «  abstraire  » toutes les situations possibles et les réduire à quelques cas typiques.

Rassurez-vous  : si vous ne connaissez pas la théorie des ensembles, elle n'est pas obligatoire pour ce cours. Les paragraphes qui en parlent seront disposées en fin de chapitre et pourront être passés. Si pour vous, le mot «  injection  » n'évoque que le vaccin de rappel contre le tétanos et que le mot «  relation  » ne vous fait penser qu'à votre liaison amoureuse présente, passée ou imaginaire, il est probable que vous deviez vous y résoudre. Vous pouvez aussi en profiter pour lire ce cours sur la théorie des ensembles pour ensuite revenir profiter de celui-ci ;-)