home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15003 < prev    next >
Encoding:
Internet Message Format  |  1992-11-15  |  1022 b 
  1. Path: sparky!uunet!ogicse!emory!wupost!crcnis1.unl.edu!moe.ksu.ksu.edu!kuhub.cc.ukans.edu!kinnersley
  2. From: kinnersley@kuhub.cc.ukans.edu (Bill Kinnersley)
  3. Newsgroups: sci.math
  4. Subject: Counting Families of Subsets
  5. Message-ID: <1992Nov15.152951.44802@kuhub.cc.ukans.edu>
  6. Date: 15 Nov 92 21:29:50 GMT
  7. Article-I.D.: kuhub.1992Nov15.152951.44802
  8. Organization: University of Kansas Academic Computing Services
  9. Lines: 24
  10.  
  11. Take a base set S with N elements.  There are 2^N subsets of S.
  12. I want to consider families of these subsets.  All together there
  13. are 2^{2^N} such families, but I want to impose a condition.
  14.  
  15. Let F be a family such that all elements of F are distinct subsets,
  16. and no element of F is a subset of another.
  17.  
  18. How many families like this are there, for given N?
  19.  
  20. If you call the number K(N), then the first few values are:
  21.  
  22. N        K
  23.  
  24. 0        1
  25. 1        2
  26. 2        5
  27. 3       19
  28. 4      167
  29.  
  30. Can you tell me even the order of magnitude for K(N)?  It appears to be
  31. much less than 2^{2^N}.
  32.  
  33. -- 
  34. --Bill Kinnersley
  35.