1
$\begingroup$

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

  • 0
    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 LaTeX2012-05-03

1 Answers 1

2

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.

  • 0
    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. :)2012-05-03