Histoire des mathématiques Discipline

Combinatoire

Discipline

branche des mathématiques étudiant les combinaisons d'ensembles finis

domaine
mathématiques discrètes · Mathématiques

Pour comprendre

Pour préparer des emplois du temps, organiser des tirages ou choisir parmi plusieurs possibilités, il serait souvent trop long d'énumérer chaque cas. La combinatoire apprend à compter sans tout lister et à étudier les arrangements, les choix et les relations entre objets.

Ce qu'elle étudie

Elle dénombre les façons d'arranger, de choisir ou de relier des objets en nombre fini. Elle cherche aussi à savoir quelles configurations doivent exister dans une structure suffisamment grande, lorsque l'ordre finit par émerger.

La notation \(\binom{n}{k}\) désigne le nombre de façons de choisir k objets parmi n. Elle permet de calculer un nombre de choix sans examiner chaque sélection séparément.

$$\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$$

Le coefficient binomial se calcule avec les factorielles : n! est le produit des entiers de 1 à n.

À quoi elle sert

Elle permet de traiter des problèmes où les possibilités sont nombreuses mais où leur structure peut être organisée.

  • Dénombrer des mots de passe, des tirages et des plannings.
  • Étudier les graphes pour les réseaux sociaux, le routage et le GPS.
  • Organiser des tournées et des emplois du temps dans les problèmes d'ordonnancement et d'optimisation.
  • Analyser des algorithmes, des loteries et des jeux.

Comment elle s'organise

Le dénombrement étudie notamment permutations et combinaisons. La théorie des graphes, les approches extrémale, analytique et algébrique forment d'autres branches qui examinent réseaux, chemins et configurations.

mindmap
  root((Combinatoire))
    Dénombrement
      Permutations
      Combinaisons
    Théorie des graphes
      Réseaux et chemins
    Extrémale
      Théorie de Ramsey
    Analytique
    Algébrique

Cas d’usage

Comptons les anagrammes de MATHS, dont les cinq lettres sont différentes. Il y a cinq choix pour la première place. Une lettre utilisée n'est plus disponible : il reste quatre choix, puis trois, puis deux, puis un.

$$5!=5\times4\times3\times2\times1=120$$

Le signe \(5!\), lu « factorielle de cinq », désigne ce produit. Il y a donc 120 arrangements des lettres.

Comptons ensuite les codes à quatre chiffres. Les répétitions sont autorisées : choisir un chiffre ne retire aucun choix pour la place suivante. Chacune des places offre dix possibilités.

$$10\times10\times10\times10=10\,000$$

On obtient 10 000 codes possibles.

Construisons le podium d'une course de huit coureurs. On choisit d'abord qui reçoit l'or, puis l'argent, puis le bronze. Un coureur déjà placé ne peut pas occuper une autre marche :

$$8\times7\times6=336$$

Il y a 336 podiums. L'ordre compte : échanger les médailles de deux coureurs change le podium.

Choisissons maintenant cinq numéros parmi 49. Les mêmes numéros dans un autre ordre donnent la même grille. Compter leurs arrangements compterait chaque grille 120 fois. Le coefficient binomial compte directement les choix sans tenir compte de l'ordre :

$$\binom{49}{5}=1\,906\,884$$

On obtient 1 906 884 grilles différentes.

Comptons enfin les mains de cinq cartes dans un jeu de 52. Réordonner les cartes d'une main ne change pas les cartes qu'elle contient. On applique donc le même comptage, cette fois parmi 52 cartes :

$$\binom{52}{5}=2\,598\,960$$

Il y a 2 598 960 mains possibles.

Liens

a compté parmi ses contributeurs
porte le nom de
comprend
a pour branche

Sources