choosing things, combinations and permutations

It does seem tricky. Consider flipping the ring of beads over, as well. I mean are WWWBBWB and WBWBBWW equivalent? I would think so

 

Log in or Sign up to hide all adverts.

Ah Fednis, I wish I could appreciate the beauty of what you just did... I will! I must! Where could I attain the mathematical knowledge to understand what you just did? I'm not sure where to start...

Please Register or Log in to view the hidden image!

 

Log in or Sign up to hide all adverts.

... college? In all seriousness, though, the skills I used to derive that expression were honed over the course of 6+ years tinkering with number puzzles because I like them. Take some basic-to-mid-level classes if you haven't already, then just practice.

 

Log in or Sign up to hide all adverts.

Let's look at subsets of those 20 strings of n = 5 beads, c = 2 colors. Note that "bead" is abstractly a node (or an edge) in some graph, but of a special kind: if we say the beads are colored edges then if k is the number of nodes, n = k - 1 when it's an open string, or n = k when it's a loop.

The strings containing a single B and four W beads are all equivalent, they're in the same 'orbit' if you make them into loops; in fact you just have to say they all start with a B (the head) the rest (the tail) is (n - 1) W's; mathematically they are all cyclic permutations, and obviously looking at your set of strings they aren't the only subsets like this.

So if we allow "necklaces" or loops of beads, plus the operations of flipping and rotating loops (we introduce geometrical symmetry, iow) there's an obvious map to those linear graphs (which are trees with maximal paths) with colored edges (respectively, nodes). We only need the extra operation of (cyclic) permutation of the beads. The path through the string is the thing . . .

 

Or just buy a puzzle book and get cracking.

Please Register or Log in to view the hidden image!

Earlier, you solved for a string with the head and tail being indistinguishable. We should also apply it to the ring scenario.

So, imagine the ring as a donut. Some donuts have chocolate on top, so this distinguishes between "top" and "bottom". We must find the no. of combos where there is no distinction between top and bottom.

 

That's the easy part. If you take a ring and "snip" it between any two beads, you'll get a string. If you then reverse the string and tie the ends back together, the result will be the original ring flipped upside down. Therefore, the rings that are symmetric under flipping are those rings that can be "snipped" to make a palindrome string, and we've already done some solid analysis of how to count palindromes.

For me, at least, the cyclic permutations are the real stumbling block. Case in point: for four colors and four beads, consider two possible non-directional strings.

RGBW, RGRG

We can turn these strings into rings by linking the last element to the first. In terms of what rings they make, the first string is equivalent to three others: WRGB, BWRG, and GBWR. The second, by contrast isn't equivalent to any other string (its only cyclic permutation, GRGR, is just the original string backwards). How can we simply count the number of unique strings that can be produced by cyclic permutations of a given original?

 

What you're doing is using the operations of flipping (reflecting) and rotating on sets of necklaces. With 5 beads there are 5 reflection lines and 5 rotations. To count all the unique necklaces use Burnside's lemma.

 

Note, the first string is also equivalent to: WBGR, BGRW, GRWB, RWBG

I think you're on the right track about dividing the strings into cycles, palindromes, or neither. In the case above the first string is neither, so it duplicates 2n times across the permutation space (after flipping).

 

Thanks for the tip! This is all new to me, but I'm going to take a stab at it anyway, following the example from Wikipedia as closely as I can.

First, we need to find the group of actions that map a ring of beads to a ring of beads. The identity is a gimme; following standard notation we'll call that \(e\). Rotations are also fairly obvious: we can rotate any ring clockwise by \(m\epsilon [1,n-1]\) beads, which we'll call \(R_m\). A counter-clockwise rotation by \(m\) is equivalent to a clockwise rotation by \(n-m\), so we don't need to consider the counter-clockwise cases separately.

Thirdly, we can flip the ring, which is a little trickier. To count as part of our group, an action must do nothing more than permute the beads; that is, it can never change the overall position of our ring or leave a bead where one wasn't before. Because of this, we need to find the axes across which the ring has reflective symmetry. If it's not clear what these lines of symmetry are, check out this handy page. In particular, notice that while a ring of \(n\) beads will always have \(n\) lines of symmetry, odd-numbered rings only have one kind of line (each passes through a single bead) while even-numbered rings have two kinds of lines (those that pass through two beads, and those that pass through none).

