# Stirling Number of the First Kind

1. Jun 7, 2004

### e(ho0n3

Hello again,

I need to prove the following identity for Stirling numbers of the first kind:
$$s_{n,2} = (n-1)!\Big(1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n-1}\Big)$$​

For the uninitiated, $s_{n,k}$ is a Stirling number of the first kind and represents (as I was explained) the number of ways of sitting $n$ people in $k$ table so that every table has at least one person. The ordering of the tables doesn't matter but the ordering of the people on a table does. Example: Suppose three people (A, B, and C) are sitting at a table such that C is to the right of B and B is to the right of A. So ABC = BCA = CAB are all the same. Another way of sitting A, B, and C is by letting C be to the right of A and B to the right of C. So ACB = BAC = CBA. So, the number of ways of sitting three people on one table is $s_{3,1}=2$.

OK. I know that $s_{n,1}=(n-1)!$. I need to find $s_{n,2}$ which is the number of ways of sitting n people in two tables. I'm going to assume n is even to simplify my analysis here. So, $s_{n,2}$ can be reduced to:
The number of ways of sitting one person at one table and n - 1 persons at the other table, plus the number of ways of sitting two persons at one table and n - 2 persons at the other table, plus..., plus the number of ways of sitting n/2 persons at one table and n/2 persons on the other table. In other words,
$$s_{n,2} = s_{1,1}s_{n-1,1} + s_{2,1}s_{n-2,1} + ... + s_{n/2,1}s_{n/2,1}$$​
Now assuming this is right, how do I simplify this to what I gave above? I just can't seem to do it.

2. Jun 10, 2004

### e(ho0n3

Continuing on here,
\begin{align*} s_{n,2} &= s_{1,1}s_{n-1,1} + s_{2,1}s_{n-2,1} + ... + s_{n/2,1}s_{n/2,1} \\&= 0!(n-2)! + 1!(n-3)! + ... + (n/2 - 1)!(n/2 - 1)! \\&= (n-2)!\sum_{k=0}^{n/2-1}{\frac{1}{C(n-2,k)}} \end{align}​
I just don't know.

3. Nov 28, 2008

### OldProf

This appears to be a standard identity. Check out the Wikipedia entry on Stirling Numbers of the First Kind, and the relation to harmonic numbers.