第七十一讲 生成函数 讲义-2026年高中数学竞赛

第七十一讲生成函数 生成函数（又称母函数）是将数列与幂级数、多项式或其他形式的函数联 系起来的代数工具，通过代数方法得出对原数列的有关性质的研究，在组合数 学、数论中有广泛应用。 1.常见的生成函数 由数列{ann≥o,我们可以构造形式幂级数 fx=a+a1X+a2x+…, 称为ann≥0的普通生成函数。形式幂级数可如多项式那样做加减法，按乘 法分配律做乘法。两个形式幂级数相等当且仅当它们对应项的系数均相等。如 果只是在形式幂级数上运算，可以不用考虑级数的收敛性。若{a只有有限项， 则它的生成函数便是多项式。组合数C,C,“,C的生成函数就是二项式公式 C9+Cx+…+Cnx=1+x”。 设S是一个有限整数集合，研究S的子集元素和时，常用下面的生成函数 1+xl=∑xA a∈S 这里A表示A的元素和。研究S中元素两两之和时，又可以用到下面 形式的生成函数 12 x= 号 a,b∈S 研究堆垒问题，也可以用生成函数。例如有面值为1,2,3元的硬币，数量 不限，用这些硬币组成n元的方法数为an,则 x= 0 1-x1-X1-x9 生成函数的形式是多样的，需要根据不同的问题选择适当的生成函数。 例1数列{ann20定义如下：a=2,a1=5,对n≥0，有a+2=5an*1-6an 。求{an的通项公式。 解考虑生成函数fX-=∑a,X。容易用归纳法证明1a,s211,由此可 n=0 知幂级数fX)在X<品 时收敛。由递推关系可知， flX]-5Xf(X)+6x2f(X)=ao+aX-5aoX+>(an-5a-1+6an-2X" n=2 =a0+a1X-5a0X=2-5X。 因此 x-0rxxx品 再将其展开为幂级数有， fx12*x三2r+豆22+ n=0 由幂级数的系数唯一性，即得an=2”+3”,n≥0。 评注本题中需要考虑X)的收敛性，而不能只是将其当作形式幂级数来 处理，因为我们需要将其表示为一个分式函数。收敛半径并不重要，只要X)在 0的某个开邻域中收敛即可。 例2设C。=C2。是第n个卡塔兰数，m≥0。证明： n+1 2 E明记-C,由于c≤2放cs2因此f因在 x<子时收敛。 利用卡塔兰数的递推关系（§16.3例4，可得 FifC.C-C n=0 p+q=n =0 由于f0=0,故 fx=1-=4x,x<1 2 2.证明组合恒等式 例3证明： ri. 证明考虑恒等式 1"1u+cr×c 计算等式两边x”的系数。左边直接由二项式公式可知x2”的系数是 -1PC2n。而右边展开后，x2n的系数为 f.f. 从而结论得证。 例4证明： 证明在通常的母函数（幂级数或多项式）中，可以通过积分得到系数上的 专或通过求导消去系数上的专：我们从二项式公式开始。 1-x”=∑C1-1x*。 =0 因此 含c1-心 现在对两边的函数在区间0,1上求定积分， c-1ax宫-c 层三声 由此便得到所需的结果。 例5证明： ∑-1ChCk=-1P。 = 证明我们需要如下的生成函数， n+1 1-xa-1=∑x 2X=∑C.① 最后一步是由于按分配律展开后，x的系数等于方程a1+a2+…+an+1=k 的非负整数解(a1,a2,“,an+1的个数。于是 1-1-x1--cx区c-r× 又1-x=∑x。比较两个级数的系数，即得 m=0 1G-1 特别在m=n时，就是我们所要证明的等式。 3.其他应用 例6设M={1,2,“…,n},其每个元素都被染为三种颜色之一。设 A={x,y,z∈M3|x,y,z同色且x+y+z=0 modn, B={x,y,z∈M3|x,y,z两两不同色且x+y+z三0 mod n)) 证明：2A≥B。 证明设集合M中染成三种颜色的数所构成的集合分别为R,S,T。令 宫三三 gw三信宫 这样A等于gx的x”,x2n及xn的系数之和，而B等于fx的 x,x2n及xn的系数之和的六倍。 设？=e2πin是n次单位根，则任一多项式Px的次数是n的倍数的那 些项的系数之和为∑P?州。从而 n 1A=12g1,B-6∑f1。 n k=1 n 因此我们只需明三g-3空f0·注做到 =1 xrx2三g点门 三三三x宫 当x取遍(k=1,2,,n时，当且仅当k=n时，之x非零，于是 含9g-321=g1-3f刊 =R3+ls3+T3-3R·lST ≥0。 例7设p是奇素数。考虑集合S={1,2,…,2p}的所有p元子集，求其 中元素和能被p整除的p元子集的个数。 解设S的p元子集中元素和模p余j的有nj个，j=0,1,,p-1。 设？=e2mip是p次单位根，考虑多项式 fix=11+*x。 计算fx的x”项系数，一方面直接展开可知 fx 这里A)表示A的元素和。因此x的系数为 i=0 A=p 另一方面， iw-道x*空x+-e+1f-2r*1. 故 空a2. 因此？是多项式np-1x2-1++n1x+n,-2的根。熟知分圆多项式 Φnx=xP-1+xP-2+.+X+1 在Zx中不可约，？在有理数域上的最小多项式为Φ，x,因此 Φ，x|np-1xP-1+…+n1x+n-2, 这表明np-1=np-2=…=n1=n0-2。结合np-1+np-2+…+n=C2p,即得 n=2+C3。-2。 例8设整数n>1,两个非负整数集合{a1,a2,,an≠b1,b2,…,bn,而C员 个数a+a,1≤i<j≤n与C个数b,+b,1≤i<j≤n作为可重集相同（即每个 数在两组数中出现的次数相同)。证明：n是2的方幂。 证明设fx=x+x2+…+x,gx=x+x+…+x。。从而由条件可得 flx-flx=2x0=2=glxp-glx. 1si<jsn 1si<jsn 从而 flx2)-g(x2=f(xP-g(xP=(f(x)-glxiflx]+g(xl. ① 由于a1,a2,…,an≠{b,b2,…,bn,因此fx≠gx。注意到f1=g1=n, 故x=1是fx-gx的根，可设 f(x)-g(x=x-1h(x), hx∈Zx,且h1≠0。于是 f(x)-g(x2=(x2-1h(x2=(x-1(x+1h(x2, (f(x]-g(xllf(x]+g(x=(x-1h(xl(f(x]+g(x), 代入①中，并两边约去x-1,可得 x+1hx2=hxfx+gx。 ② 在②中令x=1,有2h1=2nh1，从而n=2-1,即n是2的方 幂。 最后我们看一个例子，它需要在处理生成函数的时候，将变量放在复数中 考虑。 例9（完美刻度尺）设整数n≥2。若一把长度为C的直尺上仅有n个 刻度，取其中任意两个刻度作度量，恰能量出长度1,2，“，C中的每一个值，则称 为“完美刻度尺”。求所有整数n≥2，使得存在长度为C%的完美刻度尺。 解n=2时，取刻度{0,1；n=3时，取刻度{0,1,3；n=4时，取刻度{0,1,4 ,6}，均是完美刻度尺。 下面证明，≥5时，不存在完美刻度尺。反证法，假设存在，设刻度位 于a1,a2,“,an上，且 0=a1<a2<<an=C, 显然a1,a2,“,an均为整数。考虑多项式 fz=z1+z2+…+zn。 由条件，a;-a1≤i<j≤n恰取遍1,2，，C。因此 fzfz1=z+z+…+zz+z+…+z /+n-1=212 z-1+n-1,W=C2. 下面我们推导矛盾。取z=e”是一个单位复数，则等式左边即为fe° 。而代入等式右边是 lN-1i0-e-iNO o。 sin N+1 e0-1 +n-1=ey -e -+n-1= e 2+n-1. 从而 Ifleo 2+n-1。 取 1 N+ 3即=3π则snN+ 2 0=-1 n2-n+1 sin29<0=,3n <10≤1 2 22r-n+12m-mn-,m≥5. 于是， sin N+-0 +n-1<-n-1+n-1=0, sin-0 这与fe≥0矛盾。这说明反证法假设不成立，当n≥5时，不存在完美 刻度尺。