Abrazolica

This is a continuation of the previous post where now we are counting restricted necklaces. A restricted necklace is one where the symbols have to follow some rule. A simple example of this is not allowing the sequence \(11\) to appear in a binary necklace composed of \(0\)'s and \(1\)'s. Obviously the number of such necklaces will be less than the total number of binary necklaces. The first step in counting them is to find the number of circular binary words that do not contain the sequence \(11\). If \(f(k)\) is the number of these words of length \(k\) then the number of necklaces of length \(n\) is given by

\[\frac{1}{n}\sum_{d|n} \phi(d)f(n/d)\]

Notice that this is essentially the cycle index polynomial for the cyclic group \(C_n\) with \(z_{d}^{n/d}\) replaced by \(f(n/d)\).

Now what about the somewhat more difficult problem of counting how many of the necklaces have exactly \(k\) \(1\)'s? Once again this starts with counting circular words. The automaton for generating binary words that do not contain the sequence \(11\) is shown below.

Let \(x\) represent \(0\) and \(y\) represent \(1\) then the adjacency matrix for this automaton is

\[\mathbf{A}=\begin{bmatrix} x & y\\ x & 0 \end{bmatrix}\]

The generating function for the number of circular words is

\[g(x,y)=\mathrm{Tr}\;(\mathbf{I}-\mathbf{A})^{-1}=\frac{2-x}{1-x-xy}\]

The Taylor series expansion out to order \(4\) is

\[g(x,y)=2+x+(x^{2}+2xy)+(x^{3}+3x^{2}y)+(x^{4}+4yx^{3}+2y^{2}x^{2})+\cdots\]

The term \((x^{4}+4yx^{3}+2y^{2}x^{2})\) in the expansion is the generating function for strings of length \(4\). It says there is one circular word with all \(0\)'s, four words with a single \(1\) and three \(0\)'s, and two words with two \(1\)'s and two \(0\)'s. Let \(f_{n}(x,y)\) be the generating function for the number of circular words of length \(n\). Then these polynomials obey the recursion

\[f_{n}=xf_{n-1}+xyf_{n-2}\]

with \(f_{0}=2\), \(f_{1}=x\), and \(f_{2}=x^{2}+2xy\). The recursion can be solved to get the following expression for \(f_{n}(x,y)\).

\[f_{n}(x,y)=\frac{(x+\sqrt{x^{2}+4xy})^{n}+(x-\sqrt{x^{2}+4xy})^{n}}{2^n}\]

Now we can use this in the cycle index polynomial. Replace \(z_{d}\) with \(f_{n/d}(x^{d},y^{d})\)

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

This is the generating function for binary necklaces of length \(n\) that do not contain the sequence \(11\).

The same basic procedure can be used for necklaces with other kinds of restrictions.