[math-fun] A peculiar numerical coincidence
I thought that this was rather neat: http://sbseminar.wordpress.com/2010/10/06/a-peculiar-numerical-coincidence/#...
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.
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
No, I got the Fibonacci bit wrong. The last term to subtract for N=4 isn't 13. Now I kind of thinking the series involves binomial coefficients multiplied by previous terms in the sequence in a funny way, I get 1, 2, 5, 15, 52, ... which would make sense if it's really the Bell numbers, but now I've lost touch with my tesseract visualization so I can't confirm it. Arrgh. On Wed, Nov 10, 2010 at 23:07, Robert Munafo <mrob27@gmail.com> wrote:
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
="Robert Munafo" <mrob27@gmail.com>
The first amount to be subtracted is 2^(2^(N-1)-1).
Strictly syntactically, from the exponentiation, and given that the formula for A003645 in the OEIS is sum((-1)^k*binomial(n, k)2^2^(n-k), k=0..n)/2 it seems like you might be close to the right enumeration neighborhood.
I think the cube labeling is the most natural way to visualize this one, but I'd love to hear of something better.
Me too, but this is more than I was able to come up with! You might want to verify that any proposed "model schema" also down-scales to the 5 cases for n=2.
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 (-:
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? Another related way to view 109 is that it's the number of ways to distinctly partition 7 using IOR for addition. Alas none of that seems to suggest a natural visualization.
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
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
So if a(n) = 2*A003465(n) = A000371(n), we have, as you said, a(n) = sum_{j=0}^n (-1)^j (n choose j) 2^2^(n-j), which gives the total number of covers of a set of size n. Also, the coefficients of x^k in the polynomial p_n(x) = sum_{j=0}^n (-1)^j (n choose j) (x+1)^2^(n-j) gives the number of covers of a set of size n where the covers have k elements. Also, there is a nice recursion f_n(k) = k, if n = 0; f_{n-1}(k^2) - f_{n-1}(k), if k > 0 that gives a(n) = f_n(2). and p_n(x) = f_n(x+1) ----- Original Message ----- From: "David P. Moulton" <moulton@idaccr.org> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Thursday, November 11, 2010 11:44 AM Subject: Re: [math-fun] Coincidentally, 109 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 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun ----- No virus found in this message. Checked by AVG - www.avg.com Version: 10.0.1153 / Virus Database: 424/3250 - Release Date: 11/11/10 ----- No virus found in this message. Checked by AVG - www.avg.com Version: 10.0.1153 / Virus Database: 424/3250 - Release Date: 11/11/10
participants (5)
-
David P. Moulton -
David Wilson -
Marc LeBrun -
Robert Munafo -
Victor Miller