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) = ( cp + (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| Sumg |{x | g(x)=x }|
The proof is very easy. Consider the actions of G on each orbit, SumO Sumg 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, |Xg|, and the sum of the size of each orbit.
|G| |O| = |X| + Sum'g Xg
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 Cn. When n=p is prime, the identity has cp 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 Sumd|n cn/d phi(d)
From this result you can check that, for c large enough
N(n,c) = Sumk=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