On Wed, 10 Nov 2010, Marc LeBrun wrote
Now for n=3, we have S3 = ABC, and T3 = A, B, C, AB, BC, AC, ABC.
Next Question: enumerate the subsets of T3 whose union is S3.
You should get 109.
I think the easiest way to understand this is by inclusion--exclusion. I'm also going to change the problem a bit by letting T also contain the empty set; this just doubles all your numbers, since add or removing the empty set from a collection does not change whether it works. So now S has n elements, and T, the power set of S, has 2^n elements. Let's let U be the power set of T; we want to know how many elements of U have union S. For any element i of S, let U_i be the subset of U_i whose unions do not contain i, so we want to compute the size of the complement of the union of the U_i s. Let's write U_I for the union of U_i for i in I. Then U_I consists of all subsets of T whose union is disjoint from I, so it consists of all subsets of the power set of S - I. The power set of S - I has 2^(n - #I) elements, so U_I has size 2^2^(n - #I). Then the basic inclusion--exclusion formula says that our answer is #(U - union_{i in S} U_i) = sum_{I subseteq S} (-1)^#I #U_I = sum_{j=0}^n (-1)^j sum{#I = j} #U_I = sum_{j=0}^n (-1)^j (n choose j) 2^2^(n-j). If we take n = 2, we get 2^4 - 2.2^2 + 2^1 = 10, which is twice the 5 you get by excluding the empty set. If we take n = 3, we get 2^8 - 3.2^4 + 3.2^2 - 2^1 = 256 - 48 + 12 - 2 = 218, twice the 109 you get by excluding the empty set. David P. Moulton