e(ho0n3
Jun7-04, 06:01 PM
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.
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.