# Abrazolica

### Blogroll

John Baez
John D Cook
Combinatorics Problem 1

I occasionaly get emails from people asking about combinatorics problems and I run into a lot of problems in my own research so I thought I would start posting some of them here. I've blogged about these problems before but only sporadically. The plan is to start doing it on a more regular basis and to include other types of problems from subjects such as probability and information theory. I may even throw in some physics and circuit design problems. They should all be fairly simple but interesting and understandable to people who have read some of our books. So let's start with a combinatorics problem.

The problem involves constructing strings from an alphabet of the $m$ symbols: $a_1,a_2,\ldots,a_m$. Each string starts with at most $n_1$ consecutive $a_1$'s followed by at most $n_2$ consecutive $a_2$'s and so on. All $n_i$ values are greater than zero and each symbol appears at least once. The question is how many unique strings of length $n$ can one construct?

Combinatorially we are asking for the number of compositions of $n$ into exactly $m$ parts with part $i$ in the range from $1$ to $n_i$. Suppose for example $n=5$, $m=3$, and $n_1=n_2=n_3=3$ then the compositions and corresponding strings using the symbols $0,1,2$ are

• $5 = 3+1+1\hspace{3em} 00012$
• $5 = 1+3+1\hspace{3em} 01112$
• $5 = 1+1+3\hspace{3em} 01222$
• $5 = 2+2+1\hspace{3em} 00112$
• $5 = 2+1+2\hspace{3em} 00122$
• $5 = 1+2+2\hspace{3em} 01122$

The simplest way to solve the general problem is to use a generating function. If you look at each string as a concatenation of $m$ substrings each composed of a single symbol with possible lengths $1,2,\ldots,n_i$ then it's very easy to construct the generating function. The substrings have generating functions given by

$z+z^2+z^3+\cdots+z^{n_i}$

and the generating function for the complete string is the product of these substring generating functions. For the example above, each substring has the g.f. $z+z^2+z^3$ so the total g.f. is $(z+z^2+z^3)^3$ which expanded out is:

$z^9+3z^8+6z^7+7z^6+6z^5+3z^4+z^3$

This tells us there's only one string of length 3 and 9. The strings are $012$ and $000111222$ respectively. There are three strings of length 4 and 8, they are $0012$, $0112$, $0122$ and $00011122$, $00011222$, $00111222$. There are six strings of length 5 and 7 and seven strings of length 6.

In the general case where we have $m$ symbols and each can repeat at most 3 times the generating function is $(z+z^2+z^3)^m$ and the numbers of possible strings will be given by the trinomial coefficients.

Another interesting case is when the symbol $a_i$ can repeat at most $i$ times. With 4 symbols for example, the generating function is

$z(z+z^2)(z+z^2+z^3)(z+z^2+z^3+z^4)$

which expanded out is

$z^{10}+3z^9+5z^8+6z^7+5z^6+3z^5+z^4$

The coefficients of these generating functions are the Mahonian numbers which have many interesting properties and interpretations.

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.

© 2010-2017 Stefan Hollos and Richard Hollos