Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | +
Combinatoire
Une planche de l'encyclopédie de Diderot et d'Alembert
Une planche de l'encyclopédie de Diderot et d'Alembert

En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements.

En particulier la combinatoire (En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou...) s'intéresse aux méthodes permettant de compter les éléments dans des ensembles finis (combinatoire énumérative) et à la recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension...) des optima dans les configurations ainsi qu'à leur existence (combinatoire extrémale).

La combinatoire débute au XVIIe siècle, en même temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) que le calcul des probabilités. Initialement, cette partie avait pour objet (De manière générale, le mot objet (du latin objectum, 1361) désigne une entité définie dans un espace à trois dimensions, qui a une fonction précise, et qui...) la résolution des problèmes de dénombrement, provenant de l'étude des jeux de hasard (Dans le langage ordinaire, le mot hasard est utilisé pour exprimer un manque efficient, sinon de causes, au moins d'une reconnaissance de cause à effet d'un événement.). Elle se développa de façon significative sous l'influence du calcul des probabilités. Plus tard, elle se lia à la théorie des nombres et à la théorie des graphes.

Voici quelques exemples de situations donnant lieu à des questions d'analyse combinatoire :

  • les rangements de livres sur une étagère ;
  • les dispositions de personnes autour (Autour est le nom que la nomenclature aviaire en langue française (mise à jour) donne à 31 espèces d'oiseaux qui, soit appartiennent au genre Accipiter, soit constituent les 5 genres Erythrotriorchis, Kaupifalco, Megatriorchis,...) d'une table ronde ;
  • les tirages avec remise d'un certain nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de boules numérotées dans une urne ;
  • les placements de jetons sur un damier.

Quel est le nombre d'ordonnancements possibles des cartes d'un jeu de 52 cartes ?

Ce nombre est égal à 52! (le « ! » dénotant la factorielle). Il peut sembler étonnant que ce nombre, environ 8,065 817 517 094 × 1067, soit si grand. C'est environ 8 suivi de 67 zéros. Il est, par exemple, plus grand que le nombre d'Avogadro, égal à 6,022 × 1023 (nombre d'atomes (Un atome (du grec ατομος, atomos, « que l'on ne peut diviser ») est la plus petite partie d'un corps simple pouvant...) de carbone (Le carbone est un élément chimique de la famille des cristallogènes, de symbole C, de numéro atomique 6 et de masse atomique 12,0107.) 12 dans 12 grammes de carbone 12).

Permutations (dispositions, ordonnancements)

Permutation (En mathématiques, la notion de permutation exprime l'idée de réarrangement d'objets discernables. Une permutation de n objets distincts rangés dans un certain ordre, correspond à un...) (sans répétition) d'objets discernables

Comme exemple d'introduction, considérons le nombre de dispositions de six objets discernables dans six cases consécutives numérotées avec un et un seul objet par case. Chacun des objets peut être placé dans la première case, ce qui donne six possibilités d'occuper la première place. Une fois la première place occupée par l'un des objets, il reste encore cinq candidats pour la deuxième place, la deuxième place étant attribuée, il reste seulement quatre candidats pour la troisième place, et ainsi de suite. Pour l'avant-dernière place, il ne reste plus que deux objets, et une fois l'un des deux placé, la dernière place doit être occupée par le dernier objet.

Il y a ainsi 6 × 5 × 4 × 3 × 2 × 1 ou 6! = 720 possibilités de disposer six objets discernables.

Généralisation 

Nous allons voir que le nombre de dispositions de n éléments discernables est égal à n !

Une disposition des objets d'un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme...) E de cardinal n, dans n cases avec un et un seul objet par case, ou un ordonnancement des éléments de E se représente par une bijection (Une fonction f: X → Y est dite bijective ou est une bijection si pour tout y dans l’ensemble d'arrivée Y il existe un et un seul x dans l’ensemble de définition X tel que...) de {1, 2, …, n} dans E ou une permutation de E. Il est commode de représenter une telle bijection par un n-uplet (ou n-liste) d'éléments de E, (x1, x2, …, xn).

Théorème 

Il y a n! permutations (sans répétition) de n éléments.

En effet, pour former un n-uplet d'éléments de E, nous devons choisir un élément de E pour la première place du n-uplet et il y a n possibilités, il y a n - 1 choix possibles d'un élément de E pour la deuxième place, n - 2 pour la troisième etc. Il n'y a plus qu'un seul choix d'élément pour la dernière place. Donc au total ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un total est le résultat d'une addition, c'est-à-dire une...) n × (n-1) × (n-2) × … × 2 × 1 permutations.

