2. Ordinary Generating Functions

2.1Review

普通生成函数是代数组合里最为基础的一种生成函数.

简略地来说, 组合学是一门大部分情况下以解决问题为目标的数学科目, 而生成函数则是代数组合里最为普遍应用的一种方法/思想.

其大致的使用框架是, 如果我们有一个组合对象 $S$(比如说, 图, 树, 集合分拆, 整数分拆, 等等), 然后我们想要计数这一对象, 那么我们就考虑一个配重函数 $w:S\to \mathbb{N}$, 然后我们考虑形式级数 ${\sum }_{s\in S}{x}^{w(s)}$. 举例来说, 比如我们可以考虑所有的整数分拆所组成的组合对象 $\mathcal{P}=\{p:=\{p_1,...,p_k\}:p_i\in \mathbb{N}\}$, 然后考虑 $P(x):={\sum }_{p\in \mathcal{P}}{x}^{w(p)}$, 其中对于 $p=\{p_1,...,p_k\}$ 我们定义 $w(p)={\sum }_{i=1}^k{p}_i$. 那么, 如果我们能够通过代数或者组合的方法, 弄清楚 $P(x)$ 这个形式级数的系数, 比如说 $[x^7]P(x)$, 那么则不难看出, 这个系数 $[x^7]P(x)$ 对应了整数 $7$ 的分拆的数量.

换句话说, 我们如果能够弄清楚 $P(x)$ 的系数, 那么我们就解决了整数分拆的数量这个组合问题.

接下来, 我们将把上述的方法拓展到多元的情况 (也就是下面的 remark). 然后, 我们会考虑各种各样的例子来学习如何使用生成函数解决组合问题.

Remark 2.1.1 (Framework). Let $\alpha$ be a set of combinatorial objects (finite or countably infinite). Let $w_1:\alpha \to \mathbb{N},w_2:\alpha \to \mathbb{N},...$ with $\mathbb{N}=\{0,1,2,...\}$ be one or more weight functions on $\alpha$.

Then the OGF (ordinary generating function) of $\alpha$ (wrt $w_1,w_2,...$) is $$A(x_1,x_2,...)=\sum _{a\in \alpha }\prod _i{x}_i^{w_i(a)}$$In this case, we say variable $x_i$ “marks” the weight function $w_i$. The point is that we have $$Card\{a\in \alpha :w_1(a)=n_1,w_2(a)=n_2,...\}=[x_1^{n_1}{x}_2^{n_2}...]A(x_1,x_2,...)$$

Remark 2.1.2 (OGF Technique).

1.	Figure out relevant set of objects and weight function(s).
2.	Find bijections involving set of objects.
3.	Convert bijections into OGF equations.
4.	Simplify/solve equations.
5.	Extract the answer to your problem.

We remark that, in order to make everything to work, we must have the weight and bijection works together in certain way. In other word, we must have the weight of a composite object should be the sum of the weight of its components, i.e. we need to find weight-preserving bijections.

We will now introduce a series of operations on sets and their OGF correspondence.

Remark 2.1.3. In the following, we will set $\mathcal{A},\mathcal{B}$ be two sets with weight function $w:\mathcal{A}\to \mathbb{N}$ and $w^{\prime }:\mathcal{B}\to \mathbb{N}$ and their OGF are $A(x),B(x)$, respectively. Then we have

