1. Formal Power Series

1.1基本定义

这一章节我们主要复习/学习一些后面会用到的关于形式级数的概念. 这在代数组合里面是最为基本的一个概念, 因为其给生成函数提供了一个坚实的理论基础.

从下面的定义中不难看出, 其和分析中的级数的区别在于我们并不把这些无穷和考虑为某一类映射到一个环中的函数, 而只是一种用来记载系数的代数对象.

然而, 在分析组合学中, 我们会把这些原本只是形式上的级数当成是具有收敛意义的 (复) 级数, 然后用分析的方法来学习一些组合对象在极限下的行为.

Definition 1.1.1. 考虑整环 $R$, 我们定义 形式级数环为如下环$$R[[x]]:=\{\sum _{n\ge 0}{a}_i{x}^i:a_i\in R\}$$

Proposition 1.1.2. 如果 $R$ 是整环, 则 $R[[x]]$ 也是整环.

Proof. 习题.

$\square$

Definition 1.1.3. 在形式级数环上我们定义如下操作:

1.	$\frac{A(x)}{B(x)}:=C(x)$, 如果 $A(x)=B(x)C(x)$.
2.	$[x^n]A(x):=a_n$ 如果 $A(x)={\sum }_{i\ge 0}{a}_i{x}^i$.
3.	我们定义形式级数环上的赋值 ${\mathrm{V}\mathrm{a}\mathrm{l}}_x(A)$ 为: $${\mathrm{V}\mathrm{a}\mathrm{l}}_x(A):=\{\begin{array}{l}0\text{，如果}A(x)=0\\ \min \{m:[x^m]A(x)\ne 0\}\text{，其他情况}\end{array}$$

一些显然的性质有:

1.	${\mathrm{V}\mathrm{a}\mathrm{l}}_x(A+B)\ge \min \{{\mathrm{V}\mathrm{a}\mathrm{l}}_x(A),{\mathrm{V}\mathrm{a}\mathrm{l}}_x(B)\}$.
2.	${\mathrm{V}\mathrm{a}\mathrm{l}}_x(AB)={\mathrm{V}\mathrm{a}\mathrm{l}}_x(A)+{\mathrm{V}\mathrm{a}\mathrm{l}}_x(B)$.

使用这个赋值, 我们可以证明 $R[[x]]$ 是一个离散赋值环.

同时, 固定任意一个 $0<ϵ<1$, 我们可以定义出 $R[[x]]$ 上的一个度量空间, 其中$$d_{ϵ}(A(x),B(x)):={ϵ}^{{\mathrm{V}\mathrm{a}\mathrm{l}}_x(A-B)}$$

用上述拓扑我们可以定义形式级数的无穷和与无穷乘积.

在一些情况下, 我们会考虑多元形式级数 $R[[x]][[y]]=R[[y]][[x]]$, 不过我们需要小心的是, 根据定义来说, $R[[x]][[y]]$ 用的是 ${\mathrm{V}\mathrm{a}\mathrm{l}}_y$ 诱导出来的拓扑, 而 $R[[y]][[x]]$ 使用的是 ${\mathrm{V}\mathrm{a}\mathrm{l}}_x$ 诱导的拓扑, 而这两个拓扑并不等价. 在这一情况下, 我们可以使用另一个赋值, ${\mathrm{V}\mathrm{a}\mathrm{l}}_{x,y}(A):=\min m+n:[x^m{y}^n]A(x,y)\ne 0$, 或者等于 $\infty$ 如果 $A(x,y)=0$.

Definition 1.1.4. 定义 $R[[x]{]}_{+}$ 为$$R[[x]{]}_{+}:=\{A(x)\in R[[x]]:[x^0]A(x)=0\}$$对于 $A(x)\in R[[x]]$ 定义$$A_{+}(x):=A(x)-[x^0]A(x)\in R[[x]{]}_{+}$$

Definition 1.1.5. 给定 $A(x),B(x)\in R[[x]]$, 我们有:

1.	$A(B(x)):={\sum }_{n\ge 0}{a}_{n}B(x{)}^n$.
2.	如果 $A(B(x))=B(A(x))=x$, 那么我们把 $A(x),B(x)\in R[[x]]$ 称之为复合逆.

Proposition 1.1.6. $A(B(x))$ 是良定义的当且仅当 $A(x)\in R[x]$ 或者 $B(x)\in R[[x]{]}_{+}$. 也就是说, 其是良定义的当且仅当 $A(x)$ 是多项式, 或者 $B(x)$ 没有常数项.

Proposition 1.1.7. 对于 $B(x)\in R[[x]{]}_{+}$, 定义求值映射 ${\mathrm{e}\mathrm{v}}_B:R[[x]]\to R[[x]]$ 为 ${\mathrm{e}\mathrm{v}}_B(A(x))=A(B(x))$. 这一求值映射 ${\mathrm{e}\mathrm{v}}_B$ 是环同态

Proposition 1.1.8. 对于 $A(x),B(x)\in R[[x]]$, 如果 $A(B(x))=x$ 则 $B(A(x))=x$.

Proof. Note $A(B(x))=x$, we see we can apply $B$ to both side and get $B(A(B(x)))=B(x)$. On the other hand, note if $B(A(x))=x$ then we can apply $e{v}_B$ to both side and get $B(A(B(x)))=B(x)$, but $e{v}_B$ is injective, which forces us to have $B(A(x))=x$.

$\square$

Proposition 1.1.9. $A(x)$ 在 $R[[x]]$ 中可逆当且仅当 $a_0$ 在 $R$ 中可逆.

Proof. $(\Rightarrow )$: exercise.

$(\Leftarrow )$: Consider $G(x)={\sum }_{n\ge 0}(-1{)}^n{a}_0^{-n-1}{x}^n$. Then we see $(a_0+x)G(x)=1$ and now apply $e{v}_{A_{+}}$ to both side of the equation and we get $(a_0+A_{+}(x))G(A_{+}(x))=1$, where $a_0+A_{+}(x)=A(x)$ and hence we are done, i.e. $G(A_{+}(x))$ is the inverse of $A(x)$.

$\square$

Definition 1.1.10. 对于 $A(x)\in R[[x]]$ 我们定义:

1.	形式导数为 $\frac{d}{dx}A(x)=A^{\prime }(x)={\sum }_{n\ge 0}n{a}_n{x}^{n-1}$.
2.	如果 $\mathbb{Q}\subseteq R$ 则定义形式积分为 ${\int }_{x}A(x)={\sum }_{n\ge 0}\frac{a_n}{n+1}{x}^{n+1}$.

Proposition 1.1.11.

1.	$\frac{d}{dx}(A(x)+cB(x))=A^{\prime }(x)+c{B}^{\prime }(x)$, 其中 $c\in R$.
2.	$\frac{d}{dx}(A(x)B(x))=A^{\prime }(x)B(x)+A(x)B^{\prime }(x)$.
3.	$\frac{d}{dx}A(B(x))=A^{\prime }(B(x))B^{\prime }(x)$ 如果复合是良定义的.

Example 1.1.12. 在下属例子中我们考虑一些特殊的形式级数:

1.	$\exp (x)=e^x:={\sum }_{n\ge 0}\frac{1}{n!}{x}^n\in \mathbb{Q}[[x]]$. 其一些性质如下: 1. $\exp (x+y)=\exp (x)+\exp (y)$ 2. $\frac{d}{dx}\exp (x)=\exp (x)$
2.	$L(x):={\sum }_{n\ge 1}\frac{(-1{)}^{n-1}}{n}{x}^n\in \mathbb{Q}[[x]]$. 其一些性质如下: 1. $L(x)$ 是 ${\exp }_{+}(x)$ 的复合逆. 2. $L(\frac{x}{1-x})=-L(-x)={\sum }_{n\ge 1}\frac{1}{n}{x}^n$. 这是 $1-e^{-x}$ 的复合逆. 3. $L(x+y+xy)=L(x)+L(y)$. 4. $\frac{d}{dx}L(x)=\frac{1}{1+x}$ 显然这就是微积分意义上的 $\log (1+x)$ 函数, 所以我们也会时不时地这样写.
3.	$B(x,y)={\sum }_{n\ge 0}\left(\genfrac{}{}{0ex}{}{y}{n}\right)x^n\in \mathbb{Q}[y][[x]]$. 其一些性质如下: 1. $B(x,y)B(x,z)=B(x,y+z)$. 2. $\frac{\partial }{\partial x}B(x,y)=yB(x,y-1)$. 3. $B(x,y)=\exp (y\log (1+x))$. 显然这个在日常生活中等于 $B(x,y)=(1+x{)}^y$.

Lemma 1.1.13 (Hensel 引理). 给定 $F(x,t)\in R[[t,x]]$, 定义 $F^{\prime }(t,x):=\frac{\partial }{\partial x}F(t,x)$. 假设 $F(0,0)=0,F^{\prime }(0,0)\in R^{\ast }:=\{r\in R:\exists u\in R,ru=ur=1\}$. 则存在一个独特的 $f(t)\in R[[t]{]}_{+}$ 使得 $F(t,f(t))=0$.

Remark 1.1.14. Two key ideas for the proof here:

1.	Linear approximation: for any $A(x)\in R[[x]]$, we have $A(u)=A(v)+(u-v)A^{\prime }(v)(\mathrm{m}\mathrm{o}\mathrm{d}(u-v{)}^2)$.
2.	Newton’s method: we will construct $f_0(t)=0$, then $f_{n+1}(t)=f_n(t)-\frac{F(t,f_n(t))}{F^{\prime }(t,f_n(t))}$ and we take the limit to define $f(t)={\lim }_{n\to \infty }{f}_n(t)$. Then we use linear approximation to prove the limit exists.

Now we give the detailed proof of Hensel’s lemma.

Proof. Existence: let $f_0(t)=0$, $f_{n+1}(t)=f_n(t)-\frac{F(t,f_n(t))}{F^{\prime }(t,f_n(t))}$. By induction, $f_n(t)\in R[[t]{]}_{+}$ for all $n$, hence the right hand side is defined. Now apply the linear approximation with $A(x)=F(t,x)$, $u=f_n(t),v=f_{n-1}(t)$ we get$$F(t,f_n(t))=F(t,t_{n-1}(t))+(f_n(t)-f_{n-1}(t))F^{\prime }(t,f_{n-1}(t))(\mathrm{m}\mathrm{o}\mathrm{d}(f_n(t)-f_{n-1}(t){)}^2)$$Thus we see $F(t,f_{n+1}(t))$ is divisible by $(f_n(t)-f_{n-1}(t){)}^2$.

On the other hand, since $F^{\prime }(t,f_n(t))$ is invertible, from the definition of $f_n$ we see$$f_{n+1}(t)-f_n(t)$$is divisible by $F(t,f_n(t))$. Thus we see$${\mathrm{V}\mathrm{a}\mathrm{l}}_t(f_n(t)-f_{n-1}(t))\le 2{\mathrm{V}\mathrm{a}\mathrm{l}}_{t}F(t,f_n(t))\le 2{\mathrm{V}\mathrm{a}\mathrm{l}}_t(f_{n+1}(t)-f_n(t))$$and hence ${\lim }_{n\to \infty }{\mathrm{V}\mathrm{a}\mathrm{l}}_t(f_{n+1}(t)-f_n(t))=\infty$ and thus $f(t)={\lim }_{n\to \infty }{f}_n(t)={\sum }_{n\ge 0}(f_{n+1}(t)-f_n(t))$ exists. Now take limit of the defining equation of $f_n$, we get$$\underset{n\to \infty }{\lim }{f}_{n+1}(t)=\underset{n\to \infty }{\lim }{f}_n(t)-\frac{F(t,f_n(t))}{F^{\prime }(t,f_n(t))}$$$$f(t)=f(t)-\frac{F(t,f(t))}{F^{\prime }(t,f(t))}$$where $F^{\prime }(t,f(t))\ne 0$ and hence $F(t,f(t))=0$ as desired.

Uniqueness: Suppose $F(t,f(t))=F(t,g(t))=0$. Apply linear approximation with $A(x)=F(t,x)$ and $u=g(t),v=f(t)$ we get$$F(t,g(t))=F(t,f(t))+(g(t)-f(t))F^{\prime }(t,f(t))(\mathrm{m}\mathrm{o}\mathrm{d}(g(t)-f(t){)}^2)$$and hence $g(t)-f(t)$ is divisible by $(g(t)-f(t){)}^2$. Since $g(t)-f(t)$ is not a unit in $R[[t]]$ we must have $g(t)-f(t)=0$ and the proof follows.

$\square$

如下是两个 Hensel 引理的应用.

Proposition 1.1.15. $A(x)\in R[[x]{]}_{+}$ 有复合逆当且仅当 $[x^{\prime }]A(x)$ 在 $R$ 中可逆.

Proof. $(\Rightarrow )$: Exercise.

$(\Leftarrow )$: Let $F(x,\lambda )=x-A(\lambda )$ and $F^{\prime }(x,\lambda )=\frac{\partial }{\partial \lambda }F(x,\lambda )$. Then $F(0,0)=0-A(0)=0$ and $F^{\prime }(0,0)=A^{\prime }(0)$ by definition is invertible. Now by Hensel’s lemma we can find $B(\lambda )\in R[[x]{]}_{+}$ such that $F(x,B(x))=0=x-A(B(x))$ as desired.

$\square$

Proposition 1.1.16. 如果 $F$ 是一个 $Char(F)$ 不等于 2 的域. 则 $\sqrt{A(x)}\in F[[x]]$ 当且仅当 ${\mathrm{V}\mathrm{a}\mathrm{l}}_{x}A(x)=2m$, 并且 $[x^m]A(x)$ 是一个平方.

Proof. $(\Rightarrow )$: Exercise.

$(\Leftarrow )$: Write $A(x)=a^2{x}^{2m}+\text{ higher terms}$. Let $F(x,y)=(1+y{)}^2-\frac{A(x)}{a^2{x}^{2m}}$. Then we see $F^{\prime }(x,y):=\frac{\partial }{\partial y}F(x,y)=2(1+y)$. Then $F(0,0)=0$ and $F^{\prime }(0,0)=2$ and so we can use Hensel’s lemma and get $f(x)\in F[[x]{]}_{+}$ such that $F(x,f(x))=0$ and hence $a^2{x}^{2m}(1+f(x){)}^2=A(x)$, i.e. $a{x}^m(1+f(x))$ is a square root of $A(x)$ as desired.

$\square$

1.2形式洛朗级数

在上一章中我们定义了形式级数环, 不过这一套理论并不足够普遍, 以至于我们出门买菜都没法使用它和店主讨价还价. 举例来说, 在 $\mathbb{Q}[[x]]$ 里我们甚至没法定义 $\frac{e^x}{x}$.

既然吃啥补啥, 缺啥修啥, 一个最直观的修补方法是使得我们允许在整个 $\mathbb{Z}$ 上的求和, 而不是只在 ${\mathbb{Z}}_{\ge 0}$ 上求和. 不过根据” 编程第一定理 “ (如果一个东西没有 bug 则不要碰那段 code! ) , 在这新的定义下我们立马得出如下一个例子$$\sum _{n\in \mathbb{Z}}{x}^n=\sum _{n\ge 0}{x}^n+\sum _{n\ge 0}{x}^{-n-1}=\frac{1}{1-x}+\frac{x^{-1}}{1-x^{-1}}=0$$所以我们需要退一步海阔天空, 从而得出下述的定义.

Definition 1.2.1. 定义形式洛朗级数环 $R((x))$ 为$$R((x))=\{\sum _{n\ge N}{a}_n{x}^n:N\in \mathbb{Z},a_n\in R\}$$

之前定义的所有操作, 譬如提取系数, 形式求导, 极限, 都是依然良好定义的. 形式积分存在当且仅当 $[x^{-1}]A(x)=0$.

Definition 1.2.2. 我们定义两个洛朗级数之间的复合如下:$$A(B(x)):=\sum _{n\ge N}{a}_{n}B(x{)}^n$$

Definition 1.2.3. 对于 $A(x)\in R((x))$, 定义形式留数为 $[x^{-1}]A(x)$.

Proposition 1.2.4.

1.	$[x^{-1}](A(x)+cB(x))=[x^{-1}]A(x)+c[x^{-1}]B(x)$, 其中 $c\in R$.
2.	$[x^{-1}]A^{\prime }(x)=0$. 这是微积分基本定理的类比.
3.	$[x^{-1}]A^{\prime }(x)B(x)=-[x^{-1}]A(x)B^{\prime }(x)$. 这是分步积分的类比.
4.	$[x^{-1}]A(x)=\frac{1}{{\mathrm{V}\mathrm{a}\mathrm{l}}_y(B(y))}[y^{-1}]A(B(y))B^{\prime }(y)$. 这是换元积分的类比.

作为环, $R[[x]][[y]]\cong R[[y]][[x]]$, 但是对于形式洛朗级数这是错误的, 所以我们一般需要选择一个顺序. 举例来说, 考虑 $(x+y{)}^{-1}$. 在 $\mathbb{Q}((x))((y))$ 中我们有 $(x+y{)}^{-1}={\sum }_{n\ge 0}{x}^{-n-1}{y}^n$. 而在 $\mathbb{Q}((y))((x))$ 里我们有 $(x+y{)}^{-1}={\sum }_{n\ge 0}{y}^{-n-1}{x}^n$. 这两个表达式显然并不相等.

Theorem 1.2.5 (拉格朗日隐函数定理 (LIFT)). 假设 $\mathbb{Q}\subseteq R$, 并且 $\varphi (\lambda )\in R[[\lambda ]]$ 是可逆的, 则:

1.	存在独特的 $A(x)\in R[[x]{]}_{+}$ 使得 $A(x)=x\varphi (A(x))$. This equation is called the LIFT equation.
2.	对所有 $n\ge 1$, $[x^n]A(x)=\frac{1}{n}[{\lambda }^{n-1}]\varphi (\lambda {)}^n$
3.	对于任意 $f(\lambda )\in R((\lambda ))$ 和 $n>0$, 我们有$$[x^n]f(A(x))=\frac{1}{n}[{\lambda }^{n-1}]f^{\prime }(\lambda )\varphi (\lambda {)}^n$$对于 $n=0$ 我们有$$[x^0]f(A(x))=[{\lambda }^0]f(\lambda )+[{\lambda }^{-1}]f^{\prime }(\lambda )\log (\frac{\varphi (\lambda )}{\varphi (0)})$$where the second term is zero when ${\mathrm{V}\mathrm{a}\mathrm{l}}_{\lambda }f(\lambda )\ge 0$.

Theorem 1.2.6 (拉格朗日隐函数定理 (版本二)). 对于 $\varphi (\lambda ),f(\lambda )\in \mathbb{Q}[[\lambda ]]$ 和 $A(x)\in \mathbb{Q}[[x]{]}_{+}$, 假设 $\varphi (\lambda )$ 是可逆的, 并且 $A(x)=x\varphi (A(x))$. 那么对于所有 $n\ge 0$, 我们有$$[x^n]f(A(x))=[{\lambda }^n]f(\lambda )\left(1-\lambda \frac{{\varphi }^{\prime }(\lambda )}{\varphi (\lambda )}\right)\varphi (\lambda {)}^n$$

Example 1.2.7. 我们使用 LIFT 计算斐波那契数列的通项公式.

设 $f_0=1,f_1=1$, 并且 $f_n=f_{n-1}+f_{n-2}$. 定义 $F(x)={\sum }_{n\ge 0}{f}_n{x}^n$. 根据 $f_i$ 的性质我们注意到有 $F(x)=x(1+F(x)+xF(x))=x+xF(x)+x^{2}F(x)$. 在这时我们可以直接求出 $F(x)$ 的表达式, 也就是 $F(x)=\frac{x}{1-x-x^2}$, 然后使用部分分式的技巧求解.

但是我们也可以使用 LIFT 来解决这一问题. 考虑 $G(x,y)\in \mathbb{Q}[[x]][[y]]$, 使得其满足 $G(x,y)=x(1+G(x,y)+yG(x,y))$, 其中我们有 $\varphi (\lambda ):=1+\lambda +y\lambda \in \mathbb{Q}[[y]][[\lambda ]]$. 于是我们有$$G(x,y)=x\varphi (G(x,y))$$首先注意我们有 $F(x)=G(x,x)$. 现在对 $G(x)\in R[[x]]$ 和 $\varphi (\lambda )\in R[[\lambda ]]$ 使用 LIFT, 其中 $R=\mathbb{Q}[[y]]$, 我们有$$[x^n]G(x)=\frac{1}{n}[{\lambda }^{n-1}]\varphi (\lambda {)}^n=\frac{1}{n}[{\lambda }^{n-1}](1+\lambda +y\lambda {)}^n$$其中我们注意到$$(1+(1+y)\lambda {)}^n=\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})(1+y{)}^i{\lambda }^i\Rightarrow [{\lambda }^{n-1}]\varphi (\lambda {)}^n=(\genfrac{}{}{0ex}{}{n}{n-1})(1+y{)}^{n-1}$$于是$$[x^n]G(x)=(1+y{)}^{n-1}\Rightarrow G(x)=\sum _{n\ge 1}(1+y{)}^{n-1}{x}^n\Rightarrow G(x,x)=\sum _{n\ge 1}(1+x{)}^{n-1}{x}^n$$于是我们得到$$[x^n]F(x)=\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n-k-1}{k}\right)$$值得注意的是, 通过 LIFT 所求出来的通项公式与使用部分分数所求出的通项公式并不一样, 于是我们得到如下 (十分显然的) 代数恒等式$$\frac{{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n}{\sqrt{5}}=\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n-k-1}{k}\right)$$

