Question 73
Let $n$ be a positive integer, let $S_n$ be the set of all permutations of the set $\{1, 2, \dots, n\}$, and, for each $\sigma$ in $S_n$, let $I(\sigma) = \{i: \sigma(i) \le i\}$. Evaluate the sum
$$
\sum_{\sigma \in S_n} \frac{1}{|I(\sigma)|} \sum_{i \in I(\sigma)} (i + \sigma(i)).
$$
$$
\sum_{\sigma \in S_n} \frac{1}{|I(\sigma)|} \sum_{i \in I(\sigma)} (i + \sigma(i)).
$$