CIRCLES OF STONES

How many different circles can be composed with *n* stones of *c* colors?
If *n=p* is prime the answer is

N(n,c) = ( c^{p} + (p-1) c ) / p

This result follows from Bernstein lemma, which says that the number of orbits of the
action of a group *G* on a set *X* is equal to the average number of fixed
elements, ie,

1/|G| Sum_{g} |{x | g(x)=x }|
The proof is very easy. Consider the actions of *G* on each orbit,
*Sum*_{O} Sum_{g} gO, and split the sum over *g*
in those elements that leave each point of the orbit fixed and those that
"move" the orbit.
The identity *e* of *G* fixes every *x* in *X* should be counted with
the elements that move the orbit.
Therefore the overall sum splits in the sum over *g* (except *e*)
of the counts of the elements
fixed by *g*, ie, |*X*_{g}|, and the sum of the size of each orbit.

|G| |O| = |X| + Sum'_{g} X_{g}
where the sum does not include the identity of *G*.

Now |*X*| is the size of the fixed points of *e*. Therefore this can also
included in the sum and the lemma is proved.

The group of symmetry if the circle is *C*_{n}. When *n=p* is prime,
the identity has *c*^{p} fixed points, while every other *g* has *c*
fixed points (the circles with stones of one color). Thsu the above result.

In general you can prove that (*phi* is Euler phi function)

N(n,c) = 1/n Sum_{d|n} c^{n/d} phi(d)
From this result you can check that, for *c* large enough
N(n,c) = Sum_{k=1..n+1} (n+1 choose k) (-)^{k+1} N(n,c-k)

N(n,c)
1 2 3 4 5 6 7 8 9 10
1 3 6 10 15 21 28 36 45 55
1 4 11 24 45 76 119 176 249 340
1 6 24 70 165 336 616 1044 1665 2530
1 8 51 208 629 1560 3367 6560 11817 20008
1 14 130 700 2635 ...
1 20 315 2344 ...

Finally, you can consider "necklaces" instead or circles.
In this case there are also reflection symmetries: *n* reflections about
a circle position, if *n* is odd, and *n/2* reflections about two
opposite positions and *n/2* about the mid-axis between positions, if *n*
is even. You can use Burnside lemma to compute the number of necklaces too.

Marco Corvi - 2013