1.	(Disjoint Union) If $\mathcal{A}\cup \mathcal{B}$ is disjoint union, then we get a new weight function $w_0$ given by $w_0(s)=w(s)$ if $s\in \mathcal{A}$ and $w_0(s)=w^{\prime }(s)$ if $s\in \mathcal{B}$. Then we have the generating function for $\mathcal{A}\cup \mathcal{B}$ is $A(x)+B(x)$.
2.	(Products) Consider $\mathcal{A}\times \mathcal{B}$ the product of sets. Set $w_0:\mathcal{A}\times \mathcal{B}\to \mathbb{N}$ by $(a,b)\mapsto w(a)+w^{\prime }(b)$ and we have the corresponding OGF for $\mathcal{A}\times \mathcal{B}$ is $A(x)B(x)$.
3.	(Star/Sequence) Consider the set ${\mathcal{A}}^{\ast }={\bigcup }_{k\ge 0}{\mathcal{A}}^k$. Then set $w_0(z_1,z_2,z_3,...)={\sum }_{k\ge 0}w(z_k)$ and we have the generating function for ${\mathcal{A}}^{\ast }$ is $\frac{1}{1-A(x)}$, if it is defined, i.e. we need $A(0)=0$.
4.	(Composition) Consider the set ${\bigcup }_{a\in \mathcal{A}}\{a\}\times {\mathcal{B}}^{w(a)}$. The ideal of composition: imagine $w:\mathcal{A}\to \mathbb{N}$ as the number of widgets, then start with object $a\in \mathcal{A}$ and we replace each widgets by an object in $\mathcal{B}$. We can define two different weights on this set, depends on whether we decide to count the weight of $a$ or not. The first weight function is where $a$ is dewidgetized, and we have $(a,b_1,b_2,...)\mapsto \sum w^{\prime }(b_i)$. In this case we have the OGF is $A(B(x))$. The second weight function is where we still want to take account of the weight of $a$, i.e. we want to make the widgets intact, and we have $(a,b_1,b_2,...)\mapsto \sum w^{\prime }(b_i)+w(a)$. In this case we have the OGF is $A(xB(x))$

Example 2.1.4 (Ordered Rooted Trees). An ordered rooted tree(ORT)/ plane planted tree (PPT) is a rooted tree such that the childrens of any nodes are ordered (as 1st, 2nd,...). Note the order of children matters, and hence the following two trees are not equal:

The first question is, how many ORT with $n$ nodes? We will use OGF to solve it. Let $\mathcal{Q}$ be the collection of all ORTs, then we define the weight function to be the number of nodes, i.e. given $q\in \mathcal{Q}$ we have $w(q)$ equal the number of nodes of $q$.

Next, we need to come up with some bijections. In this case, we see $\mathcal{Q}\iff \{\mathcal{O}\}\times {\mathcal{Q}}^{\ast }$ by sending $q$ to the tuple $(\mathcal{O},q_1,q_2,...,q_k)$ where $q_1,...,q_k$ are ORT that are childrens of $q$ and $\mathcal{O}$ denote the root of $q$. Thus, we see for generating function we get$$Q(x)=x\frac{1}{1-Q(x)}$$Thus use LIFT we get $$[x^n]Q(x)=\frac{1}{n}[{\lambda }^{n-1}]{\left(\frac{1}{1-\lambda }\right)}^n=\frac{1}{n}\left(\genfrac{}{}{0ex}{}{2n-2}{n-1}\right),n\ge 1$$This is the answer for $n\ge 1$.

Example 2.1.5 (Full Binary Trees). We say the updegree of a node equal the number of children of the node. We say a node is terminal if the node has updegree $0$, i.e. it has no child. Then we define a full binary tree (FBT) to be a tree with each node has updegree $0$ or $2$.

So, how many FBTs with $n$ terminals? Let $\mathcal{B}$ be all FBTs and let the weight function to be $w:\mathcal{B}\to \mathbb{N}$ to be $w(b)$ the number of terminals. Then we see (on the second union we are not consider the root node because we are counting the number of terminals and if the root node has two children then it is not a terminal) $$\mathcal{B}\iff \{\mathcal{O}\}\bigcup \mathcal{B}\times \mathcal{B}$$Then we see $B(x)=x+B(x{)}^2\Rightarrow B(x)=\frac{x}{1-B(x)}\Rightarrow [x^n]B(x)=\frac{1}{n}(\genfrac{}{}{0ex}{}{2n-2}{n-1})$.

Example 2.1.6. How many ORTs with $n$ nodes and $k$ terminals?

In this problem we have two parameters. Again let the set be $\mathcal{Q}$ the collection of ORTs. The two weight functions will be $m_1(q)$ equal the number of nodes and $m_2(q)$ the number of terminals.

