Putnam 2005, Problem B-6

Let $S_n$ denote the set of all permutations of the numbers $1,2,\ldots,n$. For $\pi \in S_n$, let $\sigma(\pi) = 1$ if $\pi$ is an even permutation and $\sigma(\pi) = -1$ if $\pi$ is an odd permutation. Also, let $\nu(\pi)$ denote the number of fixed points of $\pi$. Show that $\sum_{\pi \in S_n} \frac{\sigma(\pi)}{\nu(\pi) + 1} = (-1)^{n+1} \frac{n}{n+1}$.


Solution:
First solution: Let \(I\) be the identity matrix, and let \(J_x\) be the matrix with \(x\)'s on the diagonal and 1's elsewhere. Note that \(J_x - (x - 1)I\), being the all 1's matrix, has rank 1 and trace \(n\), so has \(n - 1\) eigenvalues equal to 0 and one equal to \(n\). Hence \(J_x\) has \(n - 1\) eigenvalues equal to \(x - 1\) and one equal to \(x + n - 1\), implying
\[
\det J_x = (x + n - 1)(x - 1)^{n-1}.
\]
On the other hand, we may expand the determinant as a sum indexed by permutations, in which case we get
\[
\det J_x = \sum_{\pi \in S_n} \text{sgn}(\pi) x^{\nu(\pi)}.
\]
Integrating both sides from 0 to 1 (and substituting \(y = 1 - x\)) yields
\[
\sum_{\pi \in S_n} \frac{\text{sgn}(\pi)}{\nu(\pi) + 1} = \int_0^1 (x + n - 1)(x - 1)^{n-1} dx = \int_0^1 (-1)^{n+1} (n - y) y^{n-1} dy = (-1)^{n+1} \frac{n}{n + 1},
\]
as desired.

Second solution: We start by recalling a form of the principle of inclusion-exclusion: if \(f\) is a function on the power set of \(\{1,\ldots,n\}\), then
\[
f(S) = \sum_{T \supseteq S} (-1)^{|T| - |S|} \sum_{U \supseteq T} f(U).
\]
In this case we take \(f(S)\) to be the sum of \(\sigma(\pi)\) over all permutations \(\pi\) whose fixed points are exactly \(S\). Then \(\sum_{U \supseteq T} f(U) = 1\) if \(|T| \geq n - 1\) and 0 otherwise (since a permutation group on 2 or more symbols has as many even and odd permutations), so
\[
f(S) = (-1)^{n - |S|} (1 - n + |S|).
\]
The desired sum can thus be written, by grouping over fixed point sets, as
\[
\sum_{i=0}^n \binom{n}{i} (-1)^{n - i} \frac{1 - n + i}{i + 1} = \sum_{i=0}^n (-1)^{n - i} \binom{n}{i} - \sum_{i=0}^n (-1)^{n - i} \frac{n}{i + 1} \binom{n}{i} = 0 - \sum_{i=0}^n (-1)^{n - i} \frac{n}{n + 1} \binom{n + 1}{i + 1} = (-1)^{n+1} \frac{n}{n + 1}.
\]

Third solution: (by Richard Stanley) The cycle indicator of the symmetric group \(S_n\) is defined by
\[
Z_n(x_1,\ldots,x_n) = \sum_{\pi \in S_n} x_1^{c_1(\pi)} \cdots x_n^{c_n(\pi)},
\]
where \(c_i(\pi)\) is the number of cycles of \(\pi\) of length \(i\). Put
\[
F_n = \sum_{\pi \in S_n} \sigma(\pi) x^{\nu(\pi)} = Z_n(x,-1,1,-1,1,\ldots)
\]
and
\[
f(n) = \sum_{\pi \in S_n} \frac{\sigma(\pi)}{\nu(\pi) + 1} = \int_0^1 F_n(x) dx.
\]
A standard argument in enumerative combinatorics (the Exponential Formula) gives
\[
\sum_{n=0}^\infty Z_n(x_1,\ldots,x_n) \frac{t^n}{n!} = \exp \sum_{k=1}^\infty x_k \frac{t^k}{k},
\]
yielding
\[
\sum_{n=0}^\infty f(n) \frac{t^n}{n!} = \int_0^1 \exp \left( xt - \frac{t^2}{2} + \frac{t^3}{3} - \cdots \right) dx = \int_0^1 e^{(x - 1)t + \log(1 + t)} dx = \int_0^1 (1 + t) e^{(x - 1)t} dx = \frac{1}{t} (1 - e^{-t})(1 + t).
\]
Expanding the right side as a Taylor series and comparing coefficients yields the desired result.

Fourth solution (sketch): (by David Savitt) We prove the identity of rational functions
\[
\sum_{\pi \in S_n} \frac{\sigma(\pi)}{\nu(\pi) + x} = \frac{(-1)^{n+1} n! (x + n - 1)}{x(x + 1) \cdots (x + n)}
\]
by induction on \(n\), which for \(x = 1\) implies the desired result. (This can also be deduced as in the other solutions, but in this argument it is necessary to formulate the strong induction hypothesis.) Let \(R(n,x)\) be the right hand side of the above equation. It is easy to verify that
\[
R(x,n) = R(x + 1,n - 1) + (n - 1)! \frac{(-1)^{n+1}}{x} + \sum_{l=2}^{n-1} (-1)^{l-1} \frac{(n - 1)!}{(n - l)!} R(x,n - l),
\]
since the sum telescopes. To prove the desired equality, it suffices to show that the left hand side satisfies the same recurrence. This follows because we can classify each \(\pi \in S_n\) as either fixing \(n\), being an \(n\)-cycle, or having \(n\) in an \(l\)-cycle for one of \(l = 2,\ldots,n - 1\); writing the sum over these classes gives the desired recurrence.