From: Fred Galvin Newsgroups: comp.theory,sci.math,sci.logic Subject: Re: Two enumerating problems Date: Wed, 24 Jun 1998 23:19:59 -0500 On 23 Jun 1998, Yves Moinard wrote: > In order to obtain, by intersections and unions, > all the subsets of a set with n elements, we need at least k(n) subsets. > k(n) is the least k such that the binomial coefficient C(k,INT(k/2)) > is greater than or equal to n (cf Note below). > > Is it known how many solutions exist with this k(n), for each n? There are a couple of easy cases. If n = C(2r,r) then k(n) = 2r and there is just one solution. If n = C(2r+1,r) then k(n) = 2r+1 and there are just two solutions. You will understand why after you learn about Sperner's theorem (see below). How many solutions in the other cases? Lots, I guess; unfortunately, I don't know a lot about enumeration problems. > I do not understand it fully: > the only thing I understand is how to find such a solution, > and I see vaguely that this should probably give indeed the smallest > possible number. The fact that it does give the smallest possible number is Sperner's theorem, not to be confused with the *other* Sperner's theorem (or lemma) which is about triangulations. Sperner's theorem is usually stated in the following equivalent way: the maximum size of a family of incomparable subsets of a k-element set is C(k,INT(k/2)). (Two sets are incomparable if neither is a subset of the other; a family of incomparable sets is sometimes called an antichain, not to be confused with the *other* kind of antichain.) Among the various proofs, the LYM proof is particularly short and easy. Sperner's theorem is discussed in many textbooks on combinatorics; you should have no trouble finding it.