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".


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*}


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.