Stirling Number of the First Kind

[e(ho0n3]

Here is another question I posted on PF but got little attention:

 

I need to prove the following identity for Stirling numbers of the first kind:

 

[math]s_{n,2} = (n-1)!\Big(1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n-1}\Big)[/math]

 

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,

 

[math]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}[/math]

 

Now assuming this is right, how do I simplify this to what I gave above? I just can't seem to do it.

[Dave]

I had a quick go but I couldn't get anything out.

 

Then again, combinatorics really isn't my cup of tea

[e(ho0n3]

It has been a while, but now I've been given enough hints to solve this problem. Suppose each of the n persons is wearing a t-shirt with a number on it between 1 and n where no two persons have the same number.

 

If I ask the person with t-shirt number n (hereby referenced as dave) to sit in one table and the rest to sit at the other table, how many seating arrangements are there? Simple: s[n - 1,1] = (n - 2)! = (n - 1)!/(n - 1).

Say I want another person to sit with dave. I can pick from n - 1 persons to sit with dave. The rest of the n - 2 persons will sit at the other table and can do so in s[n - 2,1] = (n - 3)! ways. The total combinations is therefore (n - 1)(n - 3)! = (n - 1)!/(n - 2).

Say I want two persons sitting with dave. I can choose two persons in (n - 1)(n - 2) ways. The rest of the n - 3 people can sit at the other table in s[n - 3,1] = (n - 4)! ways. The total combinations is therefore (n - 1)(n - 2)(n - 4)! = (n - 1)!/(n - 3).

.

.

.

Say I want n - 2 persons to sit with dave. Choosing n - 2 person can be done in (n - 1)! ways. The other person can sit at the other table in only one way. The total combinations is therefore (n - 1)!.

 

Adding all the above combinations gives the desired equation. So deviously simple...

[psi20]

Say I want two persons sitting with dave. I can choose two persons in (n - 1)(n - 2) ways. The rest of the n - 3 people can sit at the other table in s[n - 3' date=1] = (n - 4)! ways. The total combinations is therefore (n - 1)(n - 2)(n - 4)! = (n - 1)!/(n - 3).

.

.

.

 

Say I want n - 2 persons to sit with dave. Choosing n - 2 person can be done in (n - 1)! ways. The other person can sit at the other table in only one way. The total combinations is therefore (n - 1)!.

 

Adding all the above combinations gives the desired equation. So deviously simple...

 

I think you forgot about dave's table. Since there's three people, at that table, you have 2 different ways to arrange people or s[3,1].

What's the s in that notation mean, by the way?

 

But anyways, if you want 2 people sitting with dave, you can choose (n-1)(n-2) ways. Like you said, the others sit at the table in (n-4)! ways. At dave's table, we have 2 ways of arranging the 3 people. So I think it's 2(n-1)(n-2)(n-4)! ways.

 

For choosing 3 people to sit with dave, it would be (n-1)(n-2)(n-3) ways to choose. The others sit can sit in s[n-4,1] = (n-5)! I think. Then at dave's table, we can do s[4,1] = 6.

So for 3 people with dave, it's 6(n-1)!/(n-4)

For 2 people, it's 2(n-1)!/(n-3)

For 1 person, it's 1(n-1)!/(n-2)

With just dave, it's 1(n-1)!/(n-1)

[psi20]

I think you forgot about dave's table. Since there's three people' date=' at that table, you have 2 different ways to arrange people or s[3,1'].

What's the s in that notation mean, by the way?

 

But anyways, if you want 2 people sitting with dave, you can choose (n-1)(n-2) ways. Like you said, the others sit at the table in (n-4)! ways. At dave's table, we have 2 ways of arranging the 3 people. So I think it's 2(n-1)(n-2)(n-4)! ways.

 

For choosing 3 people to sit with dave, it would be (n-1)(n-2)(n-3) ways to choose. The others sit can sit in s[n-4,1] = (n-5)! I think. Then at dave's table, we can do s[4,1] = 6.

So for 3 people with dave, it's 6(n-1)!/(n-4)

For 2 people, it's 2(n-1)!/(n-3)

For 1 person, it's 1(n-1)!/(n-2)

With just dave, it's 1(n-1)!/(n-1)

 

I was thinking over this problem for more than an hour and I found my error. You don't count in the factor of 2 when thinking about 2 people because you already counted that in when choosing (n-1)(n-2). You don't count in the factor of 6 when calculating for 3 people with dave because you chose (n-1)(n-2)(n-3) and thus already considered the seating positions in there.

 

I checked and by writing out the combination for 4 people seated at 2 tables. My calculations showed there were 17 ways, but the formula said there were 11 ways. And there were only 11 ways.

[e(ho0n3]

What's the s in that notation mean, by the way?

Check out this link: http://mathworld.wolfram.com/StirlingNumberoftheFirstKind.html

 

I'm glad to see someone else interested in this. There is another problem I'm working on right now with no progress: Prove that

 

[math]\sum_{k=0}^n s_{n,k} = n![/math]

 

I'm trying to use induction with this one, but I can't complete the proof.

[psi20]

Whoa, I had no idea math was so expansive! Where do you begin on that site?

[Dapthar]

Whoa, I had no idea math was so expansive! Where do you begin on that site?

If by begin, you mean start learning about the material in question, then I'm sorry to say that http://mathworld.wolfram.com/ is more of a technical reference rather than a tutorial site. You'd be better off finding a combinatorics textbook than trying to learn specific topics from that site.

[e(ho0n3]

I think I've figured it out. Here is the outline

 

Basis Step (n = 1). Trivial.

Inductive Step. Assume

[math]\sum_{k=0}^n s_{n,k} = n![/math]

is true. Again suppose each of the n persons is wearing a t-shirt with a number on it between 1 and n where no two persons have the same number. Every particular seating arrangement in s[n,k] can be written as some number string a[1], a[2], a[3], ..., a[n] where a is some number in {1, ..., n} and a = a[j] only if i = j. If a new person with shirt number x = n + 1 comes along, in how many ways can I sit him given a particular seating arrangment? The answer is n + 1 (I can put x in front of a[1] to get a new seating arrangement, or in front of a[2], or ..., or in front of a[n], or behind a[n]). Therefore s[n + 1,k] = (n + 1)s[n,k]. Hence

[math]\sum_{k=0}^{n+1} s_{n+1,k} = (n+1)\sum_{k=0}^n s_{n,k} = (n+1)![/math]

Hence the desired result.

 

I don't see any flaw in this proof, but who knows. I will be glad when someone gives me a "thumbs up" on this.

[e(ho0n3]

I found an error. The equation s[n + 1,k] = (n + 1)s[n,k] fails for n = 1. Actually, it fails for all n > 0. I knew it could be this easy. Back to the drawing board.

[psi20]

When you add across the absolute value of the values in the rows of the stirling table, you get the factorials of the number of the row.

[psi20]

I was having trouble with s(5,3) and I think I figured out where I went wrong.

 

There are 5 people A,B,C,D, and E and 3 tables. There are 4 different table styles.

 

1) A _ _ _ _

2) A _ _ _ _

3) A _ _ _ _

4) A _ _ _ _

 

The _'s just represent spots to be filled in. We can assume that A sits at a table.

For the first table setting, I thought it would be (4*3) number of ways to choose people, then divide by two because there would be repeats like B C and C B.

But I was wrong because you can actually state a second assumption. So you seat B down because you know B is going to sit at one of the tables.

1) A B _ _ _

So it's actually (3*2)/2 for the number of ways to arrange using that table setting.

A B C D E

A B D C E

A B E D C

 

For the second table setting, you can have 4 different choices in the 1 seat table. Then in the 3 seat table, you know everyone else (3 people) are going to sit there, so you have 2 ways to arrange people. So it's 4*2 or 8 for #2.

 

For number 3, you can have 4 different ways for sitting with A. Then you have 3 different choices sitting alone. Everyone else sits in the other table. So that's 12.

 

For number 4, you have 4 choices to sit to the left of A, and 3 choices to sit to the right of A. Everyone else's seat would then not matter. So that's 12.

 

3 + 8 + 12 + 12 = 35, which is s(5,3)

 

I think your problem with the sum might have to do with limits, but I'm not sure.

[e(ho0n3]

I figured out the problem. Back to this question: If a new person with shirt number x = n + 1 comes along, in how many ways can I sit him given a particular seating arrangment? Given a particular arrangement a[1], a[2], a[3], ..., a[n] in s[n,k], I can add x behind a[1] to get a new arrangement, or behind a[2], or ..., or behind a[n] (and this is the same as adding x in front of a[1] since the tables are circular). This gives ns[n,k] combinations. However, I can also sit x on his/her own table (which is not covered in the previous combinations) and have the rest sit in the k - 1 remaining tables, which can be done in s[n,k - 1] ways. So, the answer to the question is ns[n,k] + s[n,k - 1]. In other words, s[n + 1,k] = ns[n,k] + s[n,k - 1]. This means

 

[math]\sum_{k=0}^{n+1} s_{n+1,k} = \sum_{k=0}^{n+1} (ns_{n,k} + s_{n,k - 1})[/math]

 

Noting that

 

[math]\sum_{k=0}^{n+1} ns_{n,k} = \sum_{k=0}^{n} ns_{n,k} = n!n[/math]

 

since s[n,n + 1] = 0 and

 

[math]\sum_{k=0}^{n+1} s_{n,k - 1} = \sum_{k=0}^{n} s_{n,k} = n![/math]

 

since s[n,-1] makes no sense (so it is effectively 0). Hence the expression simplifies to n!n + n! = (n + 1)n! = (n + 1)!. I think is correct. What do you think?

 

[edit]I made an error with the last summation (I had k - 1 instead of k), but now it's correct.[/edit]

[psi20]

I don't get how you derived the second summation from the first.

[e(ho0n3]

I guess you are referring to the last two summations.

 

Note that

 

[math]\sum_{k=0}^{n+1} ns_{n,k} = \sum_{k=0}^{n} ns_{n,k} + ns_{n,n+1}[/math]

 

and since s[n,n + 1] = 0 (Every table must have at least one person, but with n + 1 tables, this is impossible so the answer is zero. In general s[n,k] = 0 if k > n) the summation reduces to n!n.

 

The summation

 

[math]\sum_{k=0}^{n+1} s_{n,k-1}[/math]

 

is (without using sigma notation) s[n,-1] + s[n,0] + s[n,1] + ... + s[n,n]. The expression s[n,-1] is pure nonsense (i.e. -1 tables), so I effectively made it zero. Hence the resulting summation.

 

I must admit the proof isn't rigorous. I should prove the recurrence relation first before proving the problem in question, but for my purposes this is enough.

[psi20]

So to prove \sum_{k=0}^{n} s_{n,k} = n!

 

you assume that \sum_{k=0}^{n} s_{n,k} = n!

 

Then figure that \sum_{k=0}^{n+1} s_{n+1,k} = (n + 1)! ,

and \sum_{k=0}^{n} ns_{n,k} = n!n .

 

Then, according to the scenario, you figured (n+1)! = n!n + n! => (n+1)! = n!(n+1) => (n+1)! = (n+1)!

 

I think it's right.

[e(ho0n3]

Judging by your response, it seems you are not familiar with induction and inductive proofs. I made an error in the argument of the inductive step, which I rectified. Completing the inductive step completes the proof. I now need someone to proofread my argument in the inductive step so I can have some closure on the solution to the problem.

[psi20]

Yeah