# Analytic Combinatorics for Computing Seeding Probabilities
## 3 Background
### Weighted Generating Functions  
The central object of analytic combinatorics is the _generating function_[13] (p. 92). Here, we will need the slightly more general concept of _weighted_ generating function, which are used in many areas of mathematics and physics, sometimes under different names and with different notations (see [21] (pp. 44-45) for an example in the context of combinatorial species and [22] (Theorem 1.3.2) for a more recent example in combinatorics). **Definition 1**. : _Let \(\mathcal{A}\) be a set of combinatorial objects characterized by a size and a weight that are nonnegative integer and nonnegative real numbers, respectively. The weighted generating function of_  
\[A(z)=\sum_{a\in\mathcal{A}}w(a)z^{|a|}, \tag{1}\]  
_where \(|a|\) and \(w(a)\) denote the size and weight of the object a (see [23] (Equation (1)) and [14] (p. 357, Equation (108))). Expression (1) also defines a sequence of nonnegative real numbers \((a_{k})_{k\geq 0}\) such that_  
\[A(z)=\sum_{k=0}^{\infty}a_{k}z^{k}. \tag{2}\]  
By definition, \(a_{k}=\sum_{a\in A_{k}}w(a)\), where \(A_{k}\) is the class of objects of size \(k\) in \(\mathcal{A}\). The number \(a_{k}\) is called the _total weight of objects of size \(k\)_. Expression (2) shows that the terms \(a_{k}\) are the coefficients of the Taylor series expansion of the function \(A(z)\). Combinatorial operations on sets of objects translate into mathematical operations on their weighted generating functions (see [13] (p. 95) and [14] (p. 166)). If two sets \(\mathcal{A}\) and \(\mathcal{B}\) are disjoint and have weighted generating functions \(A(z)\) and \(B(z)\), respectively, the weighted generating function of \(\mathcal{A}\cup\mathcal{B}\) is \(A(z)+B(z)\). This follows from  
\[\sum_{c\in\mathcal{A}\cup\mathcal{B}}w(c)z^{|c|}=\sum_{a\in\mathcal{A}}w(a)z^ {|a|}+\sum_{b\in\mathcal{B}}w(b)z^{|b|}.\]  
Size and weight can be defined for pairs of objects in \(\mathcal{A}\times\mathcal{B}\) as \(|(a,b)|=|a|+|b|\) and \(w(a,b)=w(a)w(b)\). In other words, the sizes are added and the weights are multiplied. With this convention, the weighted generating function of the Cartesian product \(\mathcal{A}\times\mathcal{B}\) is \(A(z)B(z)\). This simply follows from expression (1) and  
\[A(z)B(z)=\sum_{a\in\mathcal{A}}w(a)z^{|a|}\sum_{b\in\mathcal{B}}w(b)z^{|b|}= \sum_{(a,b)\in\mathcal{A}\times\mathcal{B}}w(a)w(b)z^{|a|+|b|}.\]  
**Example 1**. : _Let \(\mathcal{A}=\{a\}\) and \(\mathcal{B}=\{b\}\) be alphabets with a single letter of size \(1\). Assume \(w(a)=p\) and \(w(b)=q\). The weighted generating functions of \(\mathcal{A}\) and \(\mathcal{B}\) are then \(A(z)=pz\) and \(B(z)=qz\), respectively. The weighted generating function of the alphabet \(\mathcal{A}\cup\mathcal{B}=\{a,b\}\) is \(pz+qz=A(z)+B(z)\). The set \((\mathcal{A}\cup\mathcal{B})^{2}\) contains the four pairs of letters \((a,a)\), \((a,b)\), \((b,a)\) and \((b,b)\). They have size \(2\) and respective weight \(p^{2}\), \(pq\), \(qp\), and \(q^{2}\), so the weighted generating function of \((\mathcal{A}\cup\mathcal{B})^{2}\) is \((p^{2}+2 pq+q^{2})z^{2}=\big{(}A(z)+B(z)\big{)}^{2}\)._  
We can further extend the definition of size and weight to any finite Cartesian product in the same way. The sizes are always added and the weights are always multiplied. The generating function of a Cartesian product then comes as the product of their generating functions. This allows us to construct the weighted generating function of finite sequences of objects using formal power series (for more details, see [14] (p. 28 and p. 731)). **Proposition 1**: _Let \(\mathcal{A}\) be a set with weighted generating function \(A(z)=\sum_{k\geq 0}a_{k}z^{k}\). If \(a_{0}=0\), the weighted generating function of the set \(\mathcal{A}^{+}=\cup_{k=1}^{\infty}\mathcal{A}^{k}\) is well defined and is equal to_  
\[\frac{A(z)}{1-A(z)}.\]  
For \(k\geq 1\), the weighted generating function of \(\mathcal{A}^{k}\) is \(A(z)^{k}\).