Number of config. of a binary string invariant under cyclic permutation. - MathOverflow 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 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 Answer by Charles Matthews for Number of config. of a binary string invariant under cyclic permutation. 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>