# Number of config. of a binary string invariant under cyclic permutation.

The following combinatorial problem has bothered me quite a bit. I guess people smarter than me have given the problem some taught as the problem has obvious applications (e.g. to the Ising model), but I have not found any solution on the web (this might be because I don't know the proper terminology).

Anyways, here is the problem:

Consider a string of $N$ binary variables, $\uparrow$ and $\downarrow$. The string will have $2^N$ different configurations. Now impose a symmetry to the system; two configurations are equal if you can get from one to the other by cyclic permutation or by reversal of the string (or a combination of these two symmetries). How many unique configurations will the string have?

For 1 $\uparrow$ and $N-1$ $\downarrow$ there will only be 1 unique configuration. For 2 $\uparrow$ and $N-2$ $\downarrow$ there will be $N/2$ configurations if $N$ is even and $(N-1)/2$ configurations if $N$ is odd. But if you take 3 $\uparrow$ and $N-3$ $\downarrow$, it is no longer clear (at least not to me), how one efficiently should count the number of possible configurations.

I would really appreciated some help, or references on relevant literature.

-
You are counting bracelets. en.wikipedia.org/wiki/Necklace_(combinatorics) –  Gjergji Zaimi May 30 '10 at 12:58
As your question implies, you can solve the 1D spin-1/2 Ising model this way, and more generally short-ranged spin models. In two dimensions the problem is that there's not a suitable generalization of the matrix-tree theorem. See also mathoverflow.net/questions/12214/… –  Steve Huntsman May 30 '10 at 13:06
And for 2D: mathoverflow.net/questions/10752 –  Steve Huntsman May 30 '10 at 13:09
Thank you for the input. @Streve: do you know of a reference for the solution of the 1D Ising model related to Necklace combinatorics. –  jonalm Jun 1 '10 at 9:33

http://en.wikipedia.org/wiki/Necklace_(combinatorics) will get you started.

-
The final parenthesis should be part of the address, but MathOverflow doesn't know it. –  Kevin O'Bryant May 30 '10 at 13:46