Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!brunix!wcn
From: wcn@cs.brown.edu (Wen-Chun Ni)
Newsgroups: comp.theory
Subject: Errata: (Re:partitioning problem)
Message-ID: <58292@brunix.UUCP>
Date: 3 Dec 90 04:22:30 GMT
Sender: news@brunix.UUCP
Reply-To: wcn@cs.brown.edu (Wen-Chun Ni)
Organization: Brown University Department of Computer Science
Lines: 20

I gave an erroneous answer k^n/k! for the partitioning problem
since the solution presumed the existence of the "empty groups"
even we just think them unlabelled. So the answer k^n applies
only when we make the group labelled. The answer sum(for i=1 to k) S(n,i)
(the Bell number )is  correct in the unlabelled case. I thank B. S. Yee at 
CMU for pointing out the error.

Generally, we just put the following ways of enumerations:

 members labelled and groups labelled : k^n
 members labelled and groups unlabelled: sum (for i=1 to k) S(n,i)
 members unlabelled and groups labelled: {n+k-1 choose k}
 members unlabelled and groups labelled: sum (for i=1 to k) p(n,i).

 The quantity p(n,i) is the number of ways partitioning an integer
 into i parts (eg. 4=4=1+3=2+2=1+1+2=1+1+1+1).

 If we want something like "monotonicity," "injective," or
 "surjective," please refer to "Enumerative Combinatorics" by
 Richard Stanley.


Brought to you by Super Global Mega Corp .com