# Analytic Combinatorics for Computing Seeding Probabilities
## 3 Background
### Transfer Graphs and Transfer Matrices  
In many combinatorial applications, one needs to count the sequences where a pattern does not occur, or where some symbol may not follow another. A convenient way to find the weighted generating functions of such sequences is to encode this information in so-called transfer matrices [14; 24]. Generalizing the notion of incidence matrix of a graph, every transfer matrix is associated with a unique transfer graph. **Definition 2**: _A transfer graph is a directed graph whose edges are labelled by weighted generating functions. In addition, a transfer graph must contain a head vertex with only outgoing edges, and a tail vertex with only incoming edges. The matrix whose entry at position \((i,j)\) is the weighted generating function labelling the edge between vertices \(i\) and \(j\) is called the transfer matrix of the graph._  
**Remark 1**: _When all the weighted generating functions are polynomials, transfer graphs are equivalent to weighted sized graphs defined in [14] (p. 357, Definitions V.7 and V.8), where each monomial is considered a distinct edge between the same vertices._  
Following the edges of a transfer graph from the head vertex to the tail vertex describes a sequence of combinatorial objects. The associated weighted generating function is the product of the functions labelling the edges (thus, an absent edge is associated with the function 0). By convention, the vertices are ordered in the transfer matrix so that that the head vertex is first and the tail vertex is last. The first column of the transfer matrix is always 0 because the head vertex has no incoming edge, and the last row is always 0 because the tail vertex has no outgoing edge. Say that a transfer graph with \(m+2\) vertices is represented by the \((m+2)\times(m+2)\) transfer matrix \(M_{*}(z)\). The \"body\" of the transfer graph designates the sub-graph containing the \(m\) vertices that are neither the head nor the tail. \(M(z)\) denotes the \(m\times m\) matrix obtained by removing from the transfer matrix the rows and columns that correspond to the head and the tail. \(M(z)\) will be referred to as the \"body\" of the transfer matrix \(M_{*}(z)\). The rationale for breaking \(M_{*}(z)\) into blocks is that in general only \(M(z)\) contributes to the asymptotic growth rate. We also introduce \(H(z)\), the row vector of \(m\) weighted generating functions associated with the \(m\) edges from the head vertex to the body of the graph, and \(T(z)\), the column vector of \(m\) weighted generating functions associated with the edges from the body of the graph to the tail vertex. \(H(z)\) and \(T(z)\) are called the \"head\" and \"tail\" vectors, respectively. The weighted generating function labelling the edge from the head to the tail vertex is denoted \(\psi(z)\). The main interest of transfer graphs and transfer matrices is that they allow us to compute the weighted generating function of the sequences that correspond to paths from the head vertex to the tailvertex. The theorem below is useful for calculations, and it also shows that if all the entries of \(M_{*}(z)\) are polynomials, then only \(M(z)\) contributes to the asymptotic growth rate of the coefficients. Given a transfer matrix  
\[M_{*}(z)= \begin{pmatrix}0&H(z)&\psi(z)\\ 0&M(z)&T(z)\\ 0&0&0\end{pmatrix} ,\]  
where \(M(z)\) is a \(m\times m\) matrix, \(H(z)\) and \(T(z)\) are vectors of dimension \(m\) and \(\psi(z)\) has dimension \(1\), the weighted generating function of the sequences that correspond to all the possible paths from the head to the tail vertex of the transfer graph of \(M_{*}(z)\) is  
\[\psi(z)+H(z)\cdot(I-M(z))^{-1}\cdot T(z), \tag{3}\]  
where we assume that \(M(0)=0\) (the null matrix) and that all the eigenvalues of \(M(z)\) have modulus less than or equal to \(1\). Generalizing the proof of Proposition 1 shows that the weighted generating function of paths of the transfer graph from vertex \(i\) to vertex \(j\) is the entry at position \((i,j)\) of the matrix \((I-M_{*}(z))^{-1}\).