Given a cube, one of whose vertices is called V0: How many ways are there to label the other 7 vertices either white or black such that there is at least one black vertex on each of the three faces that do not contain V0? There are 2^(2^3-1) = 2^7 = 128 labelings, but the constraint rules out the labelings that would make face F1 all white: Face F1 has 4 vertices and they can't all be white, so you rule out 1 out of 16, therefore our total is reduced to 128*15/16 = 120. You then need to rule any the remaining labelings that leave face F2 all white, which subtracts 9, and then there are 2 labelings left that would satisfy F1 and F2 but yet leave F3 all white. For arbitrary N, it is an N-dimensional hypercube, and "faces" are the N-1 dimensional hypercubes that forms the bounding polytopes. I'm not too clear on the terminology. The first amount to be subtracted is 2^(2^(N-1)-1). The last number that needs to be subtracted is: 1, 2, 5, 13, 34, ... alternating Fibonacci numbers, related to the way staggered diagonals of Pascal's triangle add up to Fibonacci numbers: the number of ways that faces F1...F(n-1) can force the final vertex black are enumerated by binomial coefficients. I haven't tried to think through how to generalize the terms in between. I think the cube labeling is the most natural way to visualize this one, but I'd love to hear of something better. I looked at the OEIS entry but don't know what a "covering" is and didn't bother looking at the references or anything else (-: - Robert On Wed, Nov 10, 2010 at 20:53, Marc LeBrun <mlb@well.com> wrote:
Speaking of coincidences: to distract from some dentistry (hey, it worked for Pascal!) I tried to find--eyes closed--a natural way to enumerate the simple set-construction below that, surprisingly (to me), has 109 cases. How might this weird number break down? 108+1? Or 64+36+9? Or what?
After deciding this puzzle might be too trivial for math-fun, I checked into a hotel and they coincidentally assigned me room 109! OK, I won't fight it.
As a warm-up, for n=2 we start with a set of two elements, S2 = AB. Call the set of non-empty subsets of S2, T2 = A, B, AB.
Question: how many subsets of T2 when unioned together equal S2?
You should get 5: A+B, AB, AB+A, AB+B and AB+A+B
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.
Can you organize these into some natural scheme?
See OEIS sequence A003465 for other n.
-- Robert Munafo -- mrob.com Follow me at: mrob27.wordpress.com - twitter.com/mrob_27 - youtube.com/user/mrob143 - rilybot.blogspot.com