title: Inégalité de Lubell-Yamamoto-Meshalkin
text: # Inégalité de Lubell-Yamamoto-Meshalkin
  
  En mathématiques, l'inégalité de Lubell-Yamamoto-Meshalkin, ou inégalité LYM, est une inégalité combinatoire sur les tailles des ensembles d'une famille de Sperner, démontrée par Bollobás, Lubell, Meshalkin et Yamamoto.
  
  Elle a beaucoup d'applications en combinatoire ; en particulier, elle peut être utilisée pour démontrer le lemme de Sperner. Ce terme est aussi utilisé pour désigner des inégalités similaires.
  
  ## Énoncé
  
  Soient U un ensemble à n éléments, A une famille de parties de U dont aucune n'est incluse dans une autre, et $a_k$ le nombre de parties de taille k dans la famille A. Alors,
  
  $\sum _{k=0}^{n}{\frac {a_{k}}{n \choose k}}\leq 1.$
  
  ## Démonstration de Lubell
  
  Lubell (en 1966) démontre cette inégalité LYM par un argument de double dénombrement, dans lequel il dénombre les permutations de U = {1, … n} de deux façons. D'abord, par dénombrement direct, il y en a n!. Mais d'autre part, on peut choisir un membre S de la famille A et une bijection s : {1, … , |S|} → S, puis compléter s en une permutation de U. Si |S| = k, on lui associe ainsi k!(n – k)! permutations. Chaque permutation est associée à au plus un membre S de A. En effet par l'absurde, si s est une permutation associée à deux membres, S et T de A pris tels que |S|≤|T|, alors l'image de {1, … , |S|} par s est S, et est incluse dans T. Par conséquent, le nombre des permutations engendrées par cette construction est
  
  $\sum _{S\in A}|S|!(n-|S|)!=\sum _{k=0}^{n}a_{k}k!(n-k)!.$
  
  Comme ce nombre est au plus égal au nombre total de permutations,
  
  $\sum _{k=0}^{n}a_{k}k!(n-k)!\leq n!,$
  
  ce qui conclut.
  
  