Welcome to our community

Be a part of something great, join today!

Stirling numbers of first kind

ZaidAlyafey

Well-known member
MHB Math Helper
Jan 17, 2013
1,667
HI folks , working on Stirling nums , how to prove ?

\(\displaystyle s(n,3)=\frac{1}{2}(-1)^{n-1}(n-1)!\left(H_{n-1}^2-H_{n-1}^{(2)}\right)
\)

where we define \(\displaystyle H_k^{(n)}= \sum_{m=1}^k \frac{1}{m^n}\)

I don't how to start (Bandit)
 
Last edited:

PaulRS

Member
Jan 26, 2012
37
First, let us forget about the sign and work with unsigned Stirling numbers (so on the left you'd have $\left[{n\atop 3}\right]$, and on the right the same except that the factor $(-1)^{n-1}$ vanishes) . The result then will follow immediately.

Now, we have $\left[{n\atop 3}\right] = \left[{n-1\atop 2}\right] + (n-1)\times \left[{n-1\atop 3}\right]$

And here note that $\left[{n\atop 2}\right] = (n-1)! \times H_{n-1}$, a simpler identity. $(*)$

Having the identities above, try proving your identity (in an unsigned version) by induction. Don't forget that you have $H_n^2 = \left(H_{n-1}+1/n\right)^2$ and $H_n^{(2)} = H_{n-1}^{(2)} + 1/n^2$.

$(*)$ This one has a nicer combinatorial intepretation. First remember that $\left[{n\atop k}\right]$ counts the number of permutations having exactly $k$ cycles in its disjoint cycle decomposition.
Now $(n-1)\times H_{n-1} = \sum_{k=1}^{n-1} \frac{(n-1)!}{k}$. Here interpret $(n-1)!$ as taking the permutations that fix $n$. Then, for each $k$, let $\pi_1,\ldots,\pi_{n-1},\pi_n=n$ translate into having the cycles $\pi_1\to \ldots \pi_k\to \pi_1$ and $\pi_{k+1}\to \ldots \to \pi_n\to \pi_{k+1}$. Here note that we are overcounting $k$ times (since $\pi_1,\ldots,\pi_k$ ; $\pi_2,\ldots,\pi_k,\pi_1$ ; ... ; $\pi_k,\pi_1,\ldots,\pi_{k-1}$ result int he same cycle structure, we don't have the same problem with the other cycle since $n$ is fixed), hence the division by $k$.