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

Contenu supprimé Contenu ajouté
ajout cadre
Premier jet
Ligne 1 :
{{Cadre|'''Note :''' Ce chapitre vient d'être mis en ligne. Il comporte des trous qui seront comblés, et des erreurs dues à une relecture déficiente sont susceptibles d'être encore présentes.}}
 
{{Chapitre
| idfaculté = mathématiques
Ligne 7 ⟶ 9 :
}}
 
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'ils découvrent ce ''monde merveilleux'' : 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>\sqrt[2]{2}</math> et autres nombres irrationnels), seulement les bons vieux entiers naturels. Rien de très compliqué donc!
Bonjour, et bienvenue dans ce cours consacré à la combinatoire. Ce que l'on va apprendre ici, c'est à dénombrer les différentes façons de disposer des objets (qui peuvent être pour ainsi dire n'importe quoi : des nombres, des lettres, des livres, des fruits...)↓
 
La plupart des problèmes qui seront abordés ici pourraient être résolus par simple dénombrement. Il suffirait à chaque fois de faire la liste de tous les objets possibles et puis de simplement les compter.
Oui, mais voilà : que faire quand les ensembles d'objets en question sont extrêmement grands ? 10 objets, cela marche ; 1000, c'est long mais on y survit ; 1000000, là, cela devient surhumain. Et devant 10<sup>100</sup>, nos ordinateurs les plus puissants hisseraient le drapeau blanc.
 
Heureusement, contrairement à nos chers têtes blondes, vous savez qu'en mathématique 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.
 
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 »
 
== Le tirage au sort de la loterie ==
[[Image:Lottoschein.jpg|thumb|droite|De combien de manière peut-on cocher 6 cases dans une grille de 50 nombres?]]
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.
Évidemment, le nombre de tirage possible d'une loterie normale est colossal, donc nous allons nous contenter d'une version plus simple. Soit un tirage au sort de 2 nombres parmi 4: 0, 1, 2, 3.
 
Combien de tirage au sort différents sont-ils possibles ? Essayez d'en faire la liste par vous même avant de continuer.
 
...
 
En fait, vous vous en êtes peut-être rendu compte en essayant de répondre à la question: la question ci-dessus est mal posée. En fait il manque des informations sur la manière dont se fait le tirage au sort. Il y a plusieurs possibilités :
 
*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étition''', dans le second cas de tirage '''avec répétition'''. (2;2) par exemple est possible seulement dans le cas d'un tirage à répétition.
 
Voilà un joli tableau qui résume la situation :
 
(Ici faire un tableau)
 
Et donc le nombre de tirages possibles est :
 
(Ici faire un tableau aussi)
 
Nous verrons plus tard comment résoudre ce genre de problèmes de manière systématique.
 
Cependant, une remarque s'impose ici. Cela va vous peut-être paraître évident, mais tout ce qu'on a fait ici n'a rien à voir avec le hasard. Le tirage de la loterie est juste un exemple : on peut imaginer des situations tout à fait analogue qui ne font pas appel au hasard. Par exemple, on peut se demander combien de manière différente 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 : quel est la probabilité de chaque tirage ? Mais on est plus alors dans le domaine de la combinatoire ; c'est la théorie des probabilités qui s'occupent de ce genre de questions.
 
== Répartition d'objets dans des boîtes ==
 
Avançons avec notre deuxième exemple. Imaginons qu'on ait cinq 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 ?
Là encore, il y a plusieurs manières de procéder :
 
*Est-ce que les objets sont '''discernables''' ? En autre mot, 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 objtes. 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. Voici l'ensemble des réponses :
 
(Faire ici jolie image ou tableau)
 
Il y a donc ... possibilité. Comique : ce nombre est le même que quand on a considéré le tirage de deux nombres parmi 4 avec répétition et en considérant l'ordre comme important. Pourtant, faire un tirage au sort et répartir des objets dans une boîte paraissent être des opérations fort différentes. Est-ce qu'il y a un lien entre ces deux situations ? Nous verrons cela plus tard. Si vous en avez le courage vous pouvez essayer de changer les chiffres et voir si les réponses sont toujours les mêmes.
 
== Ensemble des sous-ensemble ==
 
En fait, une force de la combinatoire est que l'on peut utiliser des formules similaires pour des cas qui paraissent sacrément différents. Sa faiblesse – vous vous en rendrez compte - est qu'il est souvent difficile de savoir quelle formule appliquer dans quel cas.
 
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.
Puisque cela peut paraître un peu abstrait dis comme cela, nous allons commencer par décrire des exemples de situation pour lesquelles on peut utiliser la combinatoire. Cela vous donnera un aperçu des choses que vous serez capables de faire à la fin de cours.
Vous pouvez aussi en profiter pour lire ce cours sur la théorie des ensembles pour ensuite revenir profiter de celui-ci ;-)
 
[[Catégorie:{{BASEPAGENAME}}|{{SUBPAGENAME}}]]