Combinatoire/Introduction

Début de la boite de navigation du chapitre

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 au début de leur parcours scolaire : nous allons apprendre à compter des objets.
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 $\pi$, ${\sqrt {2}}$ et autres nombres irrationnels), seulement les bons vieux entiers naturels. Rien de très compliqué donc !

fin de la boite de navigation du chapitre

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¹⁰⁰, nos ordinateurs les plus puissants hisseraient le drapeau blanc.

Heureusement, vous savez qu'en mathé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 nous contenter de la première approche. Je vais ici vous présenter 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 ».

Exemples de problèmes de combinatoire

Le tirage au sort de la loterie

De combien de manières peut-on cocher 6 cases dans une grille de 49 nombres ?

Je suppose que vous savez ce qu'est une loterie : vous choisissez un ensemble de nombres 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 a, par exemple, cinq nombres tirés parmi 50. On peut se poser la question de savoir combien de tirages sont possibles. Évidemment, le nombre de tirages possibles d'une loterie normale est colossal, donc nous allons nous contenter d'une version plus simple. Imaginons un tirage au sort de 2 chiffres parmi 4 : 0, 1, 2, 3.

Combien de tirages 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.

...

(Ce n’est pas une blague. Essayez vraiment ; prenez un bic, une feuille, et essayez d'écrire tous les tirages possibles, sans en oublier)

...

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 a 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.
• Soit les chiffres ne peuvent pas apparaître plusieurs fois, soit ils peuvent. Dans le premier cas on parle de tirage sans remise, dans le second cas de tirage avec remise ; il faut imaginer que dans le premier cas, la personne qui tire au sort laisse le premier chiffre tiré sur le côté 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 remise.

Voilà un joli tableau à double entrée qui résume l’ensemble des tirages possibles:

Tableau de tous les tirages possibles.
En rouge, les tirages comptés dans tous les cas.
En bleu, les tirages comptés uniquement si le tirage permet les répétitions.
En vert, les tirages comptés uniquement si le tirage tient compte de l'ordre.

	0	1	2	3
0	0 puis 0	0 puis 1	0 puis 2	0 puis 3
1	1 puis 0	1 puis 1	1 puis 2	1 puis 3
2	2 puis 0	2 puis 1	2 puis 2	2 puis 3
3	3 puis 0	3 puis 1	3 puis 2	3 puis 3

Les possibilités en rouge sont toujours comptées. Celles en bleu sont celles où le même chiffre est tiré deux fois de suite ; ce n'est possible que si le tirage est « avec remise ». Celles en vert ont chacun un jumeau qui présente les mêmes chiffres dans le sens contraire ; elles ne sont comptées que si l’ordre est considéré comme important. Si on compte, on obtient les résultats suivants :

Nombre de tirages possibles, selon la manière de les compter

	Sans remise	Avec remise
Ordre important	12 (rouge + vert)	16 (rouge + bleu + vert)
Ordre sans importance	6 (rouge)	10 (rouge + bleu)

Nous verrons plus tard comment résoudre ce genre de problèmes de manière systématique. En fait, les quatre cas qui figurent dans ce tableau correspondent à quatre des six types de disposition que l’on étudiera dans ce cours. Gardez en tête l'image d'un tirage au sort, il s'agit d'un exemple facile à imaginer.

Une remarque s'impose ici. Cela va peut-être vous paraître évident, mais tous les calculs faits ici n'ont aucun rapport avec le hasard en jeu lors du tirage à la loterie. Il s'agit juste d'un exemple : on peut imaginer des situations tout à fait analogues qui ne font pas appel au hasard. Par exemple, on peut se demander combien de manières diffé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 : quelle est la probabilité de chaque tirage ? Mais ce n'est plus alors dans le domaine de la combinatoire ; c’est la théorie des probabilités qui s'occupe de ce genre de questions.

Répartition d'objets dans des boîtes

Avançons avec notre deuxième exemple. Imaginons qu'on ait quatre 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 objets dans les boites? Là encore, il y a plusieurs manières de procéder :

• Est-ce que les objets sont discernables ? En d'autres mots, est-ce que ce sont tous les mêmes – et dans ce cas, seul le nombre d'objets qu'on met dans chaque boîte à de l'importance – où est-ce qu’ils sont tous différents ?
  Par exemple, si on considère les objets comme indiscernables, les dispositions
  Boîte A contient {1, 2, 3} et Boîte B contient {4}
  ou bien
  Boîte A contient {2, 3, 4} et Boîte B contient {1}
  sont considérées comme identiques et ne sont comptées 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 objets. Par exemple, les dispositions
  Boîte A contient {1, 2, 3} et Boîte B contient {4}
  ou bien
  Boîte B contient {1, 2, 3} et Boîte A contient {4}
  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ù les objets et les boîtes sont discernables. Essayez de faire la liste avant de regarder la réponse. Voici l’ensemble des réponses :

Il y a donc 16 possibilités en tout.

Ensemble des sous-ensembles

Vous aurez peut-être remarqué que la réponse à l'exercice précédent est la même que l'une des réponses pour l'exemple de la loterie. Ce n’est pas un hasard: en effet, mathématiquement le problème s'exprimerait de la même manière, et ce bien que les deux problèmes posés paraissent très différents. Ce sont tous les deux des « arrangements avec répétition », un des cas théoriques que l’on étudiera plus tard. Nous allons apprendre dans la suite de ce cours à distinguer un certain nombre de ces cas théoriques, et à trouver des formules générales qui permettent de les résoudre ; toute la difficulté sera pour vous de relier chaque problème avec sa formule.

La théorie des ensembles offre le cadre théorique idéal, d’une part pour démontrer formellement les différentes formules, d’autre part pour « abstraire » toutes les situations possibles et les réduire à quelques cas typiques. Vous vous apercevrez que la difficulté du cours est d’avoir suffisamment d'intelligence pour distinguer les différents cas et rattacher le problème qui vous préoccupe au bon. Si vous avez une bonne intuition, vous pourrez vous débrouillez, mais les risques de confusion existent. Le langage de la théorie des ensembles, lui, est sans ambiguïté une fois que l’on a appris à le comprendre.

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és 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 ;-)

