Generating Series

Used this in MATH239, was quite confusing at first.

Coefficient extraction, Definition 2.8

Let $G(x)=Pn\ge 0g_n{x}_n$ be a formal power series. For $k\in \mathbb{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:

1. $[x^k](aF(x)+bG(x))=a[x^k]F(x)+b[x^k]G(x)$
2. $[x^k](x^{\ell }F(x))=[x^{k-\ell }]F(x)$
3. $[x^k](F(x)G(x))={\sum }_{\ell =0}^k([x^{\ell }]F(x)[x^{k-\ell }]G(x))$

Weight Function,Definition 2.5

Let $S$ be a set. A weight function is a function $\omega :S\to \mathbb{N}$ if, for every $n\in \mathbb{N}$, the number of elements of $S$ of weight n is finite, i.e., $\{\alpha \in S:\omega (\alpha )=n\}$ is finite.

Generating Series, Definition 2.6

Let $S$ be a set and $\omega$ be a weight function on $S$. The generating series of $S$ with respect to $\omega$ is ${\Phi }_S^{\omega }(x)={\Phi }_S(x)={\sum }_{\alpha \in S}{x}^{\omega (\alpha )}$

Sum Lemma, Lemma 2.10

Let $S_1,S_2$ be disjoint sets and let $\omega$ be a weight function on $S_1\cup S_2$. Then ${\Phi }_{S_1}(x)+{\Phi }_{S_2}(x)={\Phi }_{S_1\cup S_2}(x)$

Product Lemma, Lemma 2.12

Let $S_1,S_2$ be sets and let ${\omega }_1$ and ${\omega }_2$ be weight functions on $S_1$ and $S_2$ respectively. Then ${\Phi }_{S_1}^{{\omega }_1}(x){\Phi }_{S_2}^{{\omega }_2}(x)={\Phi }_{S_1\times S_2}^{\omega }(x)$

String Lemma, 2.14

Let $A$ be a set with weight function $\omega$ such that no elements of $A$ have weight $0$. Then ${\Phi }_{A\ast }(x)=\frac{1}{1-{\Phi }_A(x)}$