Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm doing some homework and one of the questions is is as follows. For m $\ge$ 3 show that S(m, m - 2) = $\frac{1}{24}$ m(m-1)(m-2)(3m-1).

My interpretation of the question is as follows. This problem can be modelled as the number of ways to distribute m objects amongst m - 2 containers with none left empty. This can be split into two cases:

  1. Three objects in one container, with the other m - 3 containers each containing one.
  2. Two containers each contain two objects, with the other m - 4 containing one.

Case one can happen in $\dbinom{m}{3}$ ways (choose three objects to put into one container). For case two I got $\dbinom{m - 2}{2}\dbinom{m}{2}$ ways to distribute them.

I then go through the algebra but don't get the expected result. This leads me to believe the counting I did above is wrong.

What is the correct way to model the two cases? Is what I did wrong or did I just make a mistake with my algebra? Thanks

share|improve this question
    
Are you sure about this identity? What definition of Stirling numbers are you using? –  J. M. May 3 '12 at 7:15
    
The book defined Stirling numbers of the second kind as: S(m, n) = 1/n! * sum(k=0 to n)[((-1)^k) * $\dbinom{n}{n-k}$(n - k)^m] Sorry about the formatting of it, I'm not really familiar with LaTeX –  jason May 3 '12 at 7:26

1 Answer 1

up vote 1 down vote accepted

The conventional definition would give $S_2(m, m - 2) = \frac{1}{24} m(m-1)(m-2)(3m-5)$ so with $-5$ rather than $-1$, so there may be a problem with the question.

In your answer for "case two", the two containers with two items can come in any order so you need to divide by two, and overall should be aiming to simplify $\dbinom{m }{3} + \dbinom{m - 2}{2}\dbinom{m}{2} /2.$

You should be able to show these are equal, at least for $m\ge 4$.

To check, with $m=4$, there are four ways with three objects in one container and one in another, and three ways with two objects in one container and two in the other, making seven ways in total.

share|improve this answer
    
Thanks for that, dividing by 2 gave me your expected result. I checked this with a few test numbers and it seems like the book made a mistake. :) –  jason May 3 '12 at 8:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.