From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math.num-analysis
Subject: Re: Problem with sets
Date: 6 May 1997 06:34:47 GMT

In article <33616296.64DC@iol.it>, Roberta Ganzaroli  <ganzaroli@iol.it> wrote:
>Please help me! I have to find all the groups of six not empty sets
>whose union gives a set made of the first twenty natural numbers
>and the intersection of any two of them is the empty set.

(That is, you want a partition of {1..20} into exactly 6 subsets.)

Umm, do you have a little while to wait for the prinout? 

Part of your task will be to list all the partitions into 5 singletons
and a set of 15. All you have to do is say which 5 elements are in the
singletons; there are (20 choose 5) = 15504 ways to do this.

But of the 627 partitions of 20, there are 90 partitions into precisely
6 subsets, and this partition [1,1,1,1,1,15] is the one with the
_smallest_ number of ways to place the 20 elements into the partition.
(The worst is [2,2,3,4,4,5].) Altogether I count 4 306 078 895 384 ways
to partition the elements. 

dave