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

Tweet

blog comments powered by Disqus