Abrazolica


Home     Archive     Tags     About        RSS
Counting Necklaces

To define a necklace start with the idea of a circular word. These are strings of symbols where the last symbol is followed by, or is adjacent to, the first symbol. If the binary string \(0011\) is circular then the last \(1\) is followed by the first \(0\). You can think of these strings as being labels on a circle. So there is no first or last symbol. Necklaces are sets of circular strings where no two strings are related by a circular shift of the symbols. In other words the strings \(011\), \(0110\), \(1100\), \(1001\) are all just different representations of the same necklace. When counting the number of binary necklaces of length \(4\) only one of these strings is counted. In total, there are \(6\) unique binary necklaces of length \(4\). They are \(0000(1)\), \(0001(4)\), \(0011(4)\), \(0101(2)\), \(0111(4)\), \(1111(1)\). The numbers in parentheses are the number of unique ways each necklace can be represented. If you add up those numbers you get \(16\), the number of binary strings of length \(4\).

In this case it was fairly easy to count the number of necklaces by just writing them down. But this quickly becomes impossible for longer necklaces with more symbols, especially when there are restrictions on the kinds of substrings that can appear. It is fairly easy however to solve most necklace counting problems by using the cycle index polynomials for the cyclic groups. For necklaces of length \(n\) the cycle index of the cyclic group \(C_n\) is

\[p(z_{1},z_{2},\ldots,z_{n}) = \frac{1}{n}\sum_{d|n} \phi(d)z_{d}^{n/d}\]

This is a polynomial in the variables \(z_{1},z_{2},\ldots,z_{n}\). The sum is over all the divisors of \(n\) and \(\phi(d)\) is the euler totient function, equal to the number of integers from \(1\) to \(n\) that are relatively prime to \(n\), i.e. integers \(k\) such that \(\gcd(n,k)=1\) and \(1\le k \le n\).

The number of necklaces of length \(n\) using \(m\) symbols is gotten from the cycle index by setting all the \(z\) variables equal to \(m\).

\[p_{n}(m) = \frac{1}{n}\sum_{d|n} \phi(d)m^{n/d}\]

These are now polynomials in \(m\), the first few of which are:

\[p_{1}(m) = m\] \[p_{2}(m) = \frac{1}{2}(m^{2}+m)\] \[p_{3}(m) = \frac{1}{3}(m^{3}+2m)\] \[p_{4}(m) = \frac{1}{4}(m^{4}+m^{2}+2m)\]

The table below shows the number of necklaces of length \(n=2,3,\ldots,12\) using \(m=2,3,4,5,6\) symbols.

n 2 3 4 5 6
2 3 6 10 15 21
3 4 11 24 45 76
4 6 24 70 165 336
5 8 51 208 629 1560
6 14 130 700 2635 7826
7 20 315 2344 11165 39996
8 36 834 8230 48915 210126
9 60 2195 29144 217045 1119796
10 108 5934 104968 976887 6047412
11 188 16107 381304 4438925 32981556
12 352 44368 1398500 20346485 181402676

To get the number of necklaces of length \(n\) using two symbols, let \(x\) and \(y\) represent the symbols, and set \(z_{d}=x^{d}+y^{d}\) in the cycle index.

\[p_{n}(x,y) = \frac{1}{n}\sum_{d|n} \phi(d)(x^{d}+y^{d})^{n/d}\]

For the case of \(n=6\) we get the polynomial

\[p_{6}(x,y)=y^{6}+xy^{5}+3x^{2}y^{4}+4x^{3}y^{3}+3x^{4}y^{2}+x^{5}y+x^{6}\]

which says that there is one necklace with all \(y\) symbols, one with \(5\) \(y\) and \(1\) \(x\), three with \(4\) \(y\) and \(2\) \(x\), four with \(3\) \(y\) and \(3\) \(x\), and so on. The information in \(p_{6}(x,y)\) however, is redundant since if we know there are \(k\) \(x\) symbols then the number of \(y\) symbols must be \(6-k\). So a polynomial in just \(x\) is enough. To get \(p_{n}(x)\) set \(z_{d}=x^{d}+1\) in the cycle index.

\[p_{n}(x,y) = \frac{1}{n}\sum_{d|n} \phi(d)(x^{d}+1)^{n/d}\]

The table below shows the number of binary necklaces of length \(n=2,3,\ldots,12\) with \(k=0,1,\ldots,n\) \(x\) symbols.

n 0 1 2 3 4 5 6 7 8 9 10 11 12
2 1 1 1 . . . . . . . . . .
3 1 1 1 1 . . . . . . . . .
4 1 1 2 1 1 . . . . . . . .
5 1 1 2 2 1 1 . . . . . . .
6 1 1 3 4 3 1 1 . . . . . .
7 1 1 3 5 5 3 1 1 . . . . .
8 1 1 4 7 10 7 4 1 1 . . . .
9 1 1 4 10 14 14 10 4 1 1 . . .
10 1 1 5 12 22 26 22 12 5 1 1 . .
11 1 1 5 15 30 42 42 30 15 5 1 1 .
12 1 1 6 19 43 66 80 66 43 19 6 1 1

The extension to \(k\) symbols is obvious. You just let \(z_{d}=x_{1}^{d}+x_{2}^{d}+\cdots+x_{k}^{d}\) in the cycle index where \(x_i\) represents the \(i^{th}\) symbol. What is not so obvious is how to count the necklaces with restricted patterns such as not allowing adjacent \(x\) symbols. I will show how to do that in the next post.


© 2010-2017 Stefan Hollos and Richard Hollos

submit to reddit   

blog comments powered by Disqus