Then we get $$\mathcal{Q}\iff \{\mathcal{O}\}\cup \{\mathcal{O}\}\times \mathcal{Q}\times {\mathcal{Q}}^{\ast }$$where we note this time on the second set in the union, we have $\mathcal{O}$ has weight $(1,0)$. Thus we get$$Q(x,y)=xy+xQ(x,y)\frac{1}{1-Q(x,y)}$$Now use LIFT we get $$[x^n]Q(x,y)=\frac{1}{n}[{\lambda }^{n-1}](y+\frac{\lambda }{1-\lambda }{)}^n$$Thus immediately extract the coefficient of $y^k$ we get $$\begin{array}{rl}[x^n{y}^k]Q(x,y)& =\frac{1}{n}[{\lambda }^{n-1}][y^k](y+\frac{\lambda }{1-\lambda }{)}^n\\ & =\frac{1}{n}[{\lambda }^{n-1}]\left(\genfrac{}{}{0ex}{}{n}{k}\right)(\frac{\lambda }{1-\lambda }{)}^{n-k}\\ & =\frac{1}{n}[{\lambda }^{k-1}]\left(\genfrac{}{}{0ex}{}{n}{k}\right)(1-\lambda {)}^{-(n-k)}\\ & =\frac{1}{n}\left(\genfrac{}{}{0ex}{}{n}{k}\right)\left(\genfrac{}{}{0ex}{}{n-2}{k-1}\right)\end{array}$$

2.2Partitions

Definition 2.2.1. A partition $\lambda =({\lambda }_1,{\lambda }_2,...,{\lambda }_k)$ is a weakly decreasing sequence of positive integers. The size of $\lambda$ is $|\lambda |={\sum }_{i=1}^k{\lambda }_i$. The length of $\lambda$ is $\ell (\lambda )=k$. The width of $\lambda$ is $width(\lambda )={\lambda }_1$.

Example 2.2.2 (Counting Partitions by Size). Let $\mathcal{P}$ be the set of all partitions, let weight function on $\mathcal{P}$ be the size of $\lambda \in \mathcal{P}$, i.e. $m(\lambda )=|\lambda |$. Then we want to compute OGF $P(\lambda )$. To this end, consider $${\mathcal{P}}_k:=\{\lambda \in \mathcal{P}:width(\lambda )\le k\}$$Then we see$${\mathcal{P}}_k\iff \{k{\}}^{\ast }\times \{k-1{\}}^{\ast }\times ...\times \{1{\}}^{\ast }$$and hence$$P_k(x)=\frac{1}{1-x^k}\frac{1}{1-x^{k-1}}...\frac{1}{1-x}$$However, we note $P(x)={\lim }_{k\to \infty }{P}_k(x)={\prod }_{i=1}^{\infty }\frac{1}{1-x^i}$ and hence$$[x^n]P(x)=[x^n]\prod _{i=1}^{\infty }\frac{1}{1-x^i}$$

Example 2.2.3 (Counting Partitions by Size and Length). Let $\mathcal{P}$ be the set of all partitions, let $w_1(\lambda )=|\lambda |$ and $w_2(\lambda )=\ell (\lambda )$. Then we get$$P_k(x,y)=\prod _{i=1}^k\frac{1}{1-x^{i}y}$$with a similar bijection as before. Thus we see$$P(x,y)=\prod _{i=1}^{\infty }{P}_k(x,y)=\prod _{i=1}^{\infty }\frac{1}{1-x^{i}y}$$

Example 2.2.4 (“At most” vs “Exactly”). The number of partitions of size $n$, length $l$ and width $k$ is equal to $$[x^n{y}^l](P_k(x,y)-P_{k-1}(x,y))$$On the other hand, the number of partitions with size $n$, length less than or equal $l$, and width less than or equal $k$ is equal to $$[x^n{y}^l]\frac{1}{1-y}P(x,y)=[x^n{y}^l]\prod _{i=0}^k\frac{1}{1-x^{i}y}$$

