Formal Power Series and Operations

Formal power series provide an algebraic framework for generating functions, allowing manipulations without convergence concerns. The ring structure supports powerful techniques including composition, inversion, and extraction of coefficients.

DefinitionFormal Power Series Ring

The set $R[[x]]$ of formal power series over a ring $R$ consists of infinite sequences $(a_0, a_1, a_2, \ldots)$ written as: $A(x) = \sum_{n=0}^\infty a_n x^n$

where $a_n \in R$ . Unlike analytic power series, convergence is not required—these are purely algebraic objects. The ring operations are:

Addition: $(A + B)(x) = \sum_{n=0}^\infty (a_n + b_n) x^n$
Multiplication: $(AB)(x) = \sum_{n=0}^\infty c_n x^n$ where $c_n = \sum_{k=0}^n a_k b_{n-k}$ (Cauchy product)
Scalar multiplication: $(rA)(x) = \sum_{n=0}^\infty (ra_n) x^n$ for $r \in R$

DefinitionMultiplicative Inverse

A formal power series $A(x) = \sum_{n=0}^\infty a_n x^n$ has a multiplicative inverse in $R[[x]]$ if and only if $a_0$ is a unit in $R$ . When $R$ is a field and $a_0 \neq 0$ , we can compute: $\frac{1}{A(x)} = \frac{1}{a_0} \cdot \frac{1}{1 - (1 - A(x)/a_0)} = \frac{1}{a_0} \sum_{k=0}^\infty \left(\frac{a_0 - A(x)}{a_0}\right)^k$

For example, $\frac{1}{1-x-x^2}$ can be computed by treating it as $\frac{1}{1-(x+x^2)}$ and expanding geometrically.

ExampleComputing Fibonacci Numbers

The Fibonacci generating function satisfies: $F(x) = \frac{x}{1-x-x^2}$

To find coefficients, use partial fractions. Factor the denominator: $1 - x - x^2 = -(x - \phi)(x - \hat{\phi})$ where $\phi = \frac{1+\sqrt{5}}{2}$ and $\hat{\phi} = \frac{1-\sqrt{5}}{2}$ .

Then: $F(x) = \frac{x}{1-x-x^2} = \frac{1}{\sqrt{5}}\left(\frac{1}{1-\phi x} - \frac{1}{1-\hat{\phi} x}\right) = \frac{1}{\sqrt{5}}\sum_{n=0}^\infty (\phi^n - \hat{\phi}^n) x^n$

Thus $F_n = \frac{\phi^n - \hat{\phi}^n}{\sqrt{5}}$ .

DefinitionComposition of Series

For formal power series $A(x)$ and $B(x)$ with $B(0) = 0$ (constant term zero), the composition $A(B(x))$ is well-defined: $A(B(x)) = \sum_{n=0}^\infty a_n [B(x)]^n$

The condition $B(0) = 0$ ensures that each coefficient in the composition involves only finitely many terms. This operation corresponds to substituting one combinatorial structure into another.

ExampleSpecies Composition

The species of binary trees $T(x)$ satisfies $T(x) = x(1 + T(x))^2$ , which can be written as: $T(x) = x + 2xT(x) + xT(x)^2$

This is a quadratic equation in $T(x)$ giving: $T(x) = \frac{1 - 2x - \sqrt{1-4x}}{2x}$

The coefficient $[x^n]T(x)$ gives the Catalan number $C_{n-1}$ .

DefinitionLagrange Inversion Formula

If $A(x) = x\phi(A(x))$ where $\phi$ is a formal power series with $\phi(0) \neq 0$ , then: $[x^n]A(x) = \frac{1}{n}[t^{n-1}]\phi(t)^n$

This powerful formula solves implicit functional equations. It's the cornerstone for analyzing tree enumeration and many recursive structures.

Remark

The coefficient extraction operator $[x^n]$ satisfies:

$[x^n](A(x) + B(x)) = [x^n]A(x) + [x^n]B(x)$ (linearity)
$[x^n](x^k A(x)) = [x^{n-k}]A(x)$ (shift property)
$[x^n](A(x)B(x)) = \sum_{k=0}^n ([x^k]A(x))([x^{n-k}]B(x))$ (convolution)
$[x^n]A'(x) = (n+1)[x^{n+1}]A(x)$ (differentiation)

These operations form the algebra of combinatorial enumeration.

ExampleAdvanced Coefficient Extraction

To find $[x^n]\frac{1}{(1-x)^k}$ : $\frac{1}{(1-x)^k} = \left(\sum_{m=0}^\infty x^m\right)^k$

Using the multinomial theorem or stars-and-bars: $[x^n]\frac{1}{(1-x)^k} = \binom{n+k-1}{k-1} = \binom{n+k-1}{n}$

This counts ways to place $n$ indistinguishable balls into $k$ distinguishable bins.

DefinitionDirichlet Series and Convolution

A Dirichlet series is a formal series of the form: $D(s) = \sum_{n=1}^\infty \frac{a_n}{n^s}$

The Dirichlet convolution of sequences $\{a_n\}$ and $\{b_n\}$ is: $(a * b)(n) = \sum_{d|n} a_d b_{n/d}$

This appears in multiplicative number theory, where the Riemann zeta function $\zeta(s) = \sum_{n=1}^\infty n^{-s}$ plays a central role.

Formal power series techniques unify algebraic and combinatorial reasoning, providing a powerful toolkit for solving enumeration problems across mathematics.