Abrazolica


Home     Archive     Tags     About        RSS

Blogroll

John Baez
John D Cook
Englishmen and Frenchmen

A reader of our combinatorics books emailed us recently about a group of problems in the fifth edition (1901) of Whitworth's "Choice and Chance". The first of these problems (Problem 786 on pg 276) is as follows: Six Englishmen and six Frenchmen stand in a row so that every man has a compatriot next to him. Show that the number of possible arrangements is 34.

This problem can be solved using the methods outlined in our book Combinatorics II Problems and Solutions: Counting Patterns.

The automaton for this problem is

where S is the start state, E1 represents the start of a group of Englishmen, F1 represents the start of a group of Frenchmen. E2 and F2 represent subsequent Englishmen and Frenchmen in a group. The end states are E2 and F2. From this automaton we can construct an adjacency matrix, with \(x =\) E and \(y =\) F, which is:

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

where the rows and columns consecutively show transitions to states S, E1, E2, F1, and F2. Defining matrix B as

\[\mathbf{B}=(\mathbf{I}-\mathbf{A})^{-1}\]

then the generating function we want is a sum of two matrix elements of B

\[g(x,y)=\mathbf{B}_{13}+\mathbf{B}_{15}\]

where \(\mathbf{B}_{13}\) represents starting at S and ending at E2, and \(\mathbf{B}_{15}\) represents starting at S and ending at F2.

The generating function works out to be

\[g(x,y)=\frac{2x^2y^2-x^2y-xy^2+x^2+y^2}{1-x^2y^2+xy-x-y}\]

A Taylor series expansion will give you the answer for this problem and the next three problems (Problems 786-789). It will actually give you the answer to any problem involving \(n\) Englishmen and \(m\) Frenchmen. The answer is the coefficient of \(x^ny^m\) in the expansion. The coefficient of \(x^6y^6\) is \(34\), which is the answer to Problem 786. The coefficient of \(x^7y^7\) is \(84\), which is the answer to Problem 787. The coefficient of \(x^8y^8\) is \(208\), which is the answer to Problem 788, and the coefficient of \(x^8y^7\) is \(129\), which is the answer to Problem 789.

What we've just shown is by far the easiest way to solve the problem. You can also solve it by combinatorial reasoning. Let's say we have \(n\) Englishmen and \(m\) Frenchmen. An acceptable arrangement will consist of \(k\) groups of Englishmen, where each group has at least two members, surrounded by either \(k-1\), \(k\), or \(k+1\) groups of Frenchmen that have at least two members each. Let \(\Box\) represent a group of Englishmen and \(\triangle\) represent a group of Frenchmen then for \(k=3\) the acceptable arrangements are

\[\begin{matrix} \Box & \triangle & \Box & \triangle & \Box & &\\ \triangle & \Box & \triangle & \Box & \triangle & \Box &\\ \Box & \triangle & \Box & \triangle & \Box & \triangle &\\ \triangle & \Box & \triangle & \Box & \triangle & \Box & \triangle \end{matrix}\]

The number of ways to divide a group of \(n\) objects into \(k\) groups is

\[\binom{n+k-1}{k-1}\]

If each of the \(k\) groups has to have at least two objects in it then you subtract \(2k\) from \(n\). The number of ways to divide a group of \(n\) objects into \(k\) groups with at least two objects in each group is then

\[\binom{n-k-1}{k-1}\]

Using this expression for partitioning the Englishmen and the corresponding expression for partitioning the Frenchmen, you get the following formula for arranging \(n\) Englishmen and \(m\) Frenchmen such that each has at least one compatriot next to him.

\[a(n,m)=\sum_{k}\binom{n-k-1}{k-1}\left[\binom{m-k}{k-2}+2\binom{m-k-1}{k-1}+\binom{m-k-2}{k}\right]\]

If you do the calculation you will find that \(a(n,m)\) is equal to the coefficient of \(x^ny^m\) in the Taylor series expansion of \(g(x,y)\).


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



© 2010-2017 Stefan Hollos and Richard Hollos