COMBINATOIRE ANALYSE

L'analyse combinatoire est l'ensemble des techniques qui servent, en mathématiques, à compter (ou dénombrer) certaines structures finies, ou à les énumérer (établir des listes exhaustives de structures considérées), enfin à démontrer leur existence pour certaines valeurs des paramètres dont elles dépendent. Ces structures sont très variées ; leur seul trait commun c'est d'être finies. En revanche, les problèmes qu'on se pose sur ces structures sont très divers, et les techniques mathématiques qu'on utilise pour résoudre ces problèmes, très différentes. Par exemple, si on veut dénombrer les arbres de n sommets, on établit une correspondance biunivoque entre l'ensemble de ces arbres et l'ensemble de certaines suites qu'on sait compter. Mais, si l'on veut démontrer l'existence d'une famille infinie de codes correcteurs, on utilise des résultats fins sur les anneaux de polynômes à coefficients dans un corps fini. Pourtant, dans les deux cas, on dit qu'on s'occupe d'analyse combinatoire. Dans le foisonnement des sujets dits de nature combinatoire, on a donc dû faire un choix et laisser de côté des objets importants.

Dénombrements élémentaires

Dans les opérations élementaires de dénombrement, on utilise un langage très proche du réel. On parle de choisir un objet de m façons différentes, on dit qu'il n'y a qu'un nombren de possibilités... Considérons ainsi l'exemple suivant. Une urne contient 10 boules numérotées de 1 à 10 ; on tire successivement deux boules de l'urne sans remettre la première après tirage. Combien y a-t-il de tirages croissants, c'est-à-dire de façons de tirer deux boules dont les numéros vont en croissant ? Pour déterminer ce nombre, on raisonne de la façon suivante. Si la première boule a été tirée et que son numéro est i (1 ≤ i ≤ 10), pour obtenir un tirage croissant, on peut choisir le numéro j de la seconde de 10 − i façons différentes. Enfin, pour obtenir un tirage croissant, on peut choisir soit un tirage commençant par le numéro 1, soit un tirage commençant par 2, etc. Le nombre de tirages croissants est alors égal à (10 − 1) + (10 − 2) + ... + (10 − 9) + (10 − 10) = 45. On a implicitement utilisé les deux règles suivantes (la seconde avant la première) :

– Règle de la somme : Si on peut choisir un objet a de m façons et un objet b de n façons, on peut choisir a ou b de m + n façons.

– Règle du produit : Si on peut choisir un objet a de m façons, puis un objet b de n façons, on peut choisir a puis b, dans cet ordre, de mn façons.

Reprenons l'exemple ci-dessus. Pour caractériser un tirage, il suffit de se donner un couple (i, j) d'entiers tels que i et j soient compris entre 1 et 10. Désignons par X l'ensemble des couples (i, j) tels que 1 ≤ i < j ≤ 10. Les tirages croissants correspondent aux éléments de X et, pour trouver le nombre de tirages croissants, il suffit de dénombrer l'ensemble X, c'est-à-dire de compter le nombre de ses éléments. Pour 1 ≤ h ≤ 10, notons X_h l'ensemble des couples (i, j) de X tels que i = h ; ainsi X_h est le produit cartésien des ensembles {h} et {h + 1, h + 2, ..., 10}. De plus, les ensembles X_h sont disjoints deux à deux et leur réunion est X. Désignons par |X_h| le nombre des éléments de X_h ; alors en posant k = 10, le nombre, noté |X| des éléments de X est donné par :

De plus, pour 1 ≤ h ≤ 10, on a :

En appliquant les formules (1) et (2), on retrouve bien 45 pour le nombre des éléments de X. Dans cette dernière démarche, nous avons résolument adopté le langage de la théorie des ensembles et utilisé certains résultats sur les ensembles finis. D'abord comment caractérise-t-on les ensembles finis ? En premier lieu,[...]