Abrazolica


Home     Archive     Tags     About        RSS

Blogroll

John Baez
John D Cook
Counting Restricted Necklaces

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.


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.


Musical Chords

In music, the most harmonious frequency interval is the octave. Two notes are separated by an octave if one is twice the frequency of the other. In western music, the octave is divided into \(12\) notes, with the frequency ratio between adjacent notes being \(2^{1/12}\). A frequency interval with this ratio is called a semitone. The \(12\) notes that divide the octave are called the chromatic scale. The following table shows the frequency ratio of each note to the first note. The notes are numbered from \(0\) to \(12\). Note \(12\) is one octave up in frequency from note \(0\).

Note Frequency Ratio Rational approx
0 2^0 = 1.0 1/1
1 2^(1/12) = 1.059463094359295 18/17 = 1.0588
2 2^(1/6) = 1.122462048309373 9/8 = 1.125
3 2^(1/4) = 1.189207115002721 6/5 = 1.2
4 2^(1/3) = 1.259921049894873 5/4 = 1.25
5 2^(5/12) = 1.334839854170034 4/3 = 1.3333
6 2^(1/2) = 1.414213562373095 7/5 = 1.4
7 2^(7/12) = 1.498307076876682 3/2 = 1.5
8 2^(2/3) = 1.587401051968199 8/5 = 1.6
9 2^(3/4) = 1.681792830507429 5/3 = 1.67
10 2^(5/6) = 1.781797436280679 9/5 = 1.8
11 2^(11/12) = 1.887748625363387 15/8 = 1.875
12 2^(1) = 2.0 2/1

Two notes with frequency ratios that can be approximated as a ratio of small integers will be the most harmonious. So note \(0\) and note \(7\) will be the most harmonious, since their frequency ratio is approximately \(3/2\). The next most harmonious combination is note \(0\) and \(5\) which has a ratio of \(4/3\). Two notes next to each other are the most dissonant.

Let's take a \(12\) bead necklace with beads of two colors (also called binary) to represent chords (simultaneously played notes) of the chromatic scale. Using colors black and white, there are \(30\) binary necklaces with no two adjacent beads being black, ignoring the one with all white beads. These are shown below.

If we take the rightmost bead to be the \(C\) note, and label beads counterclockwise with the \(12\) notes (C,C#,D,D#,E,F,F#,G,G#,A,A#,B) in ascending order of frequency, taking a black bead to mean the corresponding note is played, we can listen to these \(30\) necklaces as chords below.

30 chords with no adjacent notes


A Derivation of Wallis's Formula for Pi

For \(\pi\) day plus one, here is a derivation of Wallis's formula for \(\pi\) that is based on probability distributions. Start with the binomial distribution for a fair coin toss. The probability of getting \(k\) heads on \(n\) tosses is

\[\binom{n}{k}\frac{1}{2^{n}}\]

Assume an even number of tosses, \(n=2m\). Then the distribution has a maximum at \(k=m\) of

\[\binom{2m}{m}\frac{1}{2^{2m}}\]

For large \(n\), the binomial distribution can be closely approximated by a Normal probability density function give by

\[p(x)=\frac{1}{\sigma\sqrt{2\pi}}\exp{-\frac{(x-\mu)^{2}}{2\sigma^{2}}}\]

where \(\mu=n/2=m\) and \(\sigma^2=n/4=m/2\). The maximum at \(x=\mu\) is

\[p(\mu)=\frac{1}{\sqrt{m\pi}}\]

Comparing this with the maximum for the binomial distribution and taking the limit as \(m\to\infty\), you get

\[\frac{1}{\sqrt{\pi}}=\lim_{m\to\infty}\binom{2m}{m}\frac{\sqrt{m}}{2^{2m}}\]

Now we just need the following double factorial identities

\[(2m)!=(2m-1)!!2^{m}m!\]

\[2^{m}m!=(2m)!!\]

Then we can write

\[\binom{2m}{m}\frac{\sqrt{m}}{2^{2m}}=\frac{(2m-1)!!}{(2m)!!}\sqrt{m}\]

and \(\pi\) can be expressed as

\[\pi=\lim_{m\to\infty}\frac{1}{m}\left(\frac{(2m)!!}{(2m-1)!!}\right)^{2}\]

or in product form as

\[\pi=\lim_{m\to\infty}\frac{1}{m}\prod_{k=1}^{m}\left(\frac{2k}{2k-1}\right)^{2}\]

This is almost Wallis's formula. To get there, note that

\[\prod_{k=1}^{m}(2k-1)^{2}=\frac{1}{2m+1}\prod_{k=1}^{m}(2k-1)(2k+1)\]

Substitute this into the above formula, take the limit and you get Wallis's formula

\[\pi=2\prod_{k=1}^{\infty}\frac{(2k)^{2}}{(2k-1)(2k+1)}\]

Is that cool or what?



© 2010-2017 Stefan Hollos and Richard Hollos