Beads

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?

an infinite number - circles can be infinitely big

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...

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?

Originally posted by royalchicken
I mean, how many essentially different cyclical orderings of the beads are possible?

Do reflections count as distinct?

Originally posted by howardbradley
Do reflections count as distinct?

No, nor do rotations.

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?

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.

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.

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)