3. Construction de correspondances
Dans la première partie, nous avons passé en revue tous les ensembles finis qu'il était aisé de dénombrer en faisant usage des deux règles de la somme et du produit. Ces techniques élémentaires s'appliquent plus difficilement lorsqu'on veut dénombrer d'autres structures finies plus élaborées comme celles des arbres ou certains types de graphes. Le plus souvent on est conduit à chercher une correspondance biunivoque entre ces structures et les ensembles finis considérés dans la première partie. Jusqu'ici, il n'existe pas de théorie pour construire ces correspondances, tout est une question d'ingéniosité et de patience. À titre d'exemple, on peut décrire ci-dessous une telle correspondance entre les arbres de n sommets et les (n − 2)-uples (x1, x2, ..., xn-2), où les xi sont des entiers compris entre 1 et n.
Un graphe est la donnée d'un ensemble X – ses éléments sont les sommets du graphe – et d'une classe U de sous-ensembles de X à deux éléments, appelés arêtes. Si l'on a x, y ∈ X et {x, y} ∈ U, on dit que x et y sont adjacents. Une chaîne du graphe {X, U} est une suite {x1, y1}, {x2, y2}, ..., {xn, yn} d'arêtes distinctes telle que, lorsque n > 1, on ait :
… pour nos abonnés, l'article se prolonge sur 8 pages…
