Lesson 1

Sometimes a single number is not enough to write a convenient recurrence relation. Instead of counting all objects at once, we divide them into a few states and count how many objects are in each state. If the transition from one length to the next is always the same, this transition can be written as multiplication by a matrix. This idea is called the transfer-matrix method.

As an example, let us count binary strings of length \(n\) with no two consecutive ones. Let \(a_{n}\) be the number of such strings ending in \(0\), and let \(b_{n}\) be the number of such strings ending in \(1\). Then \[a_{n+1}=a_{n}+b_{n},\qquad b_{n+1}=a_{n}.\] Indeed, we may append \(0\) to any valid string, while we may append \(1\) only to a string that previously ended in \(0\).

In matrix form this becomes \[\begin{pmatrix}a_{n+1}&b_{n+1}\end{pmatrix} = \begin{pmatrix}a_n&b_n\end{pmatrix} \begin{pmatrix}1&1\\ 1&0\end{pmatrix}.\] So, in some sense, the matrix stores the rules of the problem: from the first state we can go to both the first and the second, while from the second state we can go only to the first one.