Cette propriété se démontre par récurrence sur n.

Permutation avec répétition d'objets discernables

Pour déterminer le nombre des dispositions possibles d'objets de plusieurs classes et mutuellement indiscernables dans chaque classe, il est utile de considérer le nombre de dispositions possibles de ces objets en les supposant tous discernables, et ensuite de trouver combien de ces dispositions sont indiscernables. Le nombre des dispositions possibles de ces objets est égal au nombre de dispositions possibles des objets considérés comme discernables divisé par le nombre des dispositions indiscernables.

Par exemple, si nous devons déterminer le nombre total de dispositions d'objets dont deux sont d'une première classe, trois d'une deuxième classe et cinq d'une troisième classe, alors nous calculons le nombre total de dispositions de ces objets considérés comme discernables, ce qui donne (2 + 3 + 5)!, soit 3 628 800 dispositions possibles. Mais certaines dispositions restent inchangées lorsque les objets indiscernables d'une même classe sont échangés mutuellement, et il y a 2! × 3! × 5! soit 1 440 façons de permuter les objets de chacune de ces classes.

Nous obtenons au total 3 628 800 ÷ 1 440 = 2 520 dispositions différentes. Il s'agit aussi du nombre de permutations avec répétition de 10 éléments avec 2, 3 et 5 répétitions.

Généralisation 

Le nombre de permutations de n éléments, répartis dans k classes dont n1 sont de classe 1, n2 sont de classe 2, …, nk sont de classe k, indiscernables dans chaque classe, ou le nombre de permutations de n éléments avec n1, n2, …, nk répétitions, avec \left ( \sum^k_{i=1} n_i = n \right ), est égal à : \frac{n!}{n_1! n_2! \ldots n_k!}.

