A rational generating function $G(x) = \frac{P(x)}{Q(x)}$ where $\deg(P) < \deg(Q)$ can be decomposed into partial fractions. If $Q(x) = (1-r_1x)^{m_1}(1-r_2x)^{m_2}\cdots(1-r_kx)^{m_k}$, then: $G(x) = \sum_{i=1}^{k} \sum_{j=1}^{m_i} \frac{A_{i,j}}{(1-r_ix)^j}$

Each term $\frac{A}{(1-rx)^j}$ has generating function $A\sum_{n=0}^{\infty} \binom{n+j-1}{j-1}r^n x^n$.

For any real number $\alpha$ and $|x| < 1$: $(1+x)^\alpha = \sum_{n=0}^{\infty} \binom{\alpha}{n} x^n$

where $\binom{\alpha}{n} = \frac{\alpha(\alpha-1)\cdots(\alpha-n+1)}{n!}$ is the generalized binomial coefficient.

Special cases:

• $(1-x)^{-1} = \sum_{n=0}^{\infty} x^n$
• $(1-x)^{-2} = \sum_{n=0}^{\infty} (n+1)x^n$
• $(1-x)^{-k} = \sum_{n=0}^{\infty} \binom{n+k-1}{k-1} x^n$

If $A(x)$ and $B(x)$ are exponential generating functions for $\{a_n\}$ and $\{b_n\}$, then $A(x) \cdot B(x)$ is the EGF for: $c_n = \sum_{k=0}^{n} \binom{n}{k} a_k b_{n-k}$

This accounts for the binomial coefficient arising from choosing which $k$ positions get elements from the first sequence.

The composition $A(B(x))$ where $B(0) = 0$ generates sequences related to tree structures and nested constructions. For OGFs, if $A(x) = \sum a_n x^n$ and $B(x) = \sum b_n x^n$, then: $A(B(x)) = \sum_{n=0}^{\infty} c_n x^n$

where $c_n$ counts weighted paths or compositions.