Example 2.2.5. Let $P_{k,l}=\{\lambda \in \mathcal{P}:\ell (\lambda )\le l,width(\lambda )\le k\}$. Then $|{\mathcal{P}}_{k,l}|=\left(\genfrac{}{}{0ex}{}{k+l}{k}\right)$ by consider the paths from $(0,0)$ to $(k,l)$ in ${\mathbb{R}}^2$.

Now we recall the $q$-analogous of binomial coefficients $${\left(\genfrac{}{}{0ex}{}{k+l}{l}\right)}_q=\prod _{i=1}^{\infty }\frac{q^{l+i}-1}{q^i-1}$$where those are called $q$-binomial coefficients. In particular we have a theorem says that $$P_{k,l}(q)={\left(\genfrac{}{}{0ex}{}{k+l}{k}\right)}_q$$To prove this, consider ${\sum }_{l\ge 0}{P}_{k,l}(q)y^l={\prod }_{i=0}^k\frac{1}{1-q^{i}y}$, which is by the above example. Thus it suffices to show$$\sum _{k\ge 0}\left(\genfrac{}{}{0ex}{}{k+l}{k}\right)y^l=\prod _{i=0}^k\frac{1}{1-q^{i}y}$$and this can be done by induction on $k$.

Theorem 2.2.6 (Euler’s Pentagonal Number Theorem). For $k\in \mathbb{Z}$, let $g_k=\frac{1}{2}k(3k+1)$. Then $P(x{)}^{-1}={\sum }_{k\in \mathbb{Z}}(-1{)}^k{x}^{g_k}$

Corollary 2.2.7. $p(n)={\sum }_{k\ne 0}(-1{)}^{k}p(n-g_k)$, where $p(x)$ is the number of partitions of $x$.

Proof. Note $P(x)P^{-1}(x)=1$ we see $[x^n]P(x)P^{-1}(x)=0$ for $n\ge 1$ and hence $[x^n]\left({\sum }_{n\ge 0}p(n)x^n\right)\left({\sum }_{k\in \mathbb{Z}}(-1{)}^k{x}^{g_k}\right)=0$. Now expand the left hand side and extract coefficients we get the result.

$\square$

Example 2.2.8. Compute the number of $01$-strings of length $n$ such that $011$ is not a substring.

Let $\mathcal{A}=\{012-\text{strings where }011\text{ is not a substring}\}$. We will define $3$ weight functions, $w_0,w_1,w_2$ given by $w_i(\sigma )$ equal the number of $i$ in $\sigma$. Then the OGF $A(x_0,x_1,x_2)$ is given by $$A(x_0,x_1,x_2)=\sum _{\sigma \in \mathcal{A}}{x}_0^{w_0(\sigma )}{x}_1^{w_1(\sigma )}{x}_2^{w_2(\sigma )}$$Then note$$A(x,x,0)=\sum _{\sigma \in \mathcal{A}}=\sum _{\begin{array}{c}\sigma \in \mathcal{A}\\ w_2(\sigma )=0\end{array}}{x}^{w_0(\sigma )+w_1(\sigma )}$$where we see $\sigma \in \mathcal{A}$ with $w_2(\sigma )=0$ are exactly $01$-strings without $011$ as a substring. Hence the answer of our question is $[x^n]A(x,x,0)$.

To compute $A(x_0,x_1,x_2)$, we use composition of $\mathcal{A}$ with $\mathcal{B}=\{2,011\}$. Elements are then constructed as follows: for each $\sigma \in \mathcal{A}$, replace each $2$ in $\sigma$ by some string in $\mathcal{B}$. E.g. $\sigma =2020$ then we have four strings we can construct by replacing elements from $\mathcal{B}$, namely $2020,200110,011020,01100110$.

Then the result of such construction is equal to $\{0,1,2{\}}^{\ast }$, i.e. all $012$-strings, as we can do this construction backwards as well. Thus we get $$A(x_0,x_1,B(x_0,x_1,x_2))=\frac{1}{1-(x_0+x_1+x_2)}$$where we see$$B(x_0,x_1,x_2)=x_2+x_0{x}_1^2$$and hence $$A(x_0,x_1,x_2+x_0{x}_1^2)=\frac{1}{1-(x_0+x_1+x_2)}\Rightarrow A(x_0,x_1,x_2)=\frac{1}{1-(x_0+x_1+x_2-x_0{x}_1^2)}$$