Arrangements (choix en tenant compte de l'ordre)

Arrangements sans répétition

Nous disposons de n objets discernables et nous voulons en placer k, en tenant compte de l'ordre, dans k cases numérotées de 1 à k avec un et un seul objet par case. Le nombre de dispositions est alors égal au nombre de k-listes distinctes formées à partir de ces objets. Au lieu de constituer un n-uplet, à partir de n objets discernables, nous formons ici des k-uplets avec k \le n \text{,} \left( x_1, x_2, \ldots, x_k \right) à partir de ces n objets tels que pour i \neq j, on ait x_i \neq x_j. Un tel k-uplet s'appelle un arrangement (La notion d'arrangement est utilisée en probabilités, et notamment pour les dénombrements en analyse combinatoire.) sans répétition de n éléments pris k à k.

Théorème 
Le nombre d'arrangements sans répétition de n éléments pris k à k est égal à A_n^k (égal à \frac{n!}{(n-k)!} si kn et à 0 sinon).

En effet, Il y a n choix possibles de l'objet qui occupe la première place du k-uplet, n-1 choix pour l'objet de la 2e place ; pour la ke, il ne reste plus que n-(k-1) objets et donc n-k+1 choix possibles. Le produit n \cdot (n-1) \ldots (n-k+1) s'écrit bien sous la forme : \frac{n!}{(n-k)!}.

Le cas n = k nous oblige alors à diviser par (0)! que l'on définit comme valant 1.

Arrangements avec répétition

Lorsque nous voulons placer des objets pris parmi n objets discernables dans k emplacements en tenant compte de l'ordre, ces objets pouvant apparaître plusieurs fois, le nombre de dispositions est alors égal au nombre de k-uplets formés à partir de ces n objets. Un tel k-uplet, avec kn, (x1, x2, …, xk) formé à partir de ces n objets s'appelle un arrangement avec répétition de n éléments pris k à k.

Comme chaque emplacement peut être occupé indifféremment par l'un quelconque de ces n objets, il y en a au total nk.

Quand nous tirons 11 fois l'un de 3 numéros en tenant compte de l'ordre d'apparition nous obtenons au total 311 = 177 147 tirages différents. Comme exemple tiré de la génétique, nous pouvons donner le nombre total de codons de base (triplets formés de quatre codes) : 43= 64.

Combinaisons (choix sans tenir compte de l'ordre)

Contrairement aux arrangements, les combinaisons sont des dispositions d'objets qui ne tiennent pas compte de l'ordre de placement de ces objets. Par exemple, si a, b et c sont des boules tirées d'une urne, abc et acb correspondent au même tirage. Il y a donc moins de combinaisons que d'arrangements.

Combinaison (Une combinaison peut être :) sans répétition

Si nous tirons sans remise k objets parmi n objets discernables, et nous les disposons sans tenir compte de l'ordre d'apparition, nous pouvons représenter ces k objets par une partie à k éléments d'un ensemble à n éléments. Ce sont des combinaisons sans répétition de n éléments pris k à k.

Pour déterminer le nombre de ces dispositions, nous pouvons déterminer le nombre d'arrangements de k objets et diviser par le nombre de dispositions obtenues les unes à partir des autres par une permutation. Il y a {n \choose k}=\frac{A_n^k}{k!} (pour la notation, voir aussi l'article sur le coefficient (En mathématiques un coefficient est un facteur multiplicatif qui dépend d'un certain objet, comme une variable (par exemple, les coefficients d'un polynôme), un espace vectoriel, une fonction de base et ainsi de suite....) binomial).

Au jeu du loto, nous devons choisir parmi 49 numéros, 6 numéros différents sans tenir compte de l'ordre, et il y a {49 \choose 6}=\frac{49!}{6! \cdot 43!}=13\,983\,816 choix possibles.

Sur le même principe, le jeu « euro-millions » demande de choisir 5 nombres entre 1 et 50 et 2 nombres entre 1 et 9, soit {50 \choose 5} \times {9 \choose 2}=76\,275\,360 possibilités.

Combinaison avec répétition

Si nous tirons avec remise k objets parmi n objets discernables, et nous les disposons sans tenir compte de l'ordre d'apparition; ces objets peuvent apparaître plusieurs fois et nous ne pouvons les représenter ni avec une partie à k éléments, ni avec un k-uplet puisque leur ordre de placement n'intervient pas. Il est cependant possible de représenter de telles dispositions avec des applications appelées combinaisons avec répétition.

Le nombre de combinaisons avec répétition de n éléments pris k à k est égal à : \Gamma_n^k={ n+k-1 \choose k}.

Donnons l'exemple du jeu de domino. Les pièces sont fabriquées en disposant côte à côte deux éléments de l'ensemble {blanc, 1, 2, 3, 4, 5, 6}. Si nous retournons un domino, nous changeons l'ordre des deux éléments, mais le domino reste identique. Nous avons une combinaison avec répétition de 7 éléments pris 2 à 2, et au total il y a : \Gamma_7^2={8 \choose 2}=28 dominos dans un jeu.

Fonction de comptage

Soit ?n l'ensemble des permutations de {1, 2, …, n}. Nous pouvons considérer la fonction qui à n associe le nombre de permutations. Cette fonction est la fonction factorielle (En mathématiques, la factorielle d'un entier naturel n, notée n!, ce qui se lit soit « factorielle de n » soit « factorielle n », est le produit des nombres entiers strictement positifs...) et sert à compter les permutations.

Étant donnée une collection infinie d'ensembles finis \left\{ E_n | n \in \mathbb{N} \right\} indexée par l'ensemble des entiers naturels, une fonction de comptage est une fonction qui à un entier n associe le nombre d'éléments de En. Une fonction de comptage f permet donc de compter les objets de En pour n'importe quel n. Les éléments de En ont habituellement une description combinatoire relativement simple et une structure additionnelle, permettant souvent de déterminer f.

Certaines fonctions de comptage, sont données par des formules « fermées », et peuvent être exprimées comme composées de fonctions élémentaires telles que des factorielles, des puissances, et ainsi de suite.

