Path: utzoo!attcan!uunet!kddlab!trl!rdmei!ptimtc!olivea!apple!snorkelwacker.mit.edu!hsdndev!cmcl2!lanl!beta.lanl.gov.!nmg
From: nmg@c3.c3.lanl.gov (Niall Graham)
Newsgroups: comp.theory
Subject: Re: partitioning problem
Message-ID: <NMG.90Nov30145320@c3.c3.lanl.gov>
Date: 30 Nov 90 21:53:20 GMT
References: <9011301618.AA00954@irt.watson.ibm.com>
Sender: news@lanl.gov
Organization: Los Alamos National Laboratory, New Mexico
Lines: 18


>
>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


Brought to you by Super Global Mega Corp .com