# Generating Series

Used this in MATH239, was quite confusing at first.

Coefficient extraction, Definition 2.8

Let $G(x)=Pn≥0g_{n}x_{n}$ be a formal power series. For $k∈N$, define $[x_{k}]G(x)=g_{k}$ i.e., $[x_{k}]$ extracts the coefficient of $x_{k}$ in $G(x)$.

Some simple rules about *coefficient extraction*:

- $[x_{k}](aF(x)+bG(x))=a[x_{k}]F(x)+b[x_{k}]G(x)$
- $[x_{k}](x_{ℓ}F(x))=[x_{k−ℓ}]F(x)$
- $[x_{k}](F(x)G(x))=∑_{ℓ=0}([x_{ℓ}]F(x)[x_{k−ℓ}]G(x))$

Weight Function,Definition 2.5

Let $S$ be a set. A weight function is a function $ω:S→N$ if, for every $n∈N$, the number of elements of $S$ of weight n is finite, i.e., ${α∈S:ω(α)=n}$ is finite.

Generating Series, Definition 2.6

Let $S$ be a set and $ω$ be a weight function on $S$. The generating series of $S$ with respect to $ω$ is $Φ_{S}(x)=Φ_{S}(x)=∑_{α∈S}x_{ω(α)}$

Sum Lemma, Lemma 2.10

Let $S_{1},S_{2}$ be disjoint sets and let $ω$ be a weight function on $S_{1}∪S_{2}$. Then $Φ_{S_{1}}(x)+Φ_{S_{2}}(x)=Φ_{S_{1}∪S_{2}}(x)$

Product Lemma, Lemma 2.12

Let $S_{1},S_{2}$ be sets and let $ω_{1}$ and $ω_{2}$ be weight functions on $S_{1}$ and $S_{2}$ respectively. Then $Φ_{S_{1}}(x)Φ_{S_{2}}(x)=Φ_{S_{1}×S_{2}}(x)$

String Lemma, 2.14

Let $A$ be a set with weight function $ω$ such that no elements of $A$ have weight $0$. Then $Φ_{A∗}(x)=1−Φ_{A}(x)1 $