Abrazolica

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.

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)\).