Using combinatorial argument to prove that ${ n\brack 3}=\frac{1}{2}\left(n-1\right)!\left[\left(H_{n-1}\right)^{2}-H_{n-1}^{\left(2\right)}\right]$

Question

Using combinatorial argument to prove that $${ n\brack 3}=\frac{1}{2}\left(n-1\right)!\left[\left(H_{n-1}\right)^{2}-H_{n-1}^{\left(2\right)}\right]$$

Where ${ n\brack k}$ denotes Stirling numbers of the first kind and $ H_{n}^{\left(m\right)}$ is the generalized harmonic number.

---

It should be shown that the number of permutations on $[n]$ with $3$ cycles is counted by the right-hand side. Assume the first element in each one of the cycles is the least element contained in that cycle and that the cycles are ordered increasingly according to their first element (the leftmost element is considered as the first element).

$$(a_{1}...a_{j_1})(a_{j_1+1}...a_{j_2})(a_{j_2+1}...n)$$

Based on the assumption $a_1=1$ and $1\le j_{1}\le n-2$, let's call the leftmost cycle left cycle and the two other right cycles. Summing all over possible ways to distribute the remaining $n-1$ elements to three cycles gives the following summation:

$$\sum_{\;\;\;\;\;\;k_{2},k_3\ge1,\\ k_{1}+k_{2}+k_{3}=n-1}^{ }\binom{n-1}{k_1}\binom{n-1-k_1}{k_2}\binom{n-1-k_1-k_2}{k_3}(k_1)!(k_2-1)!(k_3-1)!$$

$$=\left(n-1\right)!\sum_{\;\;\;\;\;\;k_{2},k_3\ge1,\\ k_{1}+k_{2}+k_{3}=n-1}^{ }\frac{1}{k_{2}k_{3}}$$

Where $k_1$ is the left cycle and $k_2,k_3$ are the right cycles.

But I don't know how to continue, it would be appreciated if someone helps me.

Besides I like to know how much of my work is right.

Answer 1

Notice that when you pick the elements in the cycle, you are intuitively giving them an order. So you have to divide by $2$ your expression.

Now, to keep it going, notice that a partition of the form $k_1+k_2+k_3=n-1$ where $k_1,k_2>0$ can be expressed as $n_1=k_2,n_2=k_2+k_1,n_3=k_3,$ notice that $1\leq n_1<n_2\leq n-1$ and so you can express your last expression as $$\sum _{\substack{k_1+k_2+k_3=n-1\\k_1,k_2>0}}\frac{1}{k_1k_2}=\sum _{1\leq n_1<n_2\leq n-1}\frac{1}{n_1\cdot (n_2-n_1)}.$$
Use partial fractions to show that this is actually $$2\sum _{1\leq n_1<n_2\leq n-1}\frac{1}{n_1\cdot n_2}.$$ Edit: $$\sum _{1\leq n_1<n_2\leq n-1}\frac{1}{n_1\cdot (n_2-n_1)}=\sum _{1\leq n_1<n_2\leq n-1}\frac{1}{n2}\cdot \left (\frac{1}{n_1}+\frac{1}{n_2-n_1}\right )=\sum _{1\leq n_1<n_2\leq n-1}\frac{1}{n_1\cdot n_2}+\sum _{1\leq n_1<n_2\leq n-1}\frac{1}{n_2\cdot (n_2-n_1)},$$ but doing another change of variable, mainly $m_2=n_2,m_1=n_2-n_1$ one sees that $1\leq m_1<m_2\leq n-1$ and so $$\sum _{1\leq n_1<n_2\leq n-1}\frac{1}{n_1\cdot (n_2-n_1)}=2\sum _{1\leq n_1<n_2\leq n-1}\frac{1}{n_1\cdot n_2}$$

Meanwhile, in the alternative universe of the RHS, you have that $$\left (H_{n-1}\right )^2-H^{(2)}_{n-1}=\sum _{1\leq n_1,n_2\leq n-1}\frac{1}{n_1\cdot n_2}-\sum _{1\leq n_1=n_2\leq n-1}\frac{1}{n_1\cdot n_2}=2\sum _{1\leq n_1<n_2\leq n-1}\frac{1}{n_1\cdot n_2}.$$