wcn@cs.brown.edu (Wen-Chun Ni) (12/03/90)
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.