# Analytic Combinatorics for Computing Seeding Probabilities
## 3 Background
### Asymptotic Estimates  
The notion of weight corresponds to the frequency or the probability of the associated objects. The point of the analytic combinatorics approach is that we can create objects of increasing complexity and find their weighted generating function using Theorem 1 or equivalent. Meanwhile, we know from expression (2) that we can recover the total weight of objects of size \(k\) from the Taylor expansion of their weighted generating function. We will see below that there exists an efficient way to approximate those coefficients. Since we will often need to refer to \(a_{k}\) in expressions of the form \(A(z)=\sum_{k=1}^{\infty}a_{k}z^{k}\), we define the symbol \([z^{k}]A(z)\), referred to as the \"coefficient of \(z^{k}\) in \(A(z)\)\". Theorem 2 below is a special case of a very important theorem of the field, showing how to extract the coefficients of a generating function (see more general cases in (25) (p. 498, Theorem 4) and in (12) (pp. 5-9, Theorem 1 and Corollary 3)). **Theorem 2**. : _If \(A(z)\) can be written as the ratio of two polynomials \(P(z)/Q(z)\) with \(P\) and \(Q\) coprime and \(Q(0)\
eq 0\), and if \(Q\) has exactly one root \(z_{1}\) with minimum modulus and with multiplicity \(1\), then_  
\[[z^{k}]A(z)\sim-\frac{P(z_{1})}{Q^{\prime}(z_{1})}\frac{1}{z_{1}^{k+1}}. \tag{4}\]  
**Lemma 1**. : _For \(n\geq 0\) and every complex number \(a\
eq 0\),_  
\[\frac{1}{(1-z/a)^{n+1}}=\sum_{k=0}^{\infty}\binom{k+n}{n}\frac{z^{k}}{a^{k}}. \tag{5}\]  
Proof of Lemma 1.: Using \(A(z)=z/a\) in Proposition 1 and adding 1 to the final result, we obtain  
\[\frac{1}{1-z/a}=\sum_{k=0}^{\infty}\frac{z^{k}}{a^{k}}.\]  
Differentiating this equality \(n\) times, we obtain  
\[\frac{n!}{a^{n}}\frac{1}{(1-z/a)^{n+1}}=\sum_{k=n}^{\infty}k(k-1)\ldots(k-n+1) \frac{z^{k-n}}{a^{k}}.\]  
Rearranging the terms on both sides of the equality and shifting the index of the sum yields expression (5). Proof of Theorem 2.: Assume without loss of generality that the degree of \(P\) is lower than the degree of \(Q\). Say that \(Q\) can be factored as \((z-z_{1})(z-z_{2})^{v_{2}}\ldots(z-z_{n})^{v_{n}}\), where \(|z_{1}|<|z_{2}|\leq\ldots\leq|z_{n}|\). There exist complex numbers \(\beta_{1},\beta_{2,1},\ldots,\beta_{2,v_{2}},\ldots,\beta_{n,1},\ldots,\beta_{ n,v_{n}}\) such that the partial fraction expansion of \(P(z)/Q(z)\) can be written as  
\[P(z)/Q(z)=\frac{\beta_{1}}{z_{1}-z}+\frac{\beta_{2,1}}{z_{2}-z}+\frac{\beta_{ 2,2}}{(z_{2}-z)^{2}}+\ldots+\frac{\beta_{2,v_{2}}}{(z_{2}-z)^{v_{2}}}+\ldots+ \frac{\beta_{n,1}}{z_{n}-z}+\ldots+\frac{\beta_{n,v_{n}}}{(z_{2}-z)^{v_{n}}}. \tag{6}\]  
From Lemma 1, we can expand the terms of the sum as  
\[\frac{\beta_{j,m}}{(z_{j}-z)^{m}}=\frac{\beta_{j,m}}{z_{j}^{m}(1-z/z_{j})^{m} }=\frac{\beta_{j,m}}{z_{j}^{m-1}}\sum_{k=0}^{\infty}\binom{k+m-1}{m-1}\frac{z ^{k}}{z_{j}^{k+1}}.\]  
Substituting the expression above in expression (6), we obtain  
\[[z^{k}]A(z)=\frac{\beta_{1}}{z_{1}^{k+1}}+\frac{\alpha_{2,k}}{z_{2}^{k+1}}+ \ldots+\frac{\alpha_{n,k}}{z_{n}^{k+1}}, \tag{7}\]  
where  
\[\alpha_{j,k}=\sum_{m=1}^{v_{j}}\binom{k+m-1}{m-1}\frac{\beta_{j,m}}{z_{j}^{m- 1}}=O\big{(}k^{v_{j}-1}\big{)}.\]  
Since \(z_{1}\) is the root with smallest _modulus_, the sum (7) is dominated by the term \(z_{1}^{-k-1}\) as \(k\) increases, so the coefficient of \(z^{k}\) in \(A(z)\) is asymptotically equivalent to \[[z^{k}]A(z)\sim\frac{\beta_{1}}{z_{1}^{k+1}}.\]  
To find the value of \(\beta_{1}\), we keep only the first term of the partial fraction decomposition. More specifically, there exist two polynomials \(P_{1}\) and \(Q_{1}\) such that  
\[\frac{P(z)}{Q(z)}=\frac{P(z)}{(z_{1}-z)Q_{1}(z)}=\frac{\beta_{1}}{z_{1}-z}+ \frac{P_{1}(z)}{Q_{1}(z)}.\]  
Since \((z_{1}-z)\) does not divide \(Q_{1}\), we can multiply this expression through by \((z_{1}-z)\) and set \(z=z_{1}\) to obtain \(P(z_{1})/Q_{1}(z_{1})=\beta_{1}\).