Example 1.2.8 (习题). 假设 $A(x)=x{e}^{A(x)}$, 计算 $A(x)$.

Example 1.2.9. 找到一个满足关系式 $x{B}^3-B+y=0$ 的形式级数 $B=B(x,y)\in \mathbb{Q}[[x,y]]$.

改写上述式子为如下式子 $x=\frac{B-t}{B^3}$, 接下来使用 $A=B-y$ 换元, 我们得到 $A=x(A+y{)}^3$. 现在使用 LIFT, 其中 $R=\mathbb{Q}[[y]]$, $\varphi (\lambda )=(\lambda +y{)}^3$.

后续细节留做习题, 答案是 $B=y+A=y+{\sum }_{n\ge 1}\frac{1}{n}\left(\genfrac{}{}{0ex}{}{3n}{n}\right)x^n{y}^{2n+1}$

Example 1.2.10. 假设 $H(x-x^2)=(1-x{)}^{-1}$, 计算 $H(x)$.

设 $B(x)=x-x^2,f(x)=(1-x{)}^{-1}$, 设 $B(x)$ 的复合逆为 $A(x)$.

于是我们得到 $H(B(x))=f(x)$ 当且仅当 ${\mathrm{e}\mathrm{v}}_A(H(B(x)))={\mathrm{e}\mathrm{v}}_A(f(x))$ 当且仅当 $H(x)=f(A(x))$

