Proof concerning Stirling numbers of the first kind
How do I show that
$${ n\brack 2} = \frac{n!}{2} \sum_{m=1}^{n-1} \frac{1}{m(n-m)}$$
using a combinatorial argument?
My definition of ${n \brack 2}$ is "the number of elements of $S_n$ which can be decomposed as the product of exactly $2$ disjoint cycles".
Solution 1:
The (standard) combinatorial interpreation of $\begin{bmatrix}n\\ i\end{bmatrix}$ is as permutations of $n$ into $i$ (disjoint) cycles; we are interested in the case $i=2$.
Consider a permutation of $n$ into two cycles of length $\color{red}{m}$ and $\color{blue}{n-m}$
\begin{eqnarray*}
\color{red}{(a_1 a_2 \cdots a_m)} \color{blue}{(b_1 b_2 \cdots b_{n-m})}.
\end{eqnarray*}
The set $n$ can be partitioned into two (disjoint) sets of size $\color{red}{m}$ and $\color{blue}{n-m}$ in $\binom{n}{m}$ ways, the elements in the first cycle can be arranged in $\color{red}{(m-1)!}$ ways & the elements in the second cycle can be arranged in $\color{blue}{(n-m-1)!}$ ways, as $m$ ranges from $1$ to $n-1$ we will double count the possible configurations, thus
\begin{eqnarray*}
\begin{bmatrix}n\\ 2\end{bmatrix} = \frac{1}{2} \sum_{m=1}^{n-1} \binom{n}{m} \color{red}{(m-1)!} \color{blue}{(n-m-1)!} = \frac{n!}{2} \sum_{m=1}^{n-1} \frac{1}{\color{red}{m}\color{blue}{(n-m)}}.
\end{eqnarray*}
Solution 2:
I am going to outline different proofs, related with different definitions of Stirling numbers of the first kind. An initial observation is that by partial fraction decomposition $$ \sum_{m=1}^{n-1}\frac{1}{m(n-m)} = \frac{1}{n}\sum_{m=1}^{n-1}\left(\frac{1}{m}+\frac{1}{n-m}\right) = 2\,H_{n-1} $$ so the problem can be stated as "show that ${n \brack 2}=(n-1)! H_{n-1}$".
In terms of exponential generating functions, the problem of finding an explicit form for ${n\brack 2}$, defined as in OP's question above, boils down to finding the coefficients of the Taylor series of $\log^2(1-x)$. Since $-\log(1-x)=\sum_{n\geq 1}\frac{x^n}{n}$, by multiplying both sides by $\frac{1}{1-x}$ we get $\sum_{n\geq 1}H_n x^n = -\frac{\log(1-x)}{1-x}$ and by integrating both sides we get
$$ \log^2(1-x) = \sum_{n\geq 1}\frac{2\,H_n}{n+1}\,x^{n+1} = \sum_{n\geq 2}\frac{2\,H_{n-1}}{n}\,x^n. $$
An alternative definition of ${n\brack 2}$ is "the coefficient of $x^2$ in the polynomial $x^{(n)}=x(x+1)\cdots(x+n-1)$". With such a definition, ${n\brack 2}$ is the coefficient of $x$ in the polynomial $p(x) = (x+1)^{(n-1)}=(x+1)\cdots(x+n-1)$, i.e. $p'(0)$. Since $p(x)$ is given by a simple product, it is quite practical to express $p'$ in terms of the logarithmic derivative of $p$. We have
$$ p'(x) = p(x)\cdot\frac{d}{dx}\log p(x) = \left[\frac{1}{x+1}+\ldots+\frac{1}{x+n-1}\right](x+1)\cdots(x+n) $$ and by evaluating both sides at $x=0$ we get ${n\brack 2}=(n-1)! H_{n-1}$ as wanted.