Averaging function over all permutations

Question

This is from IMO 2017 A5 problem's official solution. I'm gonna provide excerpts that raise questions in me below, for those who are interested in the solution in its entirety here's the link to pdf: https://www.imo-official.org/problems/IMO2017SL.pdf

Bit from solution 1 that is used in solution 2:

---

---

Part that don't I understand is right in the middle of the solution starting with words "where the equality holds because there are $kl$ products in $M$, of which $2l$ are selected for each $\phi$...".

Why this equality holds can be proven by counting in how many permutations each term $x_ix_j$ appears. For example, each term from $M$ can be counted to appear in $2l(l-1)!(k-1)!$ permutations, which leads to the same result.

What I don't understand is their line of reasoning... The "there are $kl$ products in $M$, of which $2l$ are selected for each $\phi$" part. I suspect this is some sort of double-counting for the average, but I'm still not getting how specifically they achieve it. Perhaps, there's some formula for sums over permutations? Can someone, please, explain?

Answer 1

There are $kl$ products in $M$ since there are $k$ ways to choose $i\in S$ and $l$ ways to choose $j \in T$.

For each $\phi$, the products $x_{\phi(1)}x_{\phi(2)}, \ x_{\phi(2)}x_{\phi(3)},\dots x_{\phi(2l)}x_{\phi(2l+1)}$ are all in $M$, which makes a total of $2l$ products. Moreover, every product in $M$ will appear an equal number of times in $\sum f(\phi)$. If this is not obvious, note that there are the same number of permutations with $\phi(1)=i, \ \phi(2)=j$ for any $i\in S, j\in T$.

Similarly, there are $k\choose 2$ products in $K$. For each $\phi$, the products $x_{\phi(2l+1)}x_{\phi(2l+2)},\dots x_{\phi(n-1)}x_{\phi(n)}$ are all in $K$. There are $n-2l-1=k-l-1$ products for each $\phi$. Again, every product in $K$ will appear an equal number of times in $\sum f(\phi)$.

Answer 2

I won't be accepting Angela Richardson's answer, but it nudged me in the right direction to come up with my own explanation, which I'll post as an answer, while Angela is getting an up-vote from me.

What I now realize I struggled with was understanding how exactly $k!l!$ on the left side of the equation disappears as you transition to the right side. I had a strong feeling it could be understood by double-counting, I just didn't understand how to perform it, but now I know.

So every product in $M$ appears an equal number of times in $\sum f(\phi)$. We denote it as $x$. There are $kl$ terms in $M$, so in total there will be $klx$ of $M$-products in $\sum f(\phi)$.

Each permutation selects $2l$ of $M$-products and there are $k!l!$ permutations, so in total there are $2lk!l!$ of $M$-products in $\sum f(\phi)$.

Now $klx = 2l\cdot k!\cdot l!$ or $x=2l\cdot k!\cdot l!/(kl)$. So $$ \frac{1}{k!l!}\sum f(\phi)=\frac{x M}{k!l!} + \ldots=\frac{2l}{kl}M+\ldots, $$ where $\ldots$ signify the terms that correspond to $K$-products. They can be handled similarly.