Compter n'est jamais qu'une opération sur des ensembles : dénombrer les applications de l'un dans l'autre, les parties d'une certaine taille, les objets qui échappent à une liste de conditions. Et lorsque deux comptes tombent égaux, ce n'est pas une coïncidence numérique : c'est qu'il existe une bijection, que l'on peut exhiber. Cette planche énumère vraiment — chaque formule y est confrontée à la liste complète des objets qu'elle prétend compter.
Placer n boules numérotées dans k boîtes numérotées, c'est se donner une application de {1, …, n} dans {1, …, k}. Toutes les questions classiques du dénombrement sont des variantes : aucune condition, injective, surjective. La page les énumère une à une et compare à la formule.
La relation C(n,k) = C(n−1,k−1) + C(n−1,k) n'est pas une identité à vérifier : c'est le découpage de l'ensemble des parties à k éléments en deux paquets — celles qui contiennent n, et les autres. Cliquez une case pour voir les deux paquets.
Combien de permutations ne laissent aucun objet à sa place ? On part de toutes, on retire celles qui fixent 1, puis celles qui fixent 2… et l'on a trop retiré, donc on rajoute, puis on retire encore. C'est la formule du crible appliquée aux parties Ai = « i est fixé ».
Trois familles d'objets sans rapport apparent : les suites de parenthèses bien formées, les arbres binaires, les découpages d'un polygone en triangles. Elles ont le même nombre d'éléments — 1, 1, 2, 5, 14, 42, 132… — et ce n'est pas un hasard numérique : la même décomposition récursive les engendre, ce qui fournit la bijection.
Élément signature. Coloriez comme vous voulez, en deux couleurs, les quinze segments joignant six points : vous obtiendrez toujours un triangle d'une seule couleur. Avec cinq points, c'est évitable. La page passe en revue les 32 768 coloriages possibles de six points, un par un.