Función de promedio sobre todas las permutaciones

Question

Esta es la solución oficial del problema A5 de IMO 2017. A continuación, proporcionaré extractos que me plantean preguntas, para aquellos que estén interesados en la solución en su totalidad, aquí está el enlace al PDF: https://www.imo-official.org/problems/IMO2017SL.pdf

Fragmento de solución 1 que se usa en solución 2:

---

---

La parte que no entiendo está justo en medio de la solución, comenzando con las palabras "donde la igualdad se cumple porque hay $kl$ productos en $M$, de los cuales se seleccionan $2l$ para cada $\phi$...".

La razón por la que esta igualdad se cumple puede demostrarse contando en cuántas permutaciones aparece cada término $x_ix_j$. Por ejemplo, cada término de $M$ puede contarse para aparecer en $2l(l-1)!(k-1)!$ permutaciones, lo que conduce al mismo resultado.

Lo que no entiendo es su línea de razonamiento... La parte de "hay $kl$ productos en $M$, de los cuales se seleccionan $2l$ para cada $\phi$". Sospecho que se trata de algún tipo de doble conteo para la media, pero aún no entiendo cómo logran específicamente esto. ¿Quizás hay alguna fórmula para sumas sobre permutaciones? ¿Alguien puede explicar, por favor?

Answer 1

Hay $kl$ productos en $M$ ya que hay $k$ formas de elegir $i\in S$ y $l$ formas de elegir $j \in T$.

Para cada $\phi$, los productos $x_{\phi(1)}x_{\phi(2)}, \ x_{\phi(2)}x_{\phi(3)},\dots x_{\phi(2l)}x_{\phi(2l+1)}$ están todos en $M$, lo que hace un total de $2l$ productos. Además, cada producto en $M$ aparecerá un número igual de veces en $\sum f(\phi)$. Si esto no es obvio, note que hay el mismo número de permutaciones con $\phi(1)=i, \ \phi(2)=j$ para cualquier $i\in S, j\in T$.

De manera similar, hay $k\choose 2$ productos en $K$. Para cada $\phi$, los productos $x_{\phi(2l+1)}x_{\phi(2l+2)},\dots x_{\phi(n-1)}x_{\phi(n)}$ están todos en $K$. Hay $n-2l-1=k-l-1$ productos para cada $\phi$. Nuevamente, cada producto en $K$ aparecerá un número igual de veces en $\sum f(\phi)$.

Answer 2

No aceptaré la respuesta de Angela Richardson, pero me empujó en la dirección correcta para llegar a mi propia explicación, la cual publicaré como respuesta, mientras Angela está recibiendo un voto positivo de mi parte.

Lo que me di cuenta que estaba luchando era entender cómo exactamente $k!l!$ en el lado izquierdo de la ecuación desaparece al pasar al lado derecho. Tenía la fuerte sensación de que podía entenderse mediante el doble conteo, simplemente no entendía cómo hacerlo, pero ahora lo sé.

Entonces, cada producto en $M$ aparece un número igual de veces en $\sum f(\phi)$. Lo denotamos como $x$. Hay $kl$ términos en $M$, por lo que en total habrá $klx$ de productos de $M$ en $\sum f(\phi)$.

Cada permutación selecciona $2l$ de los productos de $M$ y hay $k!l!$ permutaciones, por lo que en total hay $2lk!l!$ de productos de $M$ en $\sum f(\phi)$.

Ahora $klx = 2l\cdot k!\cdot l!$ o $x=2l\cdot k!\cdot l!/(kl)$. Así que $$ \frac{1}{k!l!}\sum f(\phi)=\frac{x M}{k!l!} + \ldots=\frac{2l}{kl}M+\ldots, $$ donde $\ldots$ signfican los términos que corresponden a los productos de $K$. Se pueden manejar de manera similar.