Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member royalchicken
    CHAOS GHOST!!!
    19 Apr '06 16:15
    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?
  2. 19 Apr '06 18:23
    an infinite number - circles can be infinitely big
  3. 19 Apr '06 18:30
    Originally posted by laur3tta
    an infinite number - circles can be infinitely big
    In theory - yes.
    In reality - no.
    The known universe is not large enough...
  4. Standard member royalchicken
    CHAOS GHOST!!!
    19 Apr '06 18:33
    Originally posted by laur3tta
    an infinite number - circles can be infinitely big
    I mean, how many essentially different cyclical orderings of the beads are possible?
  5. 19 Apr '06 22:37
    Originally posted by royalchicken
    I mean, how many essentially different cyclical orderings of the beads are possible?
    Do reflections count as distinct?
  6. Standard member royalchicken
    CHAOS GHOST!!!
    20 Apr '06 07:52
    Originally posted by howardbradley
    Do reflections count as distinct?
    No, nor do rotations.
  7. 20 Apr '06 16:28
    Originally posted by royalchicken
    No, nor do rotations.
    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?
  8. Standard member royalchicken
    CHAOS GHOST!!!
    20 Apr '06 18:41
    Originally posted by howardbradley
    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?
    It doesn't really matter, since the factor by which this changes things is simple, so I'll say no.
  9. 24 Apr '06 01:17 / 2 edits
    Originally posted by royalchicken
    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?
    Nope, this has me beat. Aside from a few very specific (and in some cases trivial) results, I can't get anywhere.

    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.
  10. 24 Apr '06 03:54
    OK here's a more general conjecture (nothing more).

    For k(1) = k(2) = ... = k(m-1) = 1 and k(m) = p ie a lot of one colour and one each of a lot of colours.

    N = 1/2 * (p+m-2)! / p! (m>3)