Posers and Puzzles

Posers and Puzzles

  1. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    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. Joined
    12 Apr '06
    Moves
    202
    19 Apr '06 18:23
    an infinite number - circles can be infinitely big
  3. Joined
    11 Nov '05
    Moves
    43938
    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 memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    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. Joined
    04 Jan '04
    Moves
    25350
    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 memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    20 Apr '06 07:52
    Originally posted by howardbradley
    Do reflections count as distinct?
    No, nor do rotations.
  7. Joined
    04 Jan '04
    Moves
    25350
    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 memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    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. Joined
    04 Jan '04
    Moves
    25350
    24 Apr '06 01:172 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. Joined
    04 Jan '04
    Moves
    25350
    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)
Back to Top