现在我们可以使用 LIFT 计算 $A$.

设置 $\varphi (\lambda )=\frac{\lambda }{B(\lambda )}=(1-\lambda {)}^{-1}$, 我们观察到 $A(x)=x\varphi (A(x))$.

后续细节略去不表, 答案是 $H(x)=1+{\sum }_{n\ge 1}\frac{1}{n}\left(\genfrac{}{}{0ex}{}{2n}{n-1}\right)x^n={\sum }_{n\ge 0}\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)x^n$.

Theorem 1.2.11 (Abel 二项式定理). $$(a+b)(a+b+n{)}^{n-1}=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a(a+k{)}^{k-1}b(b+n-k{)}^{n-k-1}$$

Proof. 考虑 $\varphi (\lambda )=e^x$, 根据 LIFT 存在一个级数 $T(x)$ 使得 $T(x)=x\varphi (T(x))$. 考虑 $f(x)=e^{cx}$, 其中 $c$ 为任意可逆元素, 则根据 LIFT 我们有$$[x^n]f(T(x))=[x^n]e^{cT(x)}=\frac{1}{n}[{\lambda }^{n-1}]f^{\prime }(\lambda )\varphi (\lambda {)}^n=\frac{c(c+n{)}^{n-1}}{n!}$$

接下来注意到根据指数级数的性质, 我们有 $e^{(a+b)T(x)}=e^{aT(x)}{e}^{bT(x)}$. 接下来我们注意到这意味着$$n![x^n]e^{aT(x)}{e}^{bT(x)}=n!\cdot \sum _{i=0}^n\left([x^i]e^{aT(x)}\right)\cdot \left([x^{n-i}]e^{bT(x)}\right)=\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)a(a+i{)}^{i-1}b(b+n-i{)}^{n-i-1}$$在另一边, 我们有$$n![x^n]e^{(a+b)T(x)}=n!\cdot \frac{(a+b)(a+b+n{)}^{n-1}}{n!}=(a+b)(a+b+n{)}^{n-1}$$因为 $e^{(a+b)T(x)}=e^{aT(x)}{e}^{bT(x)}$, 所以我们得出$$n![x^n]e^{aT(x)}{e}^{bT(x)}=n![x^n]e^{(a+b)T(x)}$$也就是说$$(a+b)(a+b+n{)}^{n-1}=\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})a(a+i{)}^{i-1}b(b+n-i{)}^{n-i-1}$$

