facc005@SAUPM00.BITNET ("M. Atiquzzaman") (12/01/90)
The number of ways of partitioning n objects into k groups such that * no group is empty * is given by the Stirling's number of the second type i.e. S(n,k) = S(n-1,k-1) + k*S(n-1,k) Is there any formula for calculating the number of possible partitions if * one or more groups may be empty * ? M. Atiquzzaman facc005@saupm00.bitnet facc005%saupm00.bitnet@cunyvm.cuny.edu
nmg@c3.c3.lanl.gov (Niall Graham) (12/01/90)
> >The number of ways of partitioning n objects into k groups such >that * no group is empty * is given by the Stirling's number of the >second type i.e. > >S(n,k) = S(n-1,k-1) + k*S(n-1,k) > >Is there any formula for calculating the number of possible partitions >if * one or more groups may be empty * ? How about SUM {from i=1 to k} S(n,i) I don't think a simple recurrence exists unless a third parameter is introduced to keep track of the number of empty parts. Niall Graham Los Alamos
pathria@ucbarpa.Berkeley.EDU (Anu Pathria) (12/02/90)
>The number of ways of partitioning n objects into k groups such >that * no group is empty * is given by the Stirling's number of the >second type i.e. > >S(n,k) = S(n-1,k-1) + k*S(n-1,k) > >Is there any formula for calculating the number of possible partitions >if * one or more groups may be empty * ? I must be missing something but shouldn't it be k^n-S(n,k) ?
wcn@cs.brown.edu (Wen-Chun Ni) (12/03/90)
I originally sent the following solution to the person asking
the question. But I think it is necessary to let the public
know what it is.
------------------ Solution
If I do not misinterpret your problem, the problem is in fact
easier than the original one. No recurrence is required, and
the answer is k^n/k!.
From generating function, n!S(n,k) is the coefficient of x^n in
(exp(x)-1)^k/k!,
but the function of your answer is
(exp(x))^k/k!.
You may refer to Liu's introductory book for such interpretations.
You can also get just k^n if you consider the groups are labelled,
but the generating function is another story.
Somebody (I deleted it from my file) answered this question by posing
an incorret answer: sum(for i=1 to k) S(n,i).
Wen-Chun Ni: Department of Computer Science
Brown University, (H) (401) 2723615
Providence, RI 02912 (O) (401) 8637668
________________________________________________________________
* * I'm quite sure if God were asked
* * * to draw up a programme of the world
** *** *** he had created, he could never do it.
* * * *
* * ******** -- Mahler to Alma, 15th Dec 1901
* * *
* * * in description of 2nd Symphony
* * * * "Resurrection."
* * ****
________________________________________________________________nmg@c3.c3.lanl.gov (Niall Graham) (12/03/90)
Wen-Chun Ni writes: >If I do not misinterpret your problem, the problem is in fact >easier than the original one. No recurrence is required, and >the answer is k^n/k!. Oops! k^n/k! is not an integer for k >= 3. . . >Somebody (I deleted it from my file) answered this question by posing >an incorret answer: sum(for i=1 to k) S(n,i). I did! And I still believe it is correct. Since you like generating functions I'll add that the special case k=n yields the Bell numbers whose exponential generating function is e^(e^x - 1) [Ref. An old "Monthly" article by Rota]. > Wen-Chun Ni: Department of Computer Science > Brown University, (H) (401) 2723615 > Providence, RI 02912 (O) (401) 8637668 > ________________________________________________________________ Niall Graham "If this is Heaven, I'm bailin' out" Los Alamos, New Mexico The Birthday Party