前几日做了G.Polya,G.Szego的《数学分析中的问题和定理》中的几道题目,深感知识面的不足.在这里做一个简单的小结.

组合学中一些排列组合问题,可以与数论中丢番都方程的解的个数相联系:$f(x_1,x_2,\cdots,x_n)=N$.这样,便可与无穷级数及积分发生联系.对于$X^N$的系数,可以与$f(x_1,\cdots,x_n)=N$的非负整数解的个数相对应,也可以与$\sum{\int_{0}^{1}{e^{2\pi{}i(f(x_1,\cdots,x_n)-N)z}dz}}$的值相联系,这一些恰是堆垒数论的基础.下面便通过《数学分析中的问题和定理》中的几个例子,来说明这种联系.

注:对应的方法在组合数学中称为生成函数.

1.一美元能有多少种不同的兑换方法?(1,5,10,25,50).显然,这个问题与Diophantine方程$x+5y+10z+25u+50v=100$的非负整数解的组数问题等价.一种兑换方法对应于一组非负整数解$(x,y,z,u,v)$.在《数学分析中的问题和定理》的第2题匾给出了Diophantine方程与无穷级数的联系.

2.设$n$为一非负整数,$A_n$表示Diophantine方程$x+5y+10z+25u+50v=n$的非负整数解的组数,则级数

\[A_0+A_1\zeta^1+\cdots+A_n\zeta^n+\cdots\]

表示$\zeta$的一个有理函数,求此函数.

我们发现

\[\zeta^n=\zeta^{x+5y+10z+25u+50v}|_{x+5y+10z+25u+50v=n},\]

从而给出一组解$(x,y,z,u,v)$,就给出一个$\zeta^n$,于是

\[\sum_{x+5y+10z+25u+50v=n}\sum_{x \ge 0}\sum_{y \ge 0}\sum_{z \ge 0}\sum_{u \ge 0}\sum_{v \ge 0}{\zeta^{x+5y+10z+25u+50v}}\]

就给出了$\zeta^n$的系数,从而给出了方程的解的个数,故

\[\begin{aligned}\sum_{k=0}^{\infty}{A_k\zeta^k} &= \sum_{x \ge 0}\sum_{y \ge 0}\sum_{z \ge 0}\sum_{u \ge 0}\sum_{v \ge 0}{\zeta^{x+5y+10z+25u+50v}} \\&=\sum_{x \ge 0}{\zeta^{x}}\sum_{y \ge 0}{\zeta^{5y}}\sum_{z \ge 0}{\zeta^{10z}}\sum_{u \ge 0}{\zeta^{25u}}\sum_{v \ge 0}{\zeta^{50v}} \\&=(1-\zeta)^{-1}(1-\zeta^5)^{-1}(1-\zeta^{10})^{-1}(1-\zeta^{25})^{-1}(1-\zeta^{50})^{-1}.\end{aligned}\]

有了这种表达方法,对于Diophantine方程是否有解,只需看$\zeta^n$的系数是否为0,解是否唯一,只需看$\zeta^n$的系数是否为1.这样便可给出下面两题的证明思路.(所给题目编号按《数学分析中的问题和定理》)

14.用一组重量为1,2,4,8,16,$\cdots$的砝码放在天平的一端的平盘上,能够称出给定单位的任何正整数倍的重量,并且这样的称法是唯一的,这就是说,任何正整数在二进制系统里都有唯一的表示式.

15.如果天平的两个枰盘都可利用,则用一组重为1,3,9,27,$\cdots$的砝码就能称出给定单位的正整数倍的任一重量,而且称法是唯一的.

14题可化为

\[x_1 + 2x_2 + 4x_3+\cdots+2^kx_{k+1}+\cdots=n,\]

其中$x_i=0$或$1$的解的问题.由此有

\[(1+x)(1+x^2)(1+x^4)\cdots(1+x^{2^n})\cdots=\frac{1}{1-x}=1+x+x^2+\cdots+x^n+\cdots.\]

15题可化为:

\[x_0 + 3x_1 + 4x_2+\cdots+2^kx_k+\cdots=n,\]

的解的问题,这里$x_i=-1$,$0$,或$1$.由此可得

\[(x^{-1} + 1 + x)(x^{-3}+1+x^3)\cdots(x^{-3^n}+1+x^{3^n})\cdots.\]

至于两个级数的获得,可以同题2做相同的考虑.

