Exploring Generating Functions in Combinatorics

This chapter introduces the Matrix-Tree Theorem and shows how matrix determinants can be used to count spanning trees in graphs.

Ordinary generating functions

Remark

the generating function is not actually regarded as a functions,it is a formal power series,so it is not required to converge

if we are given a genreating function,how can we get its corresponding sequence,the idea is to use the geometric series

$$ \frac{1}{1 - x} = \sum_{n \ge 0}x^n $$

the coefficient of the $x^n$-$term$ is $[x_n]G(x) = a_1 b_1^n + a_2 b_2^n + \dots + a_k b_k^n$

Generally, we may use the Taylor expansion of $G(x)$ at $x=0$,Recall that the Taylor series of a function $G(x)$ is

$$ G(x)=\sum_{n\ge 0}\frac{G^{(n)}(0)}{n!}x^n $$

Comparing the two expressions, we obtain

$$ a_n=\frac{G^{(n)}(0)}{n!} $$

Hence, the coefficients of the generating function can be recovered from the derivatives of $G(x)$.

Operating on generating function

Translating sequences into polynomials is advantegeous

Built with Hugo
Theme Stack designed by Jimmy