Back to October Calendar	←Previous Entry	Next Entry→
October 17, 2005 Let’s look at some specific cases.

 

Necklace Case 1: N is odd.

 

Case 1a:  The C_i’s are relatively prime and the number of odd C_i’s 1.

 

      (1)  In this case, the number of necklaces is  

Here’s an example of this case: 3 red beads, 2 green beads, 1 blue and 1 yellow bead.

So N = 7 and there are  

I tabulate these 30 necklaces below, sorted by whether the majority 3 reds is all together or split to 2 or 3 separate pieces.  I first thought that organizing them by the color/letter system might be niftyit is colorful, but the computer program I wrote produced digits instead of colors.  In the tabulation below, I present both together; first the color/letter representation then the digit sequence.  Remember, these are (at least, supposed to be) unique up rotation/reflection actions on the permutations, so it’s not so obvious if there is or isn’t a repetition.  I organized these by the decimal value they represent, from smallest to largest.  Do you see any interesting patterns?  Any mistakes?!

 

Three R’s together (6)	Two R’s together (18)		No R’s together (6)
RRRGGBY 1 1 1 2 2 3 4 RRRGGYB 1 1 1 2 2 4 3 RRRGBGY 1 1 1 2 3 2 4 RRRGYBG 1 1 1 2 4 3 2 RRRGYGB 1 1 1 2 4 2 3 RRRBGGY 1 1 1 3 2 2 4	RRGRGBY 1 1 2 1 2 3 4 RRGRGYB 1 1 2 1 2 4 3 RRGRBYG 1 1 2 1 3 4 2 RRGRYGB 1 1 2 1 4 2 3 RRGRYBG 1 1 2 1 4 3 2 RRGGRBY 1 1 2 2 1 3 4 RRGGRYB 1 1 2 2 1 4 3 RRGGBRY 1 1 2 2 3 1 4 RRGGYRB 1 1 2 2 4 1 3	RRGBRGY 1 1 2 3 1 2 4 RRGYRGB 1 1 2 4 1 2 3 RRGYRBG 1 1 2 4 1 3 2 RRBRGYG 1 1 3 1 2 4 2 RRBRGGY 1 1 3 1 2 2 4 RRBGRGY 1 1 3 2 1 2 4 RRBGGRY 1 1 3 2 2 1 4 RRYRGBG  1 1 4 1 2 3 2 RRYGBRG 1 1 4 2 3 1 2	RGRGRBY 1 2 1 2 1 3 4 RGRBRYG 1 2 1 3 1 4 2 RGRYRBG 1 2 1 4 1 3 2 RGRYRBG 1 2 1 4 1 2 3 RBRGRYG 1 3 1 2 1 4 2 RBRYRGG 1 3 1 4 1 2 2

                       

I actually found it pretty tough to come up with these, so I wrote a c++ program to produce them.  Here’s Jim Matthews’ proof for the formula.
                                         

      Proof of case 1a formula:  Recall that Q = N!/prod(C_i,i,1,n)  is the number of permutation of the beads, not accounting for equivalence of rotations and reflections.  We divide by 2N since each of these arrangements belongs to an equivalence class of size 2N  (The effect of N rotations and 2 orientations via reflection).  The condition that the C_i’s are relatively prime and the number of odd C_i’s is > 1 (for instance, in the example above, there are 3 odd C_i’s: 3 reds, 1 blue and 1 yellow) means that each of the 2N elements of a rotation/reflection equivalence is unique  every non-trivial action in G produces a different permutation.  Now, if for some rotation by m, where ,  r^m(x) = x, then m divides N and also. For each color C_i,  divides C_i.  So if the C_i’s are relatively prime then there greatest common divisor is 1 and so m = N, which is a contradiction.  The condition that the number of odd C_i’s is > 1, along with the condition that N is odd prevents f from acting as the identity on any permutation.  To see this, note that when N is odd, f leaves the center bead fixed and reflects the rest about it.  So for f to act as identity, the number of beads of the center bead color would have to be odd while all other colors C_i’s would have to have be even.  QED.