14题:

\[\begin{aligned}&\sum_{x_1=0,1}\cdots\sum_{x_{k+1}=0,1}{x^{x_1 + 2x_2 + 4x_3+\cdots+2^kx_{k+1}}}\\=&(\sum_{x_1=0,1}{x^{x_1}})(\sum_{x_2=0,1}{x^{2x_2}})\cdots(\sum_{x_{k+1}=0,1}{x^{2^kx_{k+1}}})\\=&(1+x)(1+x^2)\cdots(1+x^{2^n})\end{aligned}\]

15题:

\[\begin{aligned}&\sum_{x_0=-1,0,1}\cdots\sum_{x_k=-1,0,1}{\zeta^{x_0 + 3x_1 + 4x_2+\cdots+2^kx_k}}\\=&(\sum_{x_0=-1,0,1}{\zeta^{x_0}})\cdots(\sum_{x_k=-1,0,1}{\zeta^{3^kx_k}})\\=&(\zeta^{-1}+1+\zeta^1)\cdots(\zeta^{-3^n} + 1 + \zeta^{3^n})\end{aligned}\]

反过来,用组合与Diophantine方程问题也可以证明无穷级数的等式.(这里在假定两边无穷级数均收敛的情形下)

19.证明:

\[(1+\zeta)(1+\zeta^2)(1+\zeta^3)(1+\zeta^4)\cdots = \frac{1}{(1-\zeta)(1-\zeta^3)(1-\zeta^5)(1-\zeta^7)\cdots}.\]

其中一个方法为

\begin{gather*}(1+\zeta)(1+\zeta^2)(1+\zeta^4)\cdots=\frac{1}{1-\zeta} \\(1+\zeta^3)(1+\zeta^6)(1+\zeta^{3\cdot2^2})\cdots=\frac{1}{1-\zeta^3}\\…\end{gather*}

另一个方法为两边取对数,为

\[\ln{(1+\zeta)}+\ln{1+\zeta^2}+\cdots = -\ln{(1-\zeta)}-\ln{(1-\zeta^3)}-\cdots,\]

用$\ln{(1+x)}$的级数展开.

第三个思路便是用组合或Diophantine方程等模型.

$(1+\zeta)(1+\zeta^2)\cdots$中$\zeta^N$的次数为

\begin{gather}x_1+2x_2+\cdots+kx_k+\cdots=N\end{gather}

的解的个数,

$(1-\zeta)^{-1}(1-\zeta^3)^{-1}\cdots$中$\zeta^N$的次数为

\begin{gather}x_1+3x_2+\cdots+(2k-1)x_k+\cdots=N\end{gather}

的解的个数.

其中第一个方程中$x_i=0$或$1$,第二个方程中,$x_i \ge 0$.剩下的就是证明两个方程的解的个数相等.(略)

用同样的思路解决其中的题4.

4.考虑一类和式,其中每项的值可取1,2,3,4四个数.把和数位$n$($n$为正整数)的所有这种和式的数目记为$B_n$,(用相同数字按不同次序构成的两个和式,看作是不同的),则级数

\[1+B_1\zeta+\cdots+B_n\zeta_n+\cdots\]

表示$\zeta$的一个有理函数,求出这个函数.

$x_1+x_2+\cdots+x_k+\cdots=n$,这里$x_i=1,2,3,4$.于是

\[\begin{aligned}&\sum_{x_1=1,2,3,4}\cdots\sum_{x_k=1,2,3,4}{\zeta^{x_1 + \cdots+x_k}}\\=&(\sum{\zeta^{x_1}})\cdots(\sum_{\zeta^{x_k}})\\=&(\zeta+\zeta^2+\zeta^3+\zeta^4)^k\end{aligned}\]

而$n$的表示式中,$k$的取值可以不同,于是

\[\begin{aligned}\sum{B_n\zeta^n}&=1 + (\zeta + \zeta^2+\zeta^3+\zeta^4) + \cdots + (\zeta + \zeta^2+\zeta^3+\zeta^4)^k+\cdots \\&=\frac{1}{1-\zeta – \zeta^2-\zeta^3-\zeta^4}.\end{aligned}\]

必须注意,这里用到了求和号$\sum$的重要性质:

\[\sum_{i}\sum_{j}{x^ix^j}=\sum_{i}{(x^i\sum_{j}{x^j})}=(\sum{x^i})(\sum{x^j}).\]