2.3Transfer Matrix Method

Example 2.3.1. Let $G$ be a directed graph, allow loops and parallel edges. Let any $u,v\in E$ we let:

1.	${\mathcal{A}}_{u,v}=\{\text{set of edges }u\to v\}$.
2.	${\mathcal{T}}_{u,v}=\{\text{all walks }u\to v\}$.
3.	${\mathcal{T}}_{u,v}^{(n)}=\{\text{all walks }u\to v\text{ with length }n\}$.
4.	${\mathcal{T}}_u:=\{\text{all walks starting at }u\}$.

Then the TMM (transfer matrix method) theory is as follows: we assign a weight to each edge, say $e\mapsto wt(e)$. Then we obtain a generating function $A_{u,v}(x)={\sum }_{e\in {\mathcal{A}}_{u,v}}{x}^{w(e)}$. Since for each $u,v$ we have $A_{u,v}$, we get a matrix $A(x)$ with entries $\mathbb{Q}[[x]]$(or $\mathbb{Q}((x))$), just like we can get adjacency matrix from $G$.

For a walk $w$, we let the weight function to be $w\mapsto {\sum }_{\text{edges }e\text{ of }w}wt(e)$. Then we have the following propositions.

Proposition 2.3.2. Use the notation as above, we have

1.	$T_{u,v}^{(n)}(x)=(A(x{)}^n{)}_{uv}$ where for a matrix we use $A_{ab}$ to denote the entry at $ab$ place.
2.	$T_{u,v}(x)=((I-A(x){)}^{-1}{)}_{uv}$.
3.	$T_u(x)$ equal the $u$-component of $T(x)$, where $T(x)$ is the solution to $(I-A(x))T(x)=1$ where $1$ is a vector.

Remark 2.3.3. The above proposition will work out nicely, provided $A(0)$ is nilpotent matrix.

Proof. Statement $(1)$ is by induction on $n$. Statement $(2)$ we note we have $T_{u,v}(x)={\sum }_{n\ge 0}{T}_{u,v}^{(n)}(x)={\left({\sum }_{n\ge 0}A(x{)}^n\right)}_{uv}$ where if we assume $A(0)$ nilpotent then it always converges. In particular note $\sum A(x{)}^n$ is geometric series and hence we are done. For $(3)$ we note $T_u(x)={\sum }_v{T}_{u,v}(x)$ and hence by basic linear algebra we are done.

$\square$

Example 2.3.4 (TMM in Practice). We can use TMM in practice, when:

1.	Our objects are build up recursively.
2.	The options in recursive construction depends on cases.
3.	Vertices correspond to cases.
4.	Edges correspond to construction options.
5.	Walks correspond to objects(we have to be very careful to make sure this is a bijection). Also we make to make sure this bijection is weight-preserving.

Example 2.3.5. Let $\mathcal{S}:=\{012-\text{strings},\text{ no }3\text{ consecutive letters all different}\}$. For example, $01020\notin \mathcal{S}$ and $01121\in \mathcal{S}$. Then consider the weight function to be the length of the string. Compute $S(x)$.

We have three different cases:

1.	Case 1: the empty string.
2.	Case 2: string $x$ with length $1$ or $-xx$, i.e. strings end with the same letter twice.
3.	Case 3: string $-xy$, i.e. at least length $2$ and end with different letters.

Then we get the construction of $\mathcal{S}$ is the following graphThen we get a bijection $\mathcal{S}$ and ${\mathcal{T}}_1$. Hence we get$$A(x)=\left[\begin{array}{ccc}0& 3x& 0\\ 0& x& 2x\\ 0& x& x\end{array}\right]$$and so$$S(x)=T_1(x)=\frac{\det \left(\left[\begin{array}{ccc}1& -3x& 0\\ 1& 1-x& -2x\\ 1& -x& 1-x\end{array}\right]\right)}{\det (I-A(x))}=\frac{1+x+2x^2}{1-2x-x^2}$$