The transfer-matrix method is an enumeration method that encodes allowable transitions among finitely many states by a matrix. A state records the boundary information needed to extend a partial object. For a fixed number of states, repeated extension becomes matrix multiplication (Stanley 1999).
Let 
be the total weight of allowed transitions from state 
to state 
, with weights in a field.
If the column vectors 
and 
specify initial and terminal weights, then the total weight
after 
transitions is
 |
where 
denotes the transpose of 
. The ordinary generating
function is
 |
where 
is the identity matrix. The inverse is interpreted
as a formal power series. Since 
has fixed finite size, this expression is a rational
function of 
,
and the coefficients satisfy a constant-coefficient
linear recurrence equation.
The method also counts walks in a directed graph, with 
its weighted adjacency matrix. For bounded-width
combinatorial constructions, the states can record connections across a moving boundary.
This approach gives generating functions for
knight's tours on fixed-width knight graphs (Elkies
and Stanley 2003).