$\square$

1.3代数变换

这一章的内容在很长一段时间里都不会用到, 所以我暂且不翻译了...

Suppose we have polynomial $p(z_0,z_1,z_2,...)\in R[z_0,z_1,z_2,...]$. For example, $p(z_0,z_1,z_2,...)=z_1{z}_4^2+z_{999}\in \mathbb{Q}[z_0,z_1,z_2,...]$. Given such a polynomial, we get a function ${\varphi }_p:R[[x]]\to R$ given by$$U(x)=\sum _{n\ge 0}{u}_n{x}^n\mapsto p(u_0,u_1,u_2,...)$$We call such ${\varphi }_p$ an algebraic function.

For example, given $p(z_0,z_1,z_2,...)=z_1{z}_4^2+z_{999}$ then $p({\sum }_{n\ge 0}n{x}^n)=1\cdot 4^2+999$.

Similarly given $p(z_1,z_2,...)\in R[z_1,z_2,...]$, we get a function ${\varphi }_p:R[[x]{]}_{+}\to R$ given by ${\sum }_{n\ge 1}{u}_n{x}^n\mapsto p(u_1,u_2,...)$, which is called an algebraic function as well.

For example, if $p(z_0,z_1,...)=z_n$ then ${\varphi }_p=[x^n]$.

