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.
1. 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 nombre n 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 […]
… pour nos abonnés, l'article se prolonge sur 8 pages…