Voyons un exemple de question de combinatoire qui fait intervenir la théorie des ensembles. Soit un ensemble A contenant 4 éléments. Soit B l’ensemble des sous-ensembles de l’ensemble A. Quel est le cardinal de B (c'est-à-dire combien existe-il de sous-ensembles de A ?)

Visualisons la situation via un schéma très moche:

Si vous savez compter, vous remarquerez que le nombre de sous-ensembles est de 16.

Suite du cours

À propos de l’utilisation de ce cours

À la fin de chaque chapitre, nous vous conseillerons une liste d'exercices à faire avant de progresser plus loin. La plupart permettent d'appliquer les formules qui viennent d’être vues. L'accent sera mis sur les exercices les plus fondamentaux, ceux qui sont nécessaires pour pouvoir comprendre la suite ; n'hésitez pas évidemment à faire les exercices facultatifs et plus compliqués.

Ce cours n'est sans doute pas parfait, alors si vous passez par là et que vous avez des commentaires, je vous encourage à les laisser sur la page de discussion de ce cours. Idem si vous voyez des erreurs comme une mauvaise correction d'un exercice : si vous ne savez pas faire la modification vous-même, signalez-nous l'erreur et nous nous en occuperons. Les questions sont évidemment les bienvenues !

Programme

Nous allons à partir de maintenant étudier 6 cas : les arrangements avec et sans répétition, les combinaisons avec et sans répétition, et les permutations avec et sans répétition. Mais avant cela, nous devrons introduire au chapitre suivant une notation mathématique qui nous servira beaucoup : la factorielle.

À faire avant le prochain chapitre

Il n'y a rien à faire avant le prochain chapitre ;-)