Re: [math-fun] Counting problem
Ha -- and in my spare moments today I counted 87 (by hand). So, can we split the difference and agree on 86 ? --Dan Allan wrote: << As luck would have it, this afternoon I had a boring staff meeting in which I enumerated all of them ... I think. And the answer is 85 ... I think. On Tue, Dec 6, 2011 at 12:36 PM, Richard Guy <rkg@cpsc.ucalgary.ca> wrote:
This seems to be a particular case of the necklace problem which was solved by Hazel Perfect in Math Gaz, when? (more than half a century ago -- not in MR) R.
On Tue, 6 Dec 2011, Dan Asimov wrote:
What are all the ways that 30-, 60-, and 90-degree angles can be arranged
about the origin in the plane?
________________________________________________________________________________________ It goes without saying that .
I think you take each of the 19 partitions and let a=#1s, b=#2s, c=#3s; the number of ways to order the elements of that partition is (a+b+c-1)! / a! b! c! 2 (Where the -1 comes from cyclic reorderings and the 2 comes from reflections.) Am I missing something? On Tue, Dec 6, 2011 at 4:17 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Ha -- and in my spare moments today I counted 87 (by hand).
So, can we split the difference and agree on 86 ?
--Dan
Allan wrote:
<< As luck would have it, this afternoon I had a boring staff meeting in which I enumerated all of them ... I think. And the answer is 85 ... I think.
On Tue, Dec 6, 2011 at 12:36 PM, Richard Guy <rkg@cpsc.ucalgary.ca> wrote:
This seems to be a particular case of the necklace problem which was solved by Hazel Perfect in Math Gaz, when? (more than half a century ago -- not in MR) R.
On Tue, 6 Dec 2011, Dan Asimov wrote:
What are all the ways that 30-, 60-, and 90-degree angles can be arranged
about the origin in the plane?
________________________________________________________________________________________ It goes without saying that .
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
On Wednesday 07 December 2011 01:05:04 Mike Stay wrote:
I think you take each of the 19 partitions and let a=#1s, b=#2s, c=#3s; the number of ways to order the elements of that partition is (a+b+c-1)! / a! b! c! 2 (Where the -1 comes from cyclic reorderings and the 2 comes from reflections.)
Am I missing something?
Yes, I think so. Consider, for instance, the case a=12, b=0, c=0, where your formula gives 11/24. Or the case a=3, b=0, c=3, where your formula gives 5/3. -- g
I have a quick method avoiding partitions: -------- Part 1 (Enumeration of strings using recurrence relations) Firstly, let's represent a 30°, 60° and 90° with A, AB and ABB, respectively. We want to count bracelets with 12 beads, and no three adjacent 'B' beads. http://en.wikipedia.org/wiki/Bracelet_(combinatorics) Firstly, let's enumerate the strings beginning with 'A' and having n beads. This is easily given by the Tribonacci sequence, A000073. For the sake of brevity, denote the terms of this sequence with f(n). The first twelve terms are: 1,2,4,7,13,24,44,81,149,274,504,927 However, we are not just interested in these sequences, as these do not account for strings beginning with 'B'. It is fairly simple to account for this, though, by accepting strings of the form: $ B$A B$AB BB$A (It is trivial to verify that these strings are all of the valid ones, and no more, with no multiplicity.) Here, $ can represent any string of suitable length of the type enumerated by f(n). This gives a new function, g(n), for the number of bracelets, where rotations and reflections are considered to be distinct: g(n) = f(n) + f(n-2) + 2f(n-3). As it is a linear combination of linear recurrences, it is itself a linear recurrence. The first few terms are g(0) = 1, g(1) = 3, g(2) = 7, allowing us to determine the remaining terms using the recurrence itself: g(n+3) = g(n+2) + g(n+1) + g(n). This gives us A001644 in the OEIS, the first 12 terms of which are: 1,3,7,11,21,39,71,131,241,443,815,1499 The last value, 1499, is the number of solutions to the problem where rotations and reflections are considered to be distinct. Obviously, the answer to your problem is significantly smaller; the next section calculates it precisely: -------- Part 2 (Use of Burnside's Lemma to incorporate symmetries) We now need to consider bracelets invariant under each of the 24 group elements. The direct symmetries (reflections) are: Identity symmetry fixing g(12) = 1499 bracelets; 180° rotation fixing g(6) = 39 bracelets; 120°, 240° rotations each fixing g(4) = 11 bracelets; 90°, 270° rotations each fixing g(3) = 7 bracelets; 60°, 300° rotations each fixing g(2) = 3 bracelets; 30°, 150°, 210°, 330° rotations each fixing g(1) = 1 bracelet. Now, if we were just solving the analogous *necklace* problem (where reflections are considered to be distinct), then we would have the answer of: (1499 + 39 + 2*11 + 2*7 + 2*3 + 4*1)/12 = 132 necklaces. However, we still need more work to solve the full problem. There are only two distinct reflections, those where the axis of reflection passes through or between beads. Let's approach these cases separately: For the 'through beads' case, we need only consider the first seven beads on the string, as the other five can be obtained by symmetry, like so: 1 2 3 4 5 6 7 6 5 4 3 2 Obviously, we cannot have beads 6 and 7 as both 'B', nor both 1 and 2. This is the only constraint, leading to the following acceptable strings: $A $AB B$A B$AB This gives us f(6) + f(5) + f(5) + f(4) = 57 bracelets invariant under that particular reflection. Now, for the 'between beads' case: 1 2 3 4 5 6 6 5 4 3 2 1 We are constrained by exactly the same rule as before: beads 5 and 6 cannot both be 'B', nor can beads 1 and 2. So, we have g(5) + g(4) + g(4) + g(3) = 31 bracelets invariant under this reflection. There are six reflections of each type, so we now have the following group elements: Identity symmetry fixing g(12) = 1499 bracelets; 180° rotation fixing g(6) = 39 bracelets; 120°, 240° rotations each fixing g(4) = 11 bracelets; 90°, 270° rotations each fixing g(3) = 7 bracelets; 60°, 300° rotations each fixing g(2) = 3 bracelets; 30°, 150°, 210°, 330° rotations each fixing g(1) = 1 bracelet; Six reflections each fixing 57 bracelets; Six reflections each fixing 31 bracelets. The formula is now: (1499 + 39 + 2*11 + 2*7 + 2*3 + 4*1 + 6*57 + 6*31)/24 = 88 bracelets. This seems to agree with your general concensus. -------- Sincerely, Adam P. Goucher
="Adam P. Goucher" <apgoucher@gmx.com> ... = 57 bracelets invariant under that particular reflection. ... = 31 bracelets invariant under this reflection. ... The formula is now: (1499 + 39 + 2*11 + 2*7 + 2*3 + 4*1 + 6*57 + 6*31)/24 = 88 bracelets.
Numerology: is it sheer coincidence that "this" plus "that" also equals 88?
Numerology: is it sheer coincidence that "this" plus "that" also equals 88?
Indeed. For the 2-bead version of this problem (using 180° and 360° components), 'this' is 3, 'that' is 1, and the sum is 4 (not 2). Sincerely, Adam P. Goucher
So ... I'm assuming that the corresponding sequences permitting only 1 and 2 are already in OEIS? For necklaces as well as bracelets? For reversible and irreversible chains of beads ("opened" bracelets and necklaces)? On Wed, Dec 7, 2011 at 4:55 PM, Adam P. Goucher <apgoucher@gmx.com> wrote:
Numerology: is it sheer coincidence that "this" plus "that" also equals 88?
Indeed. For the 2-bead version of this problem (using 180° and 360° components), 'this' is 3, 'that' is 1, and the sum is 4 (not 2).
Sincerely,
Adam P. Goucher
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
participants (6)
-
Adam P. Goucher -
Allan Wechsler -
Dan Asimov -
Gareth McCaughan -
Marc LeBrun -
Mike Stay