From: jhnieto@my-dejanews.com
Newsgroups: sci.math
Subject: Re: Combinatorics Question
Date: Mon, 21 Dec 1998 12:51:29 GMT

In article <75jd8u$6tk$1@eskinews.eskimo.com>,
  earther@eskimo.com (Steve Earth) wrote:
> I have a feeling this may actually be an easy calculation, but I just don't
> see it at the moment.  Any illumination someone can provide would be greatly
> appreciated.  Here's the question:
>
> How many ways are there to put N distinct objects into K indistinguishable
> boxes (moreover, each of the boxes is non-empty and order doesn't matter
> within the boxes)?

The answer is ¨the Stirling number of second class S(n,k)".
Sorry, but there is no closed formula for S(n,k). However you
can compute these numbers using the recurrence

   S(n,k) = S(n-1,k-1) + k*S(n-1,k)

with boundary conditions S(n,n)=1 for n>=0, S(n,0)=0 for n>0.

Moreover for all n>0 we have:

S(n,1) = 1, S(n,2) = 2^(n-1) - 1, S(n,n-1) = C(n,2)

If you want to know more, see "Concrete Mathematics"
by Graham, Knuth & Patashnik.

Greetings,

Jose H. Nieto

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own