Inégalité de réarrangement - Définition

Démonstration

La minoration est obtenue en appliquant la majoration à

Il suffit donc de démontrer la majoration. Comme est un ensemble fini, il existe au moins une permutation σ telle que

soit maximal. Si il existe plusieurs permutations maximales, notons σ une des permutations maximales, choisie parmi les permutations maximales qui possèdent le plus grand nombre de points fixes (s'il y en a plusieurs).

On va démontrer par l'absurde que σ est nécessairement l'élément identité de . Supposons donc que σ n'est pas l'identité. Alors il existe un j dans tel que σ(j) ≠ j et σ(i) = i pour tout i dans  : j est le plus petit élément de qui ne soit pas un point fixe. Alors σ(j) > j, puisque tous les éléments de ont un antécédent autre que j. Par ailleurs, il existe tel que σ(k) = j, puisque tous les éléments de ont une image autre que j. Maintenant :

Par conséquent,

En développant et en réordonnant, on obtient :

On remarque que la permutation τ définie par

obtenue à partir de σ en échangeant les valeurs de σ(j) et σ(k), possède au moins un point fixe de plus que σ, à savoir j, et aucun point fixe de moins puisque le seul autre élément dont l'image change, l'élément k, n'était pas un point fixe. De plus, les deux sommes, et ne diffèrent qu'en les deux termes indexés par j et k. Ainsi, la permutation τ réalise le maximum tout autant que la permutation σ, puisque (3) se réécrit :

Finalement, (3') est en contradiction avec le choix de σ.

Si

alors les inégalités (1), (2), et (3) sont strictes, donc le maximum ne peut être atteint qu'en l'identité, tout autre permutation τ étant strictement suboptimale.