Cette approche peut ne pas être entièrement satisfaisante (ou pratique) pour certains problèmes combinatoires. Par exemple, soit f(n) le nombre de sous-ensembles distincts de nombres entiers dans l'intervalle [1, n] qui ne contiennent pas deux nombres entiers consécutifs. Par exemple, avec n = 4, nous obtenons ∅, { 1 }, { 2 }, { 3 }, { 4 }, { 1, 3 }, { 1, 4 }, { 2, 4 }, et donc f(4) = 8. Il s'avère que f(n) est le nème nombre de Fibonacci (Leonardo Fibonacci (Pise, v. 1170 - v. 1250) est un mathématicien italien. Fibonacci (de son nom moderne), connu à l'époque sous le nom de Leonardo Pisano (Léonard de Pise), mais aussi...), qui peut être exprimé sous la forme « fermée » suivante :

f(n)=\frac{\phi^n}{\sqrt{5}}-\frac{(1-\phi)^n}{\sqrt{5}}

φ = (1 + √5)/2, est le nombre d'or. Cependant, étant donné que nous considérons des ensembles de nombres entiers, la présence du √5 dans le résultat peut être considérée comme inesthétique d'un point (Graphie) de vue (La vue est le sens qui permet d'observer et d'analyser l'environnement par la réception et l'interprétation des rayonnements lumineux.) combinatoire. Aussi f(n) peut-il être exprimé par une relation de récurrence :

f(n) = f(n - 1) + f (n - 2)

ce qui peut être plus satisfaisant (d'un point de vue purement combinatoire), puisque la relation montre plus clairement comment le résultat a été trouvé.

Dans certains cas, un équivalent asymptotique g de f,

f(n)~g(n) quand n tend vers l'infini (Le mot « infini » (-e, -s ; du latin finitus, « limité »), est un adjectif servant à qualifier quelque chose qui n'a pas de...)

g est une fonction « familière », permet d'obtenir une bonne approximation (Une approximation est une représentation grossière c'est-à-dire manquant de précision et d'exactitude, de quelque chose, mais encore assez significative pour être utile. Bien qu'une approximation soit le...) de f. Une fonction asymptotique simple peut être préférable à une formule « fermée » extrêmement compliquée et qui informe peu sur le comportement du nombre d'objets. Dans l'exemple ci-dessus, un équivalent asymptotique serait :

f(n)\sim\frac{\phi^n}{\sqrt{5}}

quand n devient grand.

Une autre approche est celle des séries entières. f(n) peut être exprimé par une série entière formelle, appelée fonction génératrice de f, qui peut être le plus couramment :

  • la fonction génératrice ordinaire
\sum_{n > 0} f(n) \cdot x^n
  • ou la fonction génératrice exponentielle (La fonction exponentielle est l'une des applications les plus importantes en analyse, ou plus généralement en mathématiques et dans ses domaines...)
\sum_{n > 0} f(n) \cdot \frac{x^n}{n!}

Une fois déterminée, la fonction génératrice peut permettre d'obtenir toutes les informations fournies par les approches précédentes. En outre, les diverses opérations usuelles comme l'addition (L'addition est une opération élémentaire, permettant notamment de décrire la réunion de quantités ou l'adjonction de grandeurs extensives de même nature, comme les longueurs, les aires, ou les...), la multiplication (La multiplication est l'une des quatre opérations de l'arithmétique élémentaire avec l'addition, la soustraction et la division .), la dérivation, etc., ont une signification combinatoire ; et ceci permet de prolonger des résultats d'un problème combinatoire afin de résoudre d'autres problèmes.

Quelques résultats

Un théorème, dû à Franck P. Ramsey, donne un résultat surprenant. À une soirée à laquelle se rendent au moins six personnes, il y a au moins trois personnes qui se connaissent mutuellement ou au moins trois qui sont étrangères les unes aux autres.

Démonstration 

soit P1 une personne quelconque présente à la soirée. Sur les n-1 autres, soit elle en connaît au plus deux, soit elle en connaît au moins trois. Supposons que l’on est dans le second cas, et soient P_2,\, P_3 \text{ et } P_4 trois personnes connues de P1. Si deux d’entres elles se connaissent, mettons P2 et P3, alors P_1,\, P_2 \text{ et } P_3 se connaissent toutes trois. Sinon, P_2,\, P_3 \text{ et } P_4 ne se connaissent pas du tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.), et le résultat annoncé est encore juste. Dans l’autre cas de figure (P1 connaît au plus deux personnes du groupe), le même raisonnement, inversé, fonctionne avec les trois personnes que P1 ne connaît pas.

(C'est un cas particulier du théorème de Ramsey.)

L'idée de trouver un ordre dans des configurations aléatoires mène à la théorie de Ramsey. Essentiellement, cette théorie indique que n'importe quelle configuration suffisamment grande contiendra au moins un autre type de configuration.

Source: Wikipédia publiée sous licence CC-BY-SA 3.0.

Vous pouvez soumettre une modification à cette définition sur cette page. La liste des auteurs de cet article est disponible ici.