Let $n>1$ be an integer and let $f_1$, $f_2$, ..., $f_{n!}$ be the $n!$ permutations of $1$, $2$, ..., $n$. (Each $f_i$ is a bijective function from $\{1,2,...,n\}$ to itself.) For each permutation $f_i$, let us define $S(f_i)=\sum^n_{k=1} |f_i(k)-k|$. Find $\frac{1}{n!} \sum^{n!}_{i=1} S(f_i)$.
1. We start with the given expression:
   \[
   \frac{1}{n!} \sum_{i=1}^{n!} S(f_i)
   \]
   where \( S(f_i) = \sum_{k=1}^n |f_i(k) - k| \).

2. We can rewrite the sum as:
   \[
   \frac{1}{n!} \sum_{i=1}^{n!} \sum_{k=1}^n |f_i(k) - k|
   \]
   By changing the order of summation, we get:
   \[
   \frac{1}{n!} \sum_{k=1}^n \sum_{i=1}^{n!} |f_i(k) - k|
   \]

3. For each fixed \( k \), \( f_i(k) \) takes each value from 1 to \( n \) exactly \((n-1)!\) times among the \( n! \) permutations. Therefore:
   \[
   \sum_{i=1}^{n!} |f_i(k) - k| = (n-1)! \sum_{\ell=1}^n |\ell - k|
   \]

4. Substituting this back into our expression, we get:
   \[
   \frac{1}{n!} \sum_{k=1}^n (n-1)! \sum_{\ell=1}^n |\ell - k|
   \]
   Simplifying, we have:
   \[
   \frac{1}{n} \sum_{k=1}^n \sum_{\ell=1}^n |\ell - k|
   \]

5. Next, we need to evaluate \( \sum_{\ell=1}^n |\ell - k| \). This sum can be split into two parts:
   \[
   \sum_{\ell=1}^n |\ell - k| = \sum_{\ell=1}^{k-1} (k - \ell) + \sum_{\ell=k+1}^n (\ell - k)
   \]
   The first sum is:
   \[
   \sum_{\ell=1}^{k-1} (k - \ell) = k(k-1) - \sum_{\ell=1}^{k-1} \ell = k(k-1) - \frac{(k-1)k}{2} = \frac{k(k-1)}{2}
   \]
   The second sum is:
   \[
   \sum_{\ell=k+1}^n (\ell - k) = \sum_{\ell=k+1}^n \ell - k(n-k) = \frac{(n+k+1)(n-k)}{2} - k(n-k)
   \]
   Simplifying the second sum:
   \[
   \frac{(n+k+1)(n-k)}{2} - k(n-k) = \frac{n^2 - k^2 + n - k}{2} - k(n-k) = \frac{n^2 - k^2 + n - k - 2k(n-k)}{2} = \frac{n^2 - k^2 + n - k - 2kn + 2k^2}{2} = \frac{n^2 - kn + k^2 + n - k}{2}
   \]

6. Combining both parts, we get:
   \[
   \sum_{\ell=1}^n |\ell - k| = \frac{k(k-1)}{2} + \frac{n^2 - kn + k^2 + n - k}{2} = \frac{k^2 - k + n^2 - kn + k^2 + n - k}{2} = \frac{2k^2 - k + n^2 - kn + n - k}{2}
   \]

7. Summing over \( k \) from 1 to \( n \):
   \[
   \sum_{k=1}^n \sum_{\ell=1}^n |\ell - k| = \sum_{k=1}^n \frac{2k^2 - k + n^2 - kn + n - k}{2}
   \]

8. Simplifying further, we get:
   \[
   \frac{1}{n} \sum_{k=1}^n \sum_{\ell=1}^n |\ell - k| = \frac{1}{n} \sum_{k=1}^n \frac{2k^2 - k + n^2 - kn + n - k}{2}
   \]

9. Finally, we simplify the expression to get:
   \[
   \frac{2}{n} \sum_{m=1}^n m(n-m) = \frac{2}{n} \left( \frac{n^2(n+1)}{2} - \frac{n(n+1)(2n+1)}{6} \right) = \frac{n^2 - 1}{3}
   \]

The final answer is \(\boxed{\frac{n^2 - 1}{3}}\).