Abrazolica

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.