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