2.1 Introduction

À la base, tous les problèmes (ou presque) de combinatoire peuvent être résolus par une simple énumération. Placer les éléments en ordre croissant, en ordre alphabétique ou faire un diagramme en arbre sont certes des idées pouvant simplifier le travail, mais cette approche présente néanmoins beaucoup de désavantages. La principale étant tout simplement le temps nécessaire pour effectuer une énumération complète lorsque le nombre de possibilités est élevé. Un autre désavantage important est le risque élevé d’oublier un cas ou d’en énumérer un deux fois.

Au chapitre 1, nous avons introduit un ensemble de principes de base qui nous permettent de simplifier les choses. Ces principes nous permettent, entre autres, d’interpréter les différentes opérations arithmétiques en termes de problèmes de combinatoire, de sorte que nous puissions les utiliser directement pour calculer le nombre de possibilités. Par la même occasion, nous avons introduit un principe qui nous permet d’établir que deux problèmes ont autant de possibilités, ou qu’il existe au moins une possibilité. Ces principes sont à la base de toutes les questions de la combinatoire et sont probablement les premiers à avoir été développés historiquement.

Il existe deux autres approches pour résoudre les problèmes de combinatoire: Les récurrences et les fonctions génératrices. En théorie, tous les problèmes peuvent être résolus par l’une ou l’autre de ces approches, mais pour chaque problème, il y a toujours une approche plus évidente que les autres. Les récurrences que nous allons étudier dans ce chapitre sont particulièrement adaptées aux problèmes où il y a une ou des contraintes lié à la position d’un objet. Les fonctions génératrices que nous étudierons au prochain chapitre sont, pour leur part, particulièrement adaptées aux problèmes où il y a des contraintes sur la quantité.

Les principes de base, les récurrences et les fonctions génératrices forment le coeur de la combinatoire. Dans les chapitres 4 à 6, nous passerons ensuite au second palier et développerons la théorie des distributions. Il s’agit d’un ensemble de problèmes types qui apparaissent souvent en combinatoire et qui peuvent servir de modèle pour toute une variété de situations. Ces modèles incluront la question de savoir combien de façons il existe de choisir des objets et la question de placer des objets dans des urnes. Lors de notre étude de ces distributions, nous aurons l’occasion de résoudre certains problèmes avec les trois approches en même temps, ce qui nous donnera l’occasion de les comparer.

Bien que les récurrences nous permettent de résoudre de nombreux problèmes, trouver une formule explicite pour les résoudre est généralement difficile. Pour la plupart des problèmes que nous étudierons dans ce cours, il nous sera cependant possible de le faire, mais il nous faudra patienter jusqu’au chapitre 7. Pour le moment, nous allons utiliser Python pour nous permettre d’obtenir la valeur numérique, sans avoir à compléter de longs tableaux à la main.