most recent 30 from http://mathoverflow.net 2013-05-23T10:01:00Z http://mathoverflow.net/feeds/question/26443 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/26443/number-of-config-of-a-binary-string-invariant-under-cyclic-permutation jonalm 2010-05-30T12:43:44Z 2010-05-30T12:59:15Z

<p>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). </p> <p>Anyways, here is the problem:</p> <p>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?</p> <p>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.</p> <p>I would really appreciated some help, or references on relevant literature.</p>

http://mathoverflow.net/questions/26443/number-of-config-of-a-binary-string-invariant-under-cyclic-permutation/26445#26445 Charles Matthews 2010-05-30T12:59:15Z 2010-05-30T12:59:15Z

<p><a href="http://en.wikipedia.org/wiki/Necklace_(combinatorics" rel="nofollow">http://en.wikipedia.org/wiki/Necklace_(combinatorics</a>) will get you started.</p>