组合学学习笔记1.pdf

组合学笔记 1组合计数基础 41.1 排列与组合.41.2 映射与 S tir ling 数.81.3 多项式乘法及其组合意义.111.4 容斥原理.151.5 数论应用：欧拉函数。与Mobius函数.202母函数方法 232.1 形式基级数环.232.2 母函数方法.282.3 概率论应用：随机游走.353极值集合论I:基本概念与方法 383.1 算两次.383.2 抽屉原理.423.3 S per ner 定理.443.4 Bollobas 定理.483.5 Er dds-Ko-I Wo 定理.493.6 S chur引理与Fp上的费马大定理.544图论初步 564.1 图的基本概念.5614.2 树，平面图与Euler公式.614.3 生成树与Cayley公式.674.4 拓扑学应用：Br ouwer不动点定理.725相异代表元系 795.1 相异代表元系与Hall定理.795.2 二部图的匹配.815.3 Hall定理的若干应用.866 Turan 问题 886.1 Mantel 定理.886.2 Tur an 定理.916.3 Ajtai-Komlds-S zemer edi 定理.956.4 Kovar i-S os-Tur an 定理.997 Ramsey 理论 1027.1 Rams ey 数 R(s,t).1037.2 多色Rams ey数 以，曲，,s Q.1077.3 超图 Rams ey 数 Rrs,t).1097.4 练习：Rams ey数A(3,ri)的渐近估计.1138概率方法 1178.1 概率的次可加性.1188.2 期望的线性性与平均值原理.1238.3 删除技巧.1268.4 练习：Rams ey数R(3,n)的渐近估计II.1318.5 Lov6s z局部性引理.1379极值集合论n：线性代数方法 1419.1 奇偶镇问题与Fis her不等式.1419.2 欧氏空间中的2-距离点集.1459.3 代数簇与八相交族.1499.4 矩曲线与Bollob迎定理的变式.153210谱方法 15410.1 图的邻接矩阵与谱.15410.2 Laplace矩阵与Kir chhoff矩阵树定理（待重写）.15510.3 多重图（待补）.16131组合计数基础1.1排列与组合1.1.记号.我们采用如下通用记号约定:若不特别说明，一般的数字n默认正整数，一般的集合X默认有限集.对于集合X,记|X|:=1,即X的元素个数.|X|也可记作#X.x e xn 对于n个集合Xi,.,Xn,如果AX:j=0,V，/j,则(JXi也可以记作 i=lnLI 2,称为无交并.特别地，若力GB=0,则也可记作AU B.。=1 对于集合X,工记笛卡尔积x x Y：=3必e X】e Y.此外，记 Xn:(rri,xn)x i e X,i 1,n,即取值于 X 的 n 元有序组之全 体.对于映射卜X T Y以及V G Y,记fT(y):=x G X0)=y为y关 于f的原像集.1.2.记号.设72为正整数，则记集合n:=1,2,71.特别规定0:=0.阶乘川：=1 x 2 x 3 x x a特别规定0!=1.对于 0 S k S 小 排列数(72)A：=n(n-1)(r z k+1)=n!(n k)!对于0 S k Sh，组合数nkn k)1.3.性质.以下3条事实是显然的，称为组合计数基本原理：1.对于集合X,Y,则|X|=|Y|当且仅当存在双射/：X T匕42.对于集合x,-若x n v=0,则|x 口叫=|x|+|y|.3,对于集合 X,Y,则|X x Y|=|X|.|K|.1.4.记号.对于集合X,2y 4|4 C X,即X的全体子集构成的集合.（：）:=AQXA=k,即X的全体k元子集构成的集合.例如,若X=3,则=0（；）=1,2,3）Q=口,2,113,2,3Q=口，2,32x=0,1,2,3,1,2,1,3,2,3,1,2,3）1.5.性质.对于集合X,以下是众所周知的基本常识:其证明与组合意义都众所周知，不再赘述.1.6.性质.以下组合恒等式成立：5证明.虽然可以代入组合数公式（力=7暴力验证，但我们还是希望k）kn-k）“用组合的观点理解它们.1.我们知道，（1）是从同当中挑选k个元素的方法数；若挑选了某k个.则 剩下（r i-k）个元素未被挑选，这自然给出“从n个元素中挑选k个”与“从n个元素挑选n k个”之间的一一对应，从而得证.2.对于n的k元子集A,则要么1 G A,要么1任4若1任4,则需要从 n 1中挑选k个；若1 e4只需再从n 1中挑选k 1个.从而 得证.3.最后看第三个.设想某个班有n个学生，从中选出k个人参加某小组活 动，并在这k人当中选出1名组长，则安排方案有多少种.一方面，先选 出参加活动的k人，共种选法，然后再从k人当中选出组长，因此总 共心种方案；另一方面，也可以先从n个人当中指定组长，再从剩余（r i-1）人当中选出（k-1）名组员，因此共有几种活动方案.因此）=0得证1.7.例题.（Vander monde卷积公式）.对于正整数凡成立证明.直接代入组合数公式并不能轻易证明此式；而在组合 的观点下，它显然成立.设想有m个男生与几个女生当中挑选k个人，一方 面，显然有（小；九）种挑选方法；另一方面，考虑选出来的k人当中男女各多 少，若选出z个男生j个女生，则这样的取法有（；）（；）种，再让i,j取遍（0）=卜,0）即可.6可见，适当构造组合模型，并用不同的方法计数，能够得到不平凡的恒等式.1.8.性质.关于n个未知数x-i,xn的不定方程21+%2-I-Xn=kXi e 0,1,Vz=1,n有（；）组不同的解.这是显然的.为满足此方程，n个未知数里面必然有k个取值为1;这相当 于从n个未知数里挑选k个.1.9.性质.关于几个未知数3）xn的不定方程g+力2+,+力n=k工，e Z0)V z 1,)久有.+-1）组不同的解.这是经典的“隔板插球，问题.设想有71个不同的箱子与k个相同的球，将 这k个球放入这n个箱子，若第i个箱子里放入g个球，则（3,九）是上述 不定方程的一组解.容易验证该不定方程的解与将球放入箱子的方法一一对应,从而解的个数等于将球放入箱子的方法数.为了把球放到箱子里，先把这k个球从左往右排成一排，在相邻两球的间隙 处插入隔板，用-1）个隔板把球分成n堆，这n堆从左往右依次放入n个箱 子里.于是，只需考虑有多少种插入隔板的方式.将k个球与（r i-1）个隔板都 视为物体，共有（k+-1）个物体从左向右排成一排，占据（k+-1）个位置.这任十九1）个位置里面，有k个位置是球，因此共有k+：T）种情形.1.1。习题.从1,2,./中选出r个不同的整数，要求这r个整数中的任何两 个都不相邻.则符合要求的选法有多少种？解.将选中的r个整数视为隔板,未选中的整数视为球,则“任何两个选中的整数 都不相邻”即任何两个隔板都不能紧挨着，这当且仅当任何两个隔板之间都必有 球.同上一题,考虑“隔板插球”与“箱子放球”的一一对应,从而只需考虑（r+1）个不同的箱子当中，除了第1个箱子与最后一个箱子之外，其余（r-1）个箱子里 7都至少有1个球的情形.于是，不妨先将第2,3,.,r个箱子里各放1个球，然后 还剩下(n r)(r 1)=(n 2r+l)个球.之后就转化为把(n 2r+l)个球放入(r+1)个箱子里的问题，因此共有(二(一种方案.口另解.除了把问题强行转化为1.9,我们还有更简洁的方法.依然将选中的数字视 为隔板，未选中的数字视为球.则一共有(n-r)个球.注意到隔板的位置一定是 在相邻两球之间，或者第一个球的左侧，或者最后一个球的右侧，一共(n-r+1)个可供插隔板的“空隙”.任何两个隔板不能紧挨着，相当于每个“空隙”至多 被插入一个隔板.即S-r+1)个空隙当中的r个空隙里面有隔板，故共有+D种情形.1.2 映射与Stirling数L1L记号.对于集合X,Y,记：=即从X到Y的映射构成的集合.1.12.性质.对于集合x,y,成立1.尸|=丫产.2.#/G h是单射=(|y|)|x|:=|y|(|y|,i).(|y|,|X|+1).证明.记 X=%.,Y=?/i,.,yn,其中 r n:=X,n:=Y.对于 映射/:X T F,则对每个 G X,f都有|叫种可能的取值，因此共有 n|y|=|y|x|种可能的情况.接下来考虑单射的个数.设广x-y是 尤X单射，则不妨先确定为)的取值，这有丫|种情况；确定的)之后，%2)将只有(|y|-1)种合法的取值，以此类推.因此从x到y的单射的个数为|y|(|y|-i).(|y|-|x|+i).8自然要问，对于集合x,v,从x到y的满射有多少个？1.13.记号.对于(非空)集合X,记Sx：=fe xxf是双射.Sx种的元素称 为集合X的置换，或者重排.对于正整数n,记Sn:=S网.众所周知，对任意f,g G Sx,复合映射fo ge Sx,逆映射fT E S x,恒等 映射id:X t X也属于S x,因此Sx关于映射的复合运算构成群，这个群称为 集合X的置换群.容易证明，若|X|=n,则有群同构Sx*Sn,因此我们不妨只 考虑Se众所周知，Sn中的元素都可唯一分解为两两不交的轮换之积.nXn=s(%k)(2)af c=O证明.将上式等号两边视为关于C的多项式，因此只需证明1为正整数的情形.现在令x=m G Z+.考虑从n到m的映射个数，一方面，它显然为mn;另一1.14.定义.对于集合X,以及必C 2,即M是由X的某些子集构成的集合,如果M中的元素都非空且两两不交，且 口 4=X,则称是X的一个划分.*X1.15.定义.对于正整数r,n,令(-l)n-rs(r,n):=形如几个不交轮换之积、S(r,n):=#.s(r,n)与S(r,n)分别称为第一类S tir ling数与第二类S tir ling数.可见，S(r,n)是将r划分为n个非空子集的方法数.1.16性 质.从r到网 的满射的个数为5(r,n)-n.证明.对于满射/:r T n,考虑集合&:=1Q ry E n,则也给 出了 r的一个n元划分.反之，卜的每个n元划分都自然地对应于nl个从r 到n的满射.因此r到间的满射共有S(r,zz)川个.口1.17.性质.对任意 e C,以及正整数%成立9方面，对于映射/：n T m,考虑对f的像集/(n)进行分类，先确定f的像 集有多少个元素，再确定f的像集有哪些元素，从而mn=|词叫E E#/网网(网)=xk=。xe(嗯)nE E#广网rx|/为满射k=。XC(1an n E E klS(n,k)=k；二 kNSgk)k=o xe(7)k=0、卜ns(%k).(m)fc,k=0故得证.1.18.引理.对于正整数n,k,记c(n,k)(l)n-fcs(n,k),其中s(n,k)是第一类S tir ling数.则成立递推关系c(n,k)n l)c(n 1,k)+c(n l,k 1).易知c(n,k)是Sn中的形如k个不交轮换之积的置换的个数.证明.若/G S 形如k个不交轮换之积，则这样的f有c(n,k)个.另一方面,对于这样的/,如果/(I)=1,则f在子集nl上的限制映射自然看成S7一 中的形如(k-1)个不交轮换之积的置换，因此满足/(I)=1的这样的f共有 c(n-个.而如果/(I)#1,记0:=/*1,则沙有(n-1)中不同选取，对于每个可能的y,考虑如下映射%:先：形如望M仑换之积-四小形如k个不交轮换之积f 1先用：?1若，=尸 其他情况则容易验证见良定，且是一一映射.(翻译成人话，意思是说，如果/*1,则 1 G n所在/-轨道的长度大于1,把1 G n从该轮换中删去，再连接/T(l)与10/(I),就得到一个长度比原来小1的新的轮换，如此修改后的f自然是n 1 的置换，且形如k个不交轮换之积.)因此满足/(I)=y的这样的f共有 c(n 1,k)个.综上所述，c(n,k)(n l)c(n 1,A:)+c(n l,k 1).得证.1.19.推论.对于x e C,以及正整数n,成立n(x)n 2 s(n,k)xk.k=0证明.或许可以寻求等号两边的组合意义，但别忘了数学归纳法.对n归纳,九=1时显然成立.对于一般的n,利用归纳假设以及上一题的递推关系，可知n ns(n,k)xk=l)n+fcc(n,kxkk=0 k=0n=l)n+fc(n l)c(n 1,k)xk+c(n 1)k 1)/fc=On=(1 n)J2(l)n-1+fcc(n 1,k)xkk=0n1X(i尸+kc(n 1,k)xkk=Q(1 一九)(%)7Z1+I Q)?!1(7),从而得证.口1.20.考虑线性空间Vn:=/G Ca?|deg/0,n凹/=e n1四方i1H-Hn=j=lij 0,V J=l,.,n证明.直接用多项式乘法展开，然后合并同类项即可，这是显然的.口1.23.推论.（二项式定理）.对于正整数n,成立a+，）”=k=0 ）证明.此定理众所周知，但这里还是要象征性证明一下.在1.22中，取力=力=%=1+%,/：=于1于2/=(1+乃，从而对每个 A;0,酎/=*(1+/)=14-1-Hn=k 1-1-in=ij 0,V J=l,.,n ij=0,1=#(。1，必，In)|+，+=冗 =。,1注意最后一个等号利用了 18 1.24.推论.若IL,I2,.：Jn都是的有限子集，记多项式力=j=ie ij1,n,则关于未知数41,g 的不定方程X+,+xn=kXj /Vj=1,2,n的解的个数为凶（/2九）.12证明.这个是显然的.L21从而我们建立了多项式乘法与组合问题之间的联系.作为简单应用，我们 可以立刻给出Vander monde卷积公式1.7的一个另证：（九十 m律(1+x)n+m=评(1+i)n(l+x)m)i,j01.26.例题.证明如下等式:证法一.（构造组合模型）.设想某个班级有几名同学，需要从中挑选若干同学（至少1人）参加某小组活动，参加小组活动的同学之中需要有1人担任组长，那么总共有多少种活动安排方案.一方面，若选择k人参加活动（k=1,2,则有（；）种选法，之后在参加活动的k人之中选出组长，因此恰有k人参加的活动方案共有种，总共另一方面，先从全班种活动方案.n人之中选定组长，然后依次询问剩余（r i-1）个人中的每一个人是否参加，由此易知共有n-2n-1种活动方案.除了构造组合模型，微积分也是强力的手段：另证.（用微积分）.将等式（1+/严=（/两边对/求导，得到 k=0 71(1+%)T然后令.T=1,得证.13除了关于一个变元的多项式，我们也可以考虑关于n个变元叼,，外的 多项式.多元多项式的乘法当然也具有组合意义.1.27.定乂.（多重组合数）.设k,卜2,kn 6 o,k:=的+心+十七，则记k _ k!ki,kn).历!后!一廉!,考虑这样的组合问题：k个不同的球放入n个不同的箱子里，要求第i个箱 子里放除个球，i=试求符合要求的方案个数.为得到符合要求的方案,先将这k个球从左到右排成一队，共有k种方法;接下来,把最左边自个球放入 1号箱，1号箱完成之后再将最左边k2个球放入2号箱，不断进行下去.然而,在一开始，最左边的%个球之间无论如何排队（自！种情况），最终全都进入1号 箱，不同的排队方式导致最终同样的将球放入箱子的方案；这对进入2号箱，以 号箱的球也如此.因此共有f-=（1k 7）种符合要求的方案.岛!的!ki,k2,knJ1.28.性质.设/1,xn是n个变元，则对A;0,成立（为+%）卜=/八婢琮吟.kl+k2+.+kn=k 描,%0证明.对每一组考察（3+/的婷琮/%项系数.注意（为+x n）k是k个一次多项式的乘积，这k个多项式之中的每一个都在展 开式的每一项中贡献xu.,xn之一.为得到斓/2球1项，这k个多项式中 需要有加个贡献/i,k2个贡献x2,.,kn个贡献/%于是由多重组合数的组合意 义易知展开式中共有L 7 L 7 1项对斓42琮”有贡献.从而易证.口 ki,k2,k n1.29.性质.设3）4rl为n个变元）则成立(1+&)=):=1 A Cn iA证明.肉眼观察等号左边，在心里将等号左边全部展开，即得证.141.4容 斥原理1.30.对于集合A,B,我们知道，如果AHB=0,那么|A U切=|川+|B|.而 如果A,B的交集非空，则用|川+|B|来计数AU B的元素个数，就会将AHB 中的每个元素重复计数一遍.为得到正确的结果，只需再减去AQB.因此，AU B=A-B-AQB,这是小学生也能通过画图理解的容斥原理.然而，如何将两个集合A.B的情形推广到多个集合？1.31.记号.在一定语境下，假设我们谈论的所有集合都是某个集合Q的子集.对于集合4记4：=N：=C4称为集合4在。中的补集.对于集合4,定义函数1人：Ct 0,1如下：1 若 e A1a(%)：=,I o若2任4函数14称为集合A的特征函数.对于给定的集合4,4,力九，则对每个01 Q n,记4/：=记I此外，特别规定=Q补集的运算律众所周知，这里不再赘述.关于特征函数，特别注意如下运算 律：lnB 1a,1氏 14c 1 1a-1.32.定理.(容斥原理).给定全集。的子集4,4,则ni=ln(t严+1川=(-1 产0ZCn k=lE山15ni=l(1)叫=(i 产/Cn fc=OE川 g?)/容易验证上述两式等价，不妨只证其中一个.证法一.事实上，我们断言:n1韦nn布=E(-i)fc E 儿(吟 k=o 人册)假如我们证明此式，则将此式两边求和,注意|川=1/琼 即可得到.力eQ为证明(6),只需证明它对每个都成立.任意给定/e 0,记0:=#i 6 n|x G Ai,即力恰属于A,.,4之中的夕个集合.如果Q=0,则易知等号两边都为1,从 而相等.如果2#0,则必属于Ai,An中的某个集合，从而/任尚门 口段”因此(6)式等号左边为0.而由的定义易知 lAl(x)=C),因止匕(6)式等 人册)7号右边=(1产(；)=(1-1)2=0.k=0 R/综上所述，(6)得证，从而定理证毕.口这个证明富有启发性，启发我们“看每一个元素对左右两边的贡献”.另证.记4:=4 U 42 uU An,则容易验证nn(u-u)=o,k=l这是因为，对每个2 6。，如果出4则x 0 41,从而1(%)=1a()=0;而如 果2 e 4则x必然属于某个4,因此1这是因为，对于f e Dm则/(I)#1,从而g=/(I)有S-1)种取法；一旦取 定y,然后再分于=1与f(y)*1两种情况讨论，与引理1.18的思路类似，留 给读者.再由初始条件=0,D2=1容易求得数列Dn的通项.为此，令Pn:=母，则递推关系改写为 nlPn Pn-1)-(Pn-1 Pn-2)-n(一 1产从而易知为一=F“因此皿=加士喑k=0 k=0除了考虑递推关系并使用代数技巧，容斥原理更加直接粗暴:另证.记全集Q:=Sn.对于，=1,n,记4：=f E Sn/(z)=i,则易知U A2 U U An,因此直接套用容斥原理(5)可得nDn=|尚nn/=(-1产 川|k=0 人册)n=(ty E#皿wis ik=Q 人(明n=(-4 E I%ivi=(t)n k)!上0 人(功 日哈k=0 fc=0第一个证明中出现的Pn：=即有如下概率论理解：从sn中随机抽取一个 置换f,则事件f e Dn的概率为Pn.特别注意，当71 T+8时，fe=0n1e18 k、1.35.习题.试求集合 W:=/=1的元素个数.解.记全集。：=（2网产=（4,4,，4）14 c n.对每个 e n,记n、|j4Un|4 i=l，/：=（-Ai,4）G Q则易知。=/口该5山砥，因此直接套用容斥原理(5)得nk=E（-iy E U4/E=1（-E#（Al,，Ak）e lAi C n I,i=l,.,kj=0/e（甲）=（-14）（2）k=（2fc-j=o）l）n.除了使用容斥原理，还可以寻找递推关系.另解.将题设条件中的集合必重新记为 0,A;0,记 kMn,k:=(4,42,4人)4 同，4=九-对于21,定义映射夕九：砥#T n-l,k如下：外：(4,42,，4)(省，&，4)，其中4:=Ai n C n-1.容易验证映射小良定，并且是满射，并且对任意 A E 原像集/i(4)的元素个数是2fe-1.因此|为#|=(2fc-l)|1,则72可唯一地分解为n 讲1遇2球T,其中Pl,.,pr为不同的 素数，Q 0.对于整数Q,b,是指Q整除b,即久 Z.a 记0S)为与n互素的不超过n的正整数的个数，即(n):=#k e n|gcd(k,n)=1(7)函数。：Z+T Z+称为欧拉函数.Mdbius函数4：+1,0,1定义如下:1 若几形如偶数个互不相同的素数之积，)：=1 若乃形如奇数个互不相同的素数之积(8)0 其余情况特别地，。=/=1.对于n=讨p整瑞，则认n)*0当且仅当 ar=a2=-=ar=1,此时/(n)=(l)r.而欧拉函数0有如下显式表达式：1.37.定理.若n有素因子分解九二讲1成则T0（71）-n 口?=1证明.利用容斥原理.令全集Q=n.若k G网与不互素，则k必然含有 Pl,.,Pr之中的某个素因子.对每个i G r,记Ai:=d G n pid,因此由容斥 原理可得=hg必=（-1）叫却 IQr d=（-1严#IQr 1d G nYliEiPiG Z20广其中最后一步利用了 1.29的结论（把那里的看换成-1）.得证.Pi1.38.推论.对于正整数n,成立。=4)n ddn证明.注意上述定理证明的中间过程，有。=t（-1）一 丁 一急n记小由Mobius函数的定义易知上式右边恰为T驾2得证 a dn1.39.推论.函数。与都是积性函数，即；若7n,九互素，则(7wz)=0(m)(n),/L t(mn)(m)乩(n).证明.由1.37容易看出0是积性函数；而的积性可直接由定义看出.口1.40.定理.对于正整数n,成立、I 1 Tl 1工 6 =n,工认d）=dn dn 10 71 1其中 是指d取遍n的所有正因子（包括1与n本身）的求和.dn21证明.对于函数先考虑n为某个素数的塞次，即n=pa,a l的情形.此时dn而对于一般情形n=pF鳄瑞工注意1.39,有E（d）=矶曲能/、）=。（痔）。（虑）。（淄）dTl 1,aii=l,2,.,r i=l,2,.,r丁/Cbj -=n（。（由）=几 z=l b=0/i=l再看Mobius函数fl.不妨711,令72=破2.p鲁,则（d）=（淄虑浒）=儿（山=（t严dn iiid(ddf)n=。(屋)4(d)=。(九).dn d 脸反之，由第二式推第一式的方法完全类似，留给读者.口在上述Mobius反演公式中,取f(n)=n,g(n)=狄n),则能看出1.38与 1.40之间的内在联系.2母函数方法2.1形 式塞级数环我们从一道简单题目说起：2.42.例题.将k个完全相同的球放入a,b,c三个不同箱子中，要求a,b两个箱子 里放入偶数个球，则符合要求的方案有多少？设Q,A C三个箱子里的球的个数分别为%,243,则+%2+23=心(9)31,X2,G Zo,的,22是偶数.问题转化为求上述不定方程的解(为,g,g)的个数.解.此问题过于简单，过于特殊，初中数学的奇技淫巧足够应对.注意我们对 为,数有附加限制(要求是偶数)，而对23没有额外要求，于是不妨先考虑禽的 可能取值.注意+x2 一定是偶数，从而/3=k-(/1+/2)与k具有相同的奇 偶性.这启发我们分类讨论k的奇偶性.如果A:=2m-1,(m 1)为奇数，则23必为奇数，其取值范围只可能是 2m,111 mz 0的子集(可以是无限集)，则关于未知数为，外 的不定方程+=kXj e Ij,VJ=1,2,n有多少组解？特别地，当71=3,A=，2=0,2,4,6,.,4=Z+时，就是上一题.回忆L24,我们已经解决都为有限集的特殊情形，即，把有限集I:j对应于多项式 fKW=则方程组解的个数与多项式乘积的系数有关系.于是自然希望,Z0的无限子集也应该能对应到某个“无限项的多项式”，即,事级数；并且理解幕级数运算的组合含义.2.44.定义.设R是交换环(例如C,R,Z等)，记集合Rx :=7?z-=(io5 ai,%)|出 G 凡，N 0,即取值于R的序列构成的集合.并规定集合Rx 上的加法与乘法如下：1.(do?Qi,)+(bo,bi,.):=(q()+b(),clI+瓦,.).242.（Q）：=（。0）.）其中 Cn：=）:knk9k=0则容易验证（用国,+,）构成交换环（要验证乘法满足结合律！留给读者.）,称 为环R上的形式赛级数环.OO2.45.我们更习惯将形式幕级数环Rx 中的元素（Qo,Qi,）记为 fa3 其 k=0中2是形式变元.则形式幕级数环的加法，乘法可改写为OO 00 0c akxk+以岔=）：（。卜+砥）7）fc=0 k=0 k=0上述运算法则与微积分中的幕级数运算完全相同.co2.46.记号,设R是交换环）形式氟级数f=akxk e/?x.fc=0与多项式类似，对于k 2 0,记/:=ak,即xk项的系数，或者说是序列（qO,Qi,）的第k分量.定义映射；：Rx Rx 如下：d.（00,。1，。2,Q/i,）1（lai,2a2,（h+l）a?i+i,）.映射4-称为形式森级数环Rx 上的求导.d.T用看起来更舒服的记号，求导映射4-的定义式可改写为 axOO co:=，2（人十 1）。人+11拈=2 ka kT.k=0 k=l 25这似乎与微积分中“某个运算非常像呀.可以证明形式基级数环Rx 的乘法 运算与求导运算满足如下关系：对任意f,g G Rx,成立这似乎很像微积分里的某个运算法则呀.”乙上述关于形式基级数的一系列定义与性质，用到任何微积分知识了吗？虽 然大家心里都清楚它背后的想法来自微积分，但形式基级数环是纯粹的代数对 象，因为无法在抽象的环R上谈论极限，连续性，可微性等概念；并且仅仅 OO是抽象的符号，不能简单粗暴认为是取值于R的变量.所谓无穷求和k=0以及求导 并非某种极限，仅仅是抽象定义的代数对象与运算规则.(IX2.48.暂且不谈一般的交换环R,组合学里常用的情形是R=C(或者R).此时，OO可以谈论形式幕级数/&)=的收敛性.如下收敛半径公式众所周知：k=0记1P:=-lims up y/a k f co oOO那么对于复数n e C若 o,则形式幕级数/(x)可以视为定义在=o 附近的函数，该函数有良好的微分学性质，可以对它施展微积分的各种技术.如 果收敛半径p=0,即/(%)e Cx 在=o之外处处发散,此时/(%)不能对应 于某个通常意义下的函数.尽管如此，依然可以在形式基级数环的意义下谈论它 的乘法，求导等运算；换言之，无需考虑是否收敛.在形式幕级数理论的保证下，很容易将1.24的结论推广：2.49.性质.若小凡,In都是20的子集(可以是无限集)，记形式氟级数为=7 e C.r 5 j=1,.n,则关于未知数%n的不定方程记ij+62+,+=卜Xj /力 Vj 1,2,n的解的个数为/(九/2%).26容易验证这里的力一定是收敛的，收敛半径至少是1.2.50.重新看例题2.42.记OO OOAW 上=,力=，2=0 2=0由前文讨论可知，符合要求的方案数，即方程解的个数恰为注意fi=%=1 2,h(x)=不二，记 f：=fi(x)f2(x)f3(x),则 1 xz 1 X，=(1-.t)3(1+.t)21 1 1 1 1 1 3 1 3 1-1-1-1-1-.4(1 x)3 4(1 x)2 8(1+x)2 16 1+2 1612再注意泰勒公式，经计算得凹/=住+1+4+(T产)+条 1+(-1产)1 (*)rv O Z(容易验证上述(*)式与(10)式等价.)2.51.例题.对于n 0,记an为方程3%+2y=n的非负整数解(%,y)的个数.求数列an的通项公式.解法一.依然是简单的中学数学.考虑以除以6的余数，分成6种情况仔细讨论 即可，细节留给读者.答案为|_n/6j n=1 mod 6|_n/6j+1 n=0,2,3,4,5 mod 6其中，对于实数e%表示,T的整数部分，即不超过-T的最大整数(向下取 整).解法二.记为：=3%,X2：=2g,并且记集合 h=0,3,6,9,/2：=0,2,4,6,则显然an是方程组J+g=72l iG 71,%2 e，227解的个数.这就转化为2.49,然后只剩暴力计算.按部就班，记力伊)=於八1|,3,以及力=犷=厂二，则1 X6 1 1 X23生，2九力=(一(I T)1 1 1 f _1_ 1 6(%11+4 x+1%1J+3 x2+.t+1=L_+lp_O.6(%I)2 4 X+1 X 1 J 3y/3 x 3 X Cd2 J其中i=7 G C为虚数单位,=e竽=-g+等i是三次单位根.从而，力(九=n+1 1+6+3计1I I2.52.接上题，由厮的组合含义可知%一定是整数，然而有意思的是，解法二给 出的通项公式当中明显出现分数，根号，甚至虚数.（是不是很惊讶?!）可以验 证上题两种解法给出的an通项公式其实等价.注意g=e竽，利用三角函数的 _0一冶定义式Sil）。=2，,可将Qn的通项公式进一步化简为n+1-6-+1+(1 产 4+2.s in2(n+l)7r 32.53.习题.用本节所介绍的形式氟级数方法重新求解1.9.留给读者练习.2.2母函数方法形式基级数环C阳是解决组合问题的强大工具.我们来看更多例子.2.54.记号.对于数歹Qo,!,。2,，我们习惯把OOf（c）：=。苫 e Cxk=028俗称为该数列的母函数.2.55.记号.对于复数N e C,以及非负整数k e Z0,记(z z(z _ 1)(z-k+1)：=k不妨这样稍微将组合数的概念推广一下.在此记号下，有:2.56.性质.对任意实数r 6 以及.t 6（-1,1）,成立（1f c=O /特别地）对于正整数n,成立（l+/）f=玄（一1产十：IVk=0 证明.利用微积分中的泰勒公式即可.容易验证(1广71+k-1)2.57.例题.将编号分别为的n个不同的球放入编号分别为a,b,c的3 个不同箱子中，要求任何两个编号相邻的球不能都放入Q,箱子.符合上述要求的 方案数记为an,求an的通项公式.例如，r i=3的时候，我们把“1号球放入a,2号球放入c,3号球放入c”简 记为“qcc”，以此类推.这样子，每一种放球的方案就对应于一个由a,b,c构成的 长度为n的字符串.于是，题设条件“两个编号相邻的球不能都放入Q箱子”相 当于说，相应的字符串中不能出现连续2个Q.当h=1时，符合要求的方案共有：a,b,c三种.当71=2时，符合要求的方案共有:q6,qc,她她她cq,cb,cc八种.从而 Q1=3，。2=8.29证明.现在求一般的a叱对于ri之3,考虑1号球被放入哪个箱子里.如果1号 球被放入Q箱，则2号球将不能放入q箱，只能放入6或c;放完2号球之后，其 余(n-2)的球的安排方式有an-2种.如果1号球不在Q箱，则1号球被放入b 或c;放完1号球后，其余(n-1)个球的安排方式有厮-1种.因此：CL fi 2a九一1+2。九一2)Vtz 3.只需再结合初值条件Q1=3,Q2=8求解递推关系即可.这是众所周知的二阶线 性递推数列，求解方法有多种.这里介绍母函数方法.OO记/(%)：=anxn.那么有OO=3.T+8.T2+ann71=3OO=3.t+8.t2+y(2aTO_i+2an_2).Tn71=3=3.t+8x2+2/(/(7)3.t)+n=l/w从而解得f=27+3x l-2x-2x23+3 1 y3-3 1 12 7 一+12-.+i-山 2“i 2因此对于n 1,由泰勒公式直接求导并化简得n 6 6由组合意义，显然是整数，但其通项公式里出现一大串的根号.观察上述 通项公式,注意|1-V3|1,从而当口T 8时，3-产1 _ V3)-非常快地收 敛于0.不妨忽略掉这一项，得到册的近似公式(，3+2风/-xn Qn-7-(1+0302.58.例题.对于正整数n,在某个圆周上依次标记2n个不同的点.我们希望用 n条线段将这些点两两相连，从而把这2几个点分成n组；并且要求这n条线段 中的任意两条都不能相交.将所有可能的情况个数记为 累.求 心 的通项.不妨从某个点开始，将这2n个点按顺时针依次编号l,2,3,.,2n.把连接第 i个点与第j个点的线段记作(2,7).先来考察Tn的前几项.九=1时：只有连接1,2两点这一种情况，Ti=1.口=2时：可能的情况有(1,2),(3,4)与(1,4),(2,3),共两种.T2=2.九=3时：可能的情况有(1,2),(3,4),(5,6),(1,2),(3,6),(4,5),(1,4),(2,3),(5,6),(1,6),(2,3),(4,5),(1,6),(2,5),(3,4),共五种，从而八=5.解.方便起见，不如补充规定式)=1.对于一般的n,首先考虑点1与哪个点 相连.如果点1与点i相连，则余下的(2zi-2)个点自然被分为两组：4:=j e Zlji,Bi-=je Zij0,x i42是偶数k,比2）啰3从而a=k1Mg。!补充定义7o=l,则易知在C同中成立k信靛暂）E 1+2+13=及 q2是偶数32比较系数得Tk=ex+e2)3fc+2+(-1)3+2+(-1)我们再看一例指数型母函数的应用.2.62.例题.对于正整数n,记集合An:=/:n T Z+|存在非负整数i,使得f的值域恰为?；,特别规定0:=0,力()：=0.记an为An的元素个数(特别地，aQ=1).求数列an的指数型母函数/(%)=三产的具体表达式.n=O 证明.为此，我们来寻找数列an的递推关系.取定2 0,记ln-=(k,)E Z2 kJ 0,k+n.对于Tn的每一对(k,2),记集合或/：=(x_,x+j_j+)x-e(ex一=0,=(X,x+)X e O x+e 舟,X+n X=0 x 4 x 4断言：存在An+1与|_J 之间的一一对应，从而an+1=(k,2)Z九(k,2)CZ九事实上，对于/e 4门+1,记X:=i e n I f(i)/(n+1)(都可以是空集)，则显然X+G X_=0.记k:=|X_|,。：=|X+|.注意存在唯一 单调递增的双射(一：肉T X_,存在唯一的单调递增双射夕+：闺T X+.记/-W：=/(%(，)，/+(，)：=/(%(，)-/S+1),33则易知/_ 6 4,f+e 4.综上所述，f 1(X_,X+J_J+)给出了从4+1到 该的一个映射.可以验证这是一一映射(留给读者.请读者具体写出此的2)S映射的逆映射).因此间,x_ n X+=0,Q kQ g。九+1=(k,2)eZnQ/c Q=A：+n由此递推关系易知=#1(X.,x+)XeA：+1即，Q中的元素是由一1,2组成的无穷序列.对于a G Q,每=-1,2的意思 分别是：青蛙第i次向左跳跃1格或向右跳跃2格.对于每个i=1,2,.,记 工+:=a 6 0 =2,咛：=a e。|q=1.令夕1 2 为由所生 成的。代数，集合件中的元素为此概率模型中的事件.对于任意n 1,以及任 意b G规定P（a e C=bi,i=1,2,n）=易知此P可延拓至野、使之成为概率测度.从而建立概率模型（。,多,P）.在北语言框架下，事件“青蛙 能够到达/=0”是指集合 i A:=0,:。卜=1.、f c=i 可以验证4 e多，即4确实是一个事件.先初步考虑一下.如果青蛙第一步就向左跳，那就从起始位置=1直接跳 到目标位置/=0 了.因此青蛙能够到达/=o的概率至少是1.2.65.现在开始求解此题.记事件A为“青蛙在第i次跳跃后首次到达2=0”,换言之，Ai-a e。：Qk 1,且对任意 j z,）：，一1）,、k=l k=l）35则事件/=|_|4,从而p（4）=p（4）