Are there any resources for numerical methods in extracting coefficients from generating functions?

61 Views Asked by At

Oftentimes in combinatorics, one can derive a closed form for a generating function, say $F(z)$, describing some scenario. From this function, we can extract the coefficient of $z^k$ to arrive at an answer for our counting problem. When $k$ is especially large however, the real problem sometimes lies in finding this coefficient. While there are times in which we can expand $F(z)$ in terms of geometric series and find the coefficients analytically, I believe that this isn't always true, thus I'm looking for some numerical methods to extract these coefficients.

The only real method I've seem to come up with (as opposed to taking many derivatives, which also does not seem to be very numerically stable) is one involving Fourier analysis methods and the orthogonality of exponential functions. In other words, if $$F(z) = \sum_{n = 0}^\infty a_n z^n,$$ then $$[z^k]F(z) = a_k = \frac{1}{2 \pi}\int_0^{2 \pi} F(e^{it}) \> e^{-ikt} \, dt.$$ In the case that $F(z)$ is not defined for $|z| = 1$, we can pick some constant $C \in (0, 1)$ and see similarly that $$a_k = \frac{C^{-k}}{2 \pi} \int_0^{2 \pi} F(Ce^{it}) \> e^{-ikt} \, dt.$$ However, in my experience, these are pretty finicky to use and not very numerically stable. For large values of $k$, they certainly aren't easy to work with. Thus my questions is: are there any common or general numerical methods for extracting coefficients of (large) powers in generating functions?

Any help would be greatly appreciated!