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