Definition 1.3.1. An algebraic transformation of FPS is a function $f:A\to B$ with $A,B\in \{R[[x]],R[[x]{]}_{+}\}$ such that $[x^n]\circ f$ is an algebraic function for all $n\ge 0$.

Example 1.3.2.

1.	Squaring map: $sq:R[[x]]\to R[[x]]$ is given by $U(x)\mapsto U(x{)}^2$. We see $[x^n]\circ sq:U(x)\mapsto [x^n]U(x{)}^2={\sum }_{k=0}^n{u}_k{u}_{n-k}$, which is a polynomial in $u_0,u_1,...$ and hence it is an algebraic transformation.
2.	Differentiation map: $\frac{d}{dx}:R[[x]]\to R[[x]]$ is given by $U(x)\mapsto U^{\prime }(x)$. This is algebraic transformation since $[x^n]U^{\prime }(x)=(n+1)u_{n+1}$, which is a polynomial in $u_0,u_1,...$ as desired.
3.	Evaluation map: Given $B(x)\in R[[x]{]}_{+}$, the evaluation map $e{v}_B:R[[x]]\to R[[x]]$ is given by $U\mapsto U(B(x))$. We have $[x^n]\circ e{v}_B(u(x))$ is a linear function of $u_0,u_1,u_2,...$, as one can show.
4.	Application map: given $A(x)\in R[[x]]$, we get $a{p}_A:R[[x]{]}_{+}\to R[[x]]$ is given by $U(x)\mapsto A(U(X))$. This time $[x^n]\circ a{p}_A(U(x))$ is a degree $n$ polynomial of $u_1,u_2,u_3,...$, as one can show.

