MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
You are counting bracelets. – 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… – Steve Huntsman May 30 '10 at 13:06
And for 2D: – 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
up vote 1 down vote accepted will get you started.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.