Harvard-MIT Mathematics Tournament

Solution:

To solve this problem, we use the idea of a cycle in a permutation. If $\sigma$ is a permutation, we say that $(a_{1} a_{2} \cdots a_{k})$ is a cycle if $\sigma(a_{i})=a_{i+1}$ for $1 \leq i \leq k-1$ and $\sigma(a_{k})=a_{1}$. Any permutation can be decomposed into disjoint cycles; for instance, the permutation $3,7,6,4,5,1,2$ can be written as $(136)(27)(4)(5)$. For a permutation $\sigma$, let $g(\sigma)$ be the number of cycles in its cycle decomposition. (This includes single-element cycles.)

Claim. For any permutation $\sigma$ on $n$ elements, $f(\sigma)=n-g(\sigma)$.

Proof. Given a cycle $(a_{1} a_{2} \cdots a_{k})$ (with $k \geq 2$) of a permutation $\sigma$, we can turn this cycle into the identity permutation with $k-1$ transpositions; first we swap $a_{1}$ and $a_{2}$; that is, we replace $\sigma$ with a permutation $\sigma'$ such that instead of $\sigma(a_{k})=a_{1}$ and $\sigma(a_{1})=a_{2}$, we have $\sigma'(a_{k})=a_{2}$ and $\sigma'(a_{1})=a_{1}$. Now, $\sigma'$ takes $a_{1}$ to itself, so we are left with the cycle $(a_{2} \cdots a_{k})$. We continue until the entire cycle is replaced by the identity, which takes $k-1$ transpositions. Now, for any $\sigma$, we resolve each cycle in this way, making a total of $n-g(\sigma)$ transpositions, to turn $\sigma$ into the identity permutation.

This shows that $n-g(\sigma)$ transpositions suffice; now let us show that we cannot do it in less. We show that whenever we make a transposition, the value of $n-g(\sigma)$ can never decrease by more than $1$. Whenever we swap two elements, if they are in different cycles, then those two cycles merge into one; thus $n-g(\sigma)$ actually increased. If the two elements are in one cycle, then the one cycle splits into two cycles, so $n-g(\sigma)$ decreased by only one, and this proves the claim.

Thus, we want to find
$$\sum_{\sigma \in S_{7}} (7-g(\sigma)) = 7 \cdot 7! - \sum_{\sigma \in S_{7}} g(\sigma)$$
To evaluate the sum, we instead sum over every cycle the number of permutations it appears in. For any $1 \leq k \leq 7$, the number of cycles of size $k$ is $\frac{7!}{(7-k)!k}$, and the number of permutations each such cycle can appear in is $(7-k)!$. Thus we get that the answer is
$$7 \cdot 7! - \sum_{k=1}^{7} \frac{7!}{k} = 22212$$