RO-TST 2014 Problem 16

Let $n \in \mathbb{N}$ and $S_{n}$ the set of all permutations of $\{1,2,3,...,n\}$ . For every permutation $\sigma \in S_{n}$ denote $I(\sigma) := \{ i: \sigma (i) \le i \}$ . Compute the sum $\sum_ {\sigma \in S_{n}} \frac{1}{|I(\sigma )|} \sum_ {i \in I(\sigma)} (i+ \sigma(i))$ .