- #1
e(ho0n3
- 1,357
- 0
Hello again,
I need to prove the following identity for Stirling numbers of the first kind:
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,
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.