Definition 1.3.3. Let ${\mathbb{T}}_f={\mathbb{T}}_{full}={\mathbb{T}}_{full}(R[[x]])$ be the set of algebraic transformations $R[[x]]\to R[[x]]$.

We use $\mathbb{T}$ be the set of algebraic transformations $R[[x]{]}_{+}\to R[[x]]$.

We use ${\mathbb{T}}_{+}$ be the set of algebraic transformations $R[[x]{]}_{+}\to R[[x]{]}_{+}$.

In particular we have$${\mathbb{T}}_{+}\hookrightarrow \mathbb{T}\twoheadleftarrow {\mathbb{T}}_f$$

We also note $g\in \mathbb{T}$, $h\in {\mathbb{T}}_{+}$ then $g\circ h\in \mathbb{T}$. To see why composition is again algebraic trans, just note composition of polynomials is still polynomial.

On the other hand, $f\in {\mathbb{T}}_f$ and $g\in \mathbb{T}$ then $f\circ g\in \mathbb{T}$.

Note we get a ring structure on $\mathbb{T}$ because the codomain of $\mathbb{T}$ is a ring, hence we can define $f,g\in \mathbb{T}$ then we define $f+g:U(x)\mapsto f(U)+g(U(x))$. Define the similar point-wise subtraction and multiplications, we get a ring.

