Lemme des bergers
Le lemme des bergers est une propriété utilisée en mathématiques, notamment en analyse combinatoire.
Il peut s'énoncer au niveau élémentaire par :
- Si un ensemble E possède une partition en p sous-ensembles contenant chacun r éléments, alors E contient pr éléments.
Par exemple, un jeu de bridge possède une partition en quatre couleurs comportant chacune treize cartes, le nombre total de cartes est donc égal à cinquante-deux.
On utilise fréquemment ce lemme dans l'autre sens :
- Si on connait le nombre d'éléments de E, et si E admet une partition en p sous-ensembles à r élements (un des nombres p et r étant connu mais pas l'autre), on en déduit celui des nombres p et r qu'on ne connaissait pas.
L'étymologie du surnom de cette propriété vient de la forme imagée de la réciproque : Quand les bergers veulent compter leurs moutons, ils comptent les pattes et divisent par quatre.'
Une version plus abstraite du théorème s'énonce comme suit :
- Étant donnés deux ensembles finis, X et Y, et une application surjective f : X → Y telle que tout élément de Y ait exactement n antécédents dans X, alors on a Card(X) = n*Card(Y)