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.