On Thu, Nov 11, 2010 at 04:02, Marc LeBrun <mlb@well.com> wrote:
You might want to verify that any proposed "model schema" also down-scales to the 5 cases for n=2.
Oh yes, I thought it was pretty clear, but here goes: For N=2: Given a square, one of whose corners is called V0: How many ways are there to label the other 3 corners either white or black such that there is at least one black corner on each of the two edges that do not touch V0? There are 5 solutions: V0 w V0 B V0 w V0 B V0 B w B w B B B B B B w The three labelings that don't work are: V0 w V0 B V0 w w w w w B w Starting with the 8 total labelings, you first subtract 1/4 of the labelings because the right edge cannot be all white: 8 * 3/4 = 6. Then you need to subtract one more to eliminate the one remaining labeling that has the bottom edge all-white. So that's 8 - 2 - 1 = 2^(N^2-1) - 2^(2^(N-1)-1) - A000110[N-1] I hear ya. But "covering"'s not too hard to visualize. Suppose you have a
pallet of N adjacent wine barrels that you want to keep rain water out of. And what you have at hand are 2^N-1 distinct cheap thin plastic N-barrel covers, each covering with a different combination of closed barrelheads and open tops . How many ways, using those covers, can you ensure that no barrel remains uncovered?
That's a great description, and I see that "covering" just means the same thing as the original statement of the problem: how many unions of subsets of a given set, not counting the empty set as a subset, will yield the original set? - Robert -- Robert Munafo -- mrob.com Follow me at: mrob27.wordpress.com - twitter.com/mrob_27 - youtube.com/user/mrob143 - rilybot.blogspot.com