Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Stirling Number of the First Kind

  1. Jun 7, 2004 #1
    Hello again,

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

    For the uninitiated, [itex]s_{n,k}[/itex] is a Stirling number of the first kind and represents (as I was explained) the number of ways of sitting [itex]n[/itex] people in [itex]k[/itex] 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 [itex]s_{3,1}=2[/itex].

    OK. I know that [itex]s_{n,1}=(n-1)![/itex]. I need to find [itex]s_{n,2}[/itex] 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, [itex]s_{n,2}[/itex] 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,
    [tex]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}[/tex]​
    Now assuming this is right, how do I simplify this to what I gave above? I just can't seem to do it.
     
  2. jcsd
  3. Jun 10, 2004 #2
    Continuing on here,
    [tex]\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}[/tex]​
    I just don't know.
     
  4. Nov 28, 2008 #3
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?