MHB How to Prove Stirling Numbers of the First Kind for s(n,3)?

  • Thread starter Thread starter alyafey22
  • Start date Start date
  • Tags Tags
    Numbers Stirling
AI Thread Summary
To prove the Stirling numbers of the first kind for s(n,3), the initial approach suggests working with unsigned Stirling numbers, simplifying the expression by removing the sign factor. The key identity to use is s(n,3) = s(n-1,2) + (n-1) * s(n-1,3), with the relationship s(n,2) = (n-1)! * H(n-1) aiding the proof. Induction is recommended for demonstrating the identity in its unsigned form, utilizing the definitions of harmonic numbers H(n) and H(n)^(2). The discussion emphasizes the combinatorial interpretation of the Stirling numbers, particularly in relation to permutations and cycle structures.
alyafey22
Gold Member
MHB
Messages
1,556
Reaction score
2
HI folks , working on Stirling nums , how to prove ?

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

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

I don't how to start (Bandit)
 
Last edited:
Physics news on Phys.org
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$.
 
Back
Top