Putting all this together gives one for the identity, \(n-1\) rotations, and \(n\) flips, for a total of \(2n\) elements in the group. The next step is to figure out what bead rings are invariant under each element, so that we can apply Burnside's lemma. For starters, it's clear that \(e\) maps any choice of bead coloration to itself, so all \(c^n\) configurations are invariant under \(e\).

Under a given rotation \(R_m\), there are two ways in which a ring could be invariant. One is if all the beads are the same color, and there will always be \(c\) such rings. The other is if \(n\) is evenly divisible by \(m\), and the bead ring is formed by repeating a sequence of \(m\) colors over and over. To illustrate, consider a four-bead ring in two colors. The only colorings invariant under \(R_1\) are WWWW and BBBB. These same colorings are also the only ones invariant under \(R_3\), since 4 is not evenly divisible by 3. But 4 is divisible by 2, so we get two more invariant colorings under \(R_2\): WBWB and BWBW. In general, there are \(c^m\) ways to take a sequence of \(m\) colors and repeat it \(n/m\) times. To allow compact notation later, I'll make up a function \(G(c,n,m)\) which is defined as follows:

\(G(c,n,m)=c^m\) if \(n/m\) is an integer, and \(G(c,n,m)=c\) otherwise.

This new, somewhat cumbersome function allows us to say that there are \(G(c,n,m)\) invariant configurations under a given \(R_m\). (If anyone knows of a way to express this entirely in terms of standard functions, I'd love to hear it.)

Lastly, the flips behave differently for even and odd cases. If \(n\) is odd, each flip keeps one bead in place while exchanging the rest in pairs. For a ring to be invariant under this action, the one bead can be any of \(c\) colors, any each exchanging pair must match each other by can otherwise be any of \(c\) colors. Since there are \(\frac{n-1}{2}\) pairs and one singleton, there are a total of \(c^{(n+1)/2}\) invariant cases. If \(n\) is even, half of the flips will be around axes that pass through two beads, leaving \(\frac{n-2}{2}\) pairs and two singletons for a total of \(c^{(n+2)/2}\) invariant cases. The other half of the flips will have \(\frac{n}{2}\) pairs and no singletons, for a total of \(c^{n/2}\) invariant cases. For the sake of finding common notation with the odd case, we can write \((n+2)/2\) as \(ceil((n+1)/2)\) and \(n/2\) as \(floor((n+1)/2)\).

That's all we need to apply Burnside's lemma! Because a couple of the types of group elements we chose turned out to have different-sized fixed sets depending on \(n\), our result will look a little different from the Wikipedia example, but the principle is the same.

\(P_{ring}(c,n)=\frac{1}{2n}(c^n+\sum_{m=1}^{n-1}G(c,n,m)+\frac{n}{2}(c^{ceil((n+1)/2)}+c^{floor((n+1)/2)}))\)

Edit: The formula as written here actually has a mistake. See my subsequent post for a correction.

I'm less confident in this answer than the last, so let's try a harder test case: 4 beads in 3 colors (red, green, and blue). According to our formula:

\(P_{ring}(3,4)=\frac{1}{8}(3^4+(3+3^2+3)+2(3^3+3^2))=\frac{1}{10}(81+15+72)=21\)

We got an integer - so far so good!

Please Register or Log in to view the hidden image!

Now let's see if brute force matches this result.

RRRR, RRRB, RRRG, RRBB, RBRB, RRGG, RGRG, RRBG, RBRG, RBBB, RGGG, RBBG, RBGB, RBGG, RGBG, BBGG, BGBG, BBBG, BGGG, BBBB, GGGG

HOLY $#*%! It actually worked! Special thanks to arfa brane, for pointing me in the right direction, and to the national science foundation, for paying my salary while I get distracted by problems like this.

 

What we learned to do was to count all the necklaces 'fixed' by each rotation or reflection. Obviously the identity fixes every necklace, and at the other extreme, a necklace with all beads the same is fixed by every operation.

So it's easy to calculate how many necklaces can be made with say, two colors of beads, but quite a bit harder to count the unique necklaces, because the symmetry group has 2n elements for n beads. For instance n = 4 has the symmetry of a square: four rotations (including the identity) and four reflections. If n is odd, there are no 180[sup]o[/sup] reflections.

Correction, a 180[sup]o[/sup] reflection necessarily has a line of symmetry through one bead and the edge opposite, so one bead is fixed.

 

Yeah, I was onto something here. In the Burnside's lemma formalism, I think cyclicality corresponds to the rotations symmetries and the \(G\) function I defined, while palindromocity (sp?) corresponds to the flipping symmetry. What I had trouble with was dealing with the fact that the "cycles" category has a lot of subdivisions: it can be cyclical with period 2, or 3, or 4 or... etc. And the periodicities overlap, too; any 2-periodic ring is also 4-periodic, but the reverse is not true. Burnside's lemma gave me just the formalism I needed to sum all these overlapping terms together with no over- or under-counting.

 

I just realized that my formula above isn't quite right. (Some part of me knew that the formula being right on the first try with no corrections was too good to be true.) The mistake is in the \(G\) function: even if \(n\) isn't evenly divisible by \(m\), there can still be rings that are symmetric under \(R_m\) as long as they're periodic with period equal to a common denominator of \(n\) and \(m\). For example, 6 is not evenly divisible by 4, but the string BWBWBW is symmetric under \(R_4\) because it consists of a repeating pattern of length 2, and 2 is a common factor of 6 and 4. In general, the exponent on \(c\) in \(G(c,n,m)\) will actually be equal to the greatest common factor of \(n\) and \(m\), \(gcf(n,m)\). On the plus side, this means I can write the expression without making up any new functions. What's more, \(c^n=c^{gcf(n,n)}\), so I can even use this notation to collapse the first term into the sum:

\(P_{ring}(c,n)=\frac{1}{2n}(\sum_{m=1}^{n}c^{gcf(n,m)}+\frac{n}{2}(c^{ceil((n+1)/2)}+c^{floor((n+1)/2)}))\)

This version of the expression seems to work for 12 and 13 beads (I was testing those cases for a related idea that didn't pan out), so hopefully it's right in general.

 

One of the NSF's jobs is to promote math and science education, so you can still wing it.

Please Register or Log in to view the hidden image!

Did you use a computer to find the permutations?

 

No - I just figured them out from the underlying symmetries of the problem. If it turns out I missed some, I'm gonna be really embarrassed.

 

Haha.

Please Register or Log in to view the hidden image!

How do you "know" that you've managed to get them all?

I was thinking about how to prove that the formula is correct. Either via computer exhaustion which will take forever, or by making sure that no false assumptions regarding the nature of beads and strings have been made.

 

Well, the list of rings comes from a thought process a bit more rigorous than just listing all the ones I could think of. Basically, I went through all the options regarding how "matching color groups" are partitioned across the string, then I made every possible choice of colors for a given partition. If all the beads are the same, you can choose their color (3 options). If 3 are the same and one is different, you can choose the color of the 3 and the color of the 1 (6 options). If there are two groups of two, the colors can be alternating or in pairs, and you can choose the absent color (2x3 options). If 2 are the same and the other 2 are different, the matching beads can either be adjacent or not, and you can choose their color (2x3 options). By the pigeonhole theorem, at least one color needs to appear twice in any ring, so these are all the options and they add up to 21.

Proving the correctness of the formula in general is more difficult. The Wikipedia page on Burnside's lemma links to the one on cycle indices as justification for how all the rotations on a cube were found. If one took some time to really understand the concepts there, I'm sure they could be applied to rigorously find the complete group of rotations and flips on a connected, rank 2 graph, which is isomorphic to a ring of beads. The cycle indices also make it really easy to see how many invariants are associated with each group element, so they would take all the heuristic parts out of my use of Burnside's lemma.

 

That highlights the difficulties of writing a listing algorithm. It's good that invariants allow us to not rely on any heuristic parts.