The $0$ element will be the map $U(x)\mapsto 0$ and the $1$ element will be $U(x)\mapsto 1$.

We note ${\mathbb{T}}_f$ is a ring, but ${\mathbb{T}}_{+}$ is not a ring as it is missing the multiplicative identity.

Remark 1.3.4. We can also take limits of algebraic transformations. Given $f_0,f_1,f_2,...\in \mathbb{T}$, or in ${\mathbb{T}}_f,{\mathbb{T}}_{+}$. Then we say$$\underset{n\to \infty }{\lim }{f}_n=f\in \mathbb{T}$$if and only if ${\lim }_{n\to \infty }{f}_n[U(x)]=f(U(x))$ for all FPS $U(x)\in R[[x]{]}_{+}$. Hence we can also talk about infinite sums and products of algebraic transformations.

Remark 1.3.5. In particular we can define composition with FPS. If $A(x)={\sum }_{n\ge 0}{a}_n{x}^n\in R[[x]]$, and $f\in {\mathbb{T}}_{+}(R[[x]])$. Then we can define $A(f)={\sum }_{n\ge 0}{a}_n{f}^n\in \mathbb{T}$. As an exercise, show that $A(f)=a{p}_A\circ f$.

Example 1.3.6. Let $f=e{v}_{x^2}$ and $g=\frac{d}{dx}$. Then what does $\exp (f^{2}g)\circ f$ do?

Apply this to $U(x)$, we see $$\begin{array}{rl}\exp (f^{2}g)\circ f[U(x)]& =\exp (f^{2}g)[U(x^2)]\\ & =\exp (f(U(x^2){)}^2\cdot g(U(x^2)))\\ & =\exp (U(x^4{)}^2\cdot 2x{U}^{\prime }(x^2))\end{array}$$

Remark 1.3.7. Caution: note algebraic transformations are not formal power series. For example, if we have $A(x),B(x)\in R[[x]],U(x)\in R[[x]{]}_{+}$. If $A(U(x))=B(U(x))$ we know in fact $A=B$.

However, on the other hand, if we have $f,g\in \mathbb{T}$, then $f[U(x)]=g[U(x)]$ does not imply $f=g$.