Posers and Puzzles
19 Apr 06
19 Apr 06
This is the general case of something relatively easy, but presumably it involves a lot of legwork.
Given n beads and some partition of {1,2,...n} into m subsets of size k(1), k(2),...k(m), let the beads of each subset be given a different colour (ie, we have k(1) white beads, k(2) yellow ones, etc). How many essentially different necklaces (arrangement of beads in a circle) are possible?
20 Apr 06
Originally posted by howardbradleyIt doesn't really matter, since the factor by which this changes things is simple, so I'll say no.
Further clarification required.
If we have just two beads (and two possible colours) are the possibilities:
i) YW
or ii) YW and YY
or iii) YW, YY and WW
Similarly, for three beads, is YYW different from YWW?
24 Apr 06
2 edits
Originally posted by royalchickenNope, this has me beat. Aside from a few very specific (and in some cases trivial) results, I can't get anywhere.
This is the general case of something relatively easy, but presumably it involves a lot of legwork.
Given n beads and some partition of {1,2,...n} into m subsets of size k(1), k(2),...k(m), let the beads of each subset be given a different colour (ie, we have k(1) white beads, k(2) yellow ones, etc). How many essentially different necklaces (arrangement of beads in a circle) are possible?
A couple of results:
For 3 colours with k(1) = k(2) = 1, and k(3) = p = n-2
N = 1 + int(p/2)
For 4 colours with k(1) = k(2) = k(3) = 1 and k(4) = p = n-3
N = (p+1)(p+2)/2 - the triangle numbers which is a vaguely interesting result.
For fun, I had a program work out necklaces of two colours where k(1) = k(2) = n/2 ie all the necklaces with equal numbers of white and yellow beads. This gives the sequence: 1, 1, 2, 3, 8, 16, 50, 133, 440, 1387, ...
I looked that up in The On-Line Encyclopedia of Integer Sequences (http://www.research.att.com/~njas/sequences - a great resource) and it was there, but I didn't understand the formula :-( Oh well.