Bergers

Douze moutons rejoignent trois enclos, avec exactement quatre moutons dans chacun. Pour compter tous les moutons, il suffit alors de multiplier le nombre d’enclos par le nombre de moutons par enclos : 3 × 4 = 12.

Le lemme des bergers formalise ce comptage. On associe chaque objet à une catégorie et l’on vérifie que toutes les catégories ont le même nombre d’objets. Le total est le produit du nombre de catégories par cet effectif commun.

Le lemme des bergers est un résultat de dénombrement pour des ensembles finis. Soient un ensemble de départ X, un ensemble d’arrivée Y et une application f qui associe à chaque élément de X un élément de Y. L’application est surjective lorsque chaque élément de Y est atteint au moins une fois.

L’ensemble des éléments de X associés à un même élément y de Y est la fibre de y, autrement dit l’ensemble de ses antécédents. Si f est surjective et si chaque fibre contient exactement le même nombre n d’éléments, alors les fibres forment une partition de X en autant de parts qu’il y a d’éléments dans Y. On obtient :

La notation |X| désigne le nombre d’éléments de X, et |Y| celui de Y. Pour des ensembles finis, la preuve consiste à additionner les tailles de toutes les fibres. L’hypothèse d’un effectif constant est essentielle à cette forme multiplicative.

Un troupeau de 12 moutons est réparti dans 3 enclos. Chaque mouton rejoint un seul enclos et chaque enclos reçoit exactement 4 moutons. L’application associe donc un mouton à son enclos.

Données.
L’ensemble de départ X contient les moutons.
L’ensemble d’arrivée Y contient les 3 enclos.
Chaque enclos possède exactement 4 antécédents, donc n = 4.

Étape 1. Vérifier que chacun des 3 enclos est atteint : l’application est surjective.
Étape 2. Compter la fibre de chaque enclos : elle contient 4 moutons.
Étape 3. Multiplier le nombre d’enclos par la taille commune des fibres.

Le troupeau compte donc 12 moutons. Pour contrôler le résultat, on additionne directement les trois fibres : 4 + 4 + 4 = 12. La représentation des fibres rend ce double comptage visible.

Dans un problème de comptage, on choisit une application qui regroupe les objets en catégories. Si toutes les fibres ont la même taille, le lemme remplace une longue énumération par une multiplication.

Pour compter les objets d’une même classe d’équivalence, on associe chaque objet à sa classe. Lorsque toutes les classes ont le même cardinal, leur nombre multiplié par ce cardinal donne le total. Si leurs tailles diffèrent, il faut additionner les tailles classe par classe.

Le bon réflexe consiste à vérifier deux points avant tout calcul : chaque catégorie est-elle atteinte, et le nombre d’antécédents est-il vraiment constant ? Une réponse négative impose un comptage par fibres plutôt que la formule du lemme.

Surjection et injection. Une surjection exige que chaque élément de l’ensemble d’arrivée ait au moins un antécédent. Une injection exige que deux éléments distincts du départ n’aient jamais la même image. Dans l’exemple, quatre moutons ont le même enclos pour image : l’application est surjective, mais pas injective.

Lemme des bergers et principe multiplicatif. Le principe multiplicatif compte des choix successifs. Le lemme des bergers compte les éléments d’un ensemble par des fibres de même taille. Le calcul 3 × 4 a la même forme, mais ici les quatre moutons ne constituent pas quatre choix successifs.

Image et antécédent. L’enclos est l’image d’un mouton, tandis que les moutons qui y sont envoyés sont ses antécédents. Confondre les deux inverse le sens de l’application et empêche d’identifier les fibres à compter.

Fibres de tailles différentes. Si les trois enclos contiennent 3, 4 et 5 moutons, aucun nombre commun n convient. Il faut additionner 3 + 4 + 5, même si le total reste 12.

Catégorie vide. Si un quatrième enclos est vide, l’application vers les quatre enclos n’est pas surjective et les fibres n’ont pas toutes taille 4. Il faut retirer l’enclos vide de l’ensemble d’arrivée ou abandonner la formule uniforme.

Cas n = 0. Avec un ensemble d’arrivée non vide, zéro antécédent par élément contredit la surjectivité. Si l’ensemble d’arrivée est vide, une application depuis X vers lui n’existe que lorsque X est également vide.

Ensembles infinis. Le raisonnement par addition finie ne s’étend pas tel quel. En arithmétique des cardinaux infinis, multiplier par un entier non nul peut ne pas changer le cardinal ; l’égalité ne fournit alors plus le même outil de dénombrement numérique.

La fiche surjection précise la condition selon laquelle chaque élément de l’ensemble d’arrivée possède au moins un antécédent.

La fiche relation d’équivalence montre comment un ensemble se partage en classes, auxquelles le même comptage s’applique lorsque leurs tailles sont égales.

La fiche dénombrement replace ce double comptage parmi les techniques utilisées pour déterminer le nombre d’éléments d’un ensemble fini.