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

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'ensemblel’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'ensemblel’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 ».

[[ImageFichier:Lottoschein.jpg|thumb|De combien de manières peut-on cocher 6 cases dans une grille de 50 nombres ?]]

* 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'ensemblel’ensemble des tirages possibles:

* 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 ? <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é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 <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.

Voici l'ensemblel’ensemble des réponses :

[[ImageFichier:Nombre_arrangements_avec_repetition.png|300px]]

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'ensemblel’ensemble des sous-ensembles de l'ensemblel’ensemble A. Quel est le cardinal de B (c'est-à-dire combien existe-il de sous-ensembles de A ?)

[[ImageFichier:EnsembleCombi.png|300px|Ensemble A et ses 16 sous-ensembles]]