组合数学讲义及答案 3章 递推关系

第一章答案1．(a) 45 ( {1,6},{2,7},{3,8},…,{45,50} )(b) 45⨯5+(4+3+2+1) = 235( 1→2~6, 2→3~7, 3→4~8, …,45→46~50, 46→47~50, 47→48~50, 49→50 ) 2．(a) 5!8!(b) 7! P(8,5) (c) 2 P(5,3) 8! 3. (a) n!P(n+1, m) (b) n!(m+1)!(c) 2!((m+n-2)+1)! 4. 2 P(24,5) 20!5. 2⨯5⨯P(8,2)+3⨯4⨯P(8,2)6. (n+1)!-17. 用数学归纳法易证。

8. 41⨯319. 设 n=p 1n 1p 2n 2…p kn k , 则n 2的除数个数为 ( 2p 1+1) (2p 2+1) …(2p k+1).10．1）用数学归纳法可证n 能表示成题中表达式的形式；2）如果某n 可以表示成题中表达式的形式，则等式两端除以2取余数，可以确定a 1；再对等式两端的商除以3取余数，又可得a 2；对等式两端的商除以4取余数，又可得a 3；…；这说明表达式是唯一的。

11．易用C(m,n)=m!/(n!(m-n)!)验证等式成立。

组合意义：右：从n 个不同元素中任取r+1个出来，再从这r+1个中取一个的全体组合的个数；左：上述组合中，先从n 个不同元素中任取1个出来，每一个相同的组合要生复 C(n-1,r) 次。

12．考虑,)1(,)1(101-=-=+=+=∑∑n nk k k n nnk kknx n x kC x x C 求导数后有令x=1, 即知.210-==∑n nk kn n kC13. 设此n 个不同的数由小到大排列后为a 1, a 2, …, a n 。

当第二组最大数为a k 时，第二组共有2k-1种不同的可能，第一组有2n-k -1种不同的可能。

故符合要求的不同分组共有12)2()12(21111+-=-----=∑n k n k n k n 种。

组合数学基础答案及讲稿（陶平生）基本内容与方法：组合计数；组合构造；组合结构；映射与对应；分类与染色；归纳与递推；容斥原理；极端原理；调整法；补集法；数形结合法，等等．1、设M 为n 元集，若M 有k 个不同的子集12,,,k A A A ，满足：对于每个{},1,2,,i j k ∈ ，i j A A ≠∅ ，求正整数k 的最大值．解：正整数k 的最大值为12n -．()01、先证明，存在M的12n -个子集，两两之交不空；设{}12,,,n M a a a = ，而1122,,,n A A A - 为集合{}121,,,n a a a - 的全部12n -个子集，令{}1,1,2,,2n i i n B A a i -== ，则M 的12n -个子集1122,,,n B B B - ，两两之交不空；()02、再证，对于M的任何121n -+个子集，其中必有两个子集不相交．设1122,,,n B B B - 是M 的12n -个不同子集，其中每个皆含n a ；用i B 表示子集i B 在M 中的补集，1(\),1,2,,2n i i B M B i -== ，则对于任意i j ≠，,i j i j B B B B ≠≠，并且j i B B ≠， （因前者含n a 而后者不含），故1122,,,n B B B - ，1122,,,n B B B - 为M 的全部2n个不同子集，现将上述集合搭配成为12n -对：()()()11122122,,,,,,n n B B B B B B -- ；任取M 的121n -+个子集，必有两个子集属于同一对，则这两个子集不相交．2、将前九个正整数1,2,,9 分成三组，每组三个数，使得每组中的三数之和皆为质数；求出所有不同分法的种数．证：()01、由于在1,2,,9 中，三个不同的数之和介于6和24之间，其中的质数有7,11,13,17,19,23这六个数，今将这六数按被3除的余数情况分为两类：{}7,13,19A =，其中每个数被3除余1；{}11,17,23B =，其中每个数被3除余2；假若所分成的,,A B C 三组数对应的和,,a b c p p p 为互异质数，则因12945a b c p p p ++=+++= 被3整除，故三个和数,,a b c p p p 必为同一类数，因为A 类三数和713193945++=<，B 类三数和1117235145++=>，矛盾！ 故三个和数中必有两个相等．()02、据()01知，将45表成7,11,13,17,19,23中的三数和（其中有两数相等），只有四种情况：()119197++；()2171711++；()3131319++；()4111123++．由于在1,2,,9 中有5个奇数，故分成的三组中必有一组，三数全为奇数，另两组各有一个奇数．对于情形()1，和为7的组只有{}1,2,4，剩下六数3,5,6,7,8,9，分为和为19的两组，且其中一组全为奇数，只有唯一的分法：{}3,7,9与{}5,6,8；对于情形()2，若三奇数的组为{}1,7,9，则另两组为 {}{}4,5,8,2,3,6；或{}{}3,6,8,2,4,5；若三奇数的组为{}3,5,9，则另两组为 {}{}2,8,7,1,4,6，或{}{}4,6,7,1,2,8； 若三奇数的组为{}1,3,7，则另两组为 {}{}2,6,9,4,5,8；共得分法5种；对于情形()3，若三奇数的组为{}3,7,9，则另两组为 {}{}1,4,8,2,5,6； 若三奇数的组为{}1,3,9，则另两组为 {}{}2,4,7,5,6,8或{}{}2,5,6,4,7,8； 若三奇数的组为{}1,5,7，则另两组为 {}{}3,4,6,2,8,9或{}{}2,3,8,4,6,9； 共得分法5种；对于情形()4，和为23的组只有{}6,8,9，则另两组为 {}{}1,3,7,2,4,5； 据以上，共计得到155112+++=种分法．3、设正整数a 的各位数字全由1和2组成，由其中任意() 2k k ≥个连续数位上的数字所组成的k 位数，称为数a 的一个“k 段”；若数a 的任两个“k 段”都不相同．证明：对于具有这种性质的最大正整数a ，其开初的一个“1k -段”和最后的一个“1k -段”必定相同.证：设12n a x x x = 是一个具有这种性质的最大正整数，由a 的最大性，在其后面无论添加1或2，所得到的1n +位数1121n a x x x = 以及2122n a x x x = 中，都有两个相同的“k 段”. 设在1a 中有 1121i i i k n k n x x x x x ++--+= ；在2a 中有1122j j j k n k n x x x x x ++--+= . 显然i j ≠，（因为11i k j k x x +-+-≠），且11i n k ≤≤-+，11j n k ≤≤-+，如果1i =或1j =，则直接去掉相应“k 段”中的末位数，可知结论成立；如果2i ≥且2j ≥，因 12212i i i k n k n j j j k x x x x x x x x ++--+++-== ，考虑各自的前一位数字111, , i j n k x x x ---+，它们只取1和2两个值，其中必有两数相同，于是数a 中有两个相同的“k 段”，矛盾. 因此,i j 中必有一个为1，故结论得证.4、将数集},...,,{21n a a a A =中所有元素的算术平均值记为)(A P ，（na a a A P n+++=...)(21）. 若B 是A 的非空子集，且)()(A P B P =，则称B 是A的一个“均衡子集”．试求数集}9,8,7,6,5,4,3,2,1{=M 的所有“均衡子集”的个数． 解：由于()5P M=，令{}{}54,3,2,1,0,1,2,3,4M x x M '=-∈=----，则()0P M '=, 依照此平移关系，M 和M '的均衡子集可一一对应．用()f k 表示M '的k 元均衡子集的个数，显然有(9)(1)1f f ==(M '的9元均衡子集只有M '，一元均衡子集只有{}0)．M '的二元均衡子集共四个，为{,},1,2,3,4i B i i i =-=, 因此(2)4f =． M '的三元均衡子集有两种情况：（1）含有元素0的为{0}{,0,},1,2,3,4i B i i i =-= , 共四个；（2）不含元素0的，由于等式312,413=+=+可表示为3120,3120-++=--=以及4130,4130-++=--=，得到4个均衡子集{3,1,2},{3,1,2},{4,1,3},{4,1,3}------，因此(3)448f =+=．M '的四元均衡子集有三种情况：（1）每两个二元均衡子集之并：,14i j B B i j ≤<≤ , 共6个集； （2）不含元素0的三元均衡子集与{}0的并集，共4个集；（3）以上两种情况之外者，由于等式1423+=+可表为14230--++=以及14230+--=得2个均衡子集{1,4,2,3}--与{1,4,2,3}--，因此()464212f =++=． 又注意到，除M '本身外，若B '是M '的均衡子集，当且仅当其补集''M C B 也是M '的均衡子集，二者一一对应. 因此(9)(),1,2,3,4f k f k k -==．从而M '的均衡子集个数为9411()(9)2()12(14812)51k k f k f f k ===+=++++=∑∑．即M 的均衡子集有51个．5、某校有2010名新生，每人至少认识其中n 人，试求n 的最小值，使得其中必存在彼此认识的16个人.解：记这2010个人的集合为{}122010,,,M v v v = ，i v 所认识的人的集合记为, 1,2,2010i A i = ，则i A n ≥，且 1,2,2010i i v A i ∉= ，若12,v v 是M 中相识的两人，则有121222010A A A A A B n =+-≥- ， 当220101n -≥，则有312v A A ∈ ，且123,,v v v 两两相识，而()123123123322010A A A A A A A A A n =+-≥-⋅ .当3220101n -⋅≥，则有4123v A A A ∈ ，且1234,,,v v v v 两两相识，而()123412341234432010A A A A A A A A A A A A n =+-≥-⋅ ，如此继续，得1215,,,v v v 两两相识，而151414151511115142010i i i i i i A A A A A n ===⎛⎫=+-≥-⋅ ⎪⎝⎭. 当151420101n -⋅≥，则有15161, i i v A =∈ 且1216,,,v v v 两两相识,而由151420101n -⋅≥，得142010115n ⋅+≥，n 为整数，则1877n ≥.再说明1877n =是最小的；若1876n =，我们可构造一种情形，使得M 中不存在相互认识的16个人．为此，将2010个人均分为1215,,,B B B 等15组，每组134个人，令同组的人互不相识，而异组的任两人皆相识，则M 中任一人v 所认识的人的个数皆为()141341876d v =⨯=，从M 中任取16个人，必有两个人属于这15组中的同一个组，于是这两人互不相识，因此M 中不存在相互认识的16个人.从而n 的最小值为1877.6、有()2nn ≥名运动员，其编号分别是1,2,,n ，在一次活动中，他们以任意方式站成了一排. 如果每次允许将其中一些人两两对换位置，但在同一轮操作过程中,任一人至多只能参与一次这种对换.证明：至多只需两轮这样的操作，可使队列变成1,2,,n 的顺序排列. 证明：对n 归纳，2≤n 时显然. 设n k ≤时结论成立；今证1n k =+时情形，设121,,...,k a a a +是1k +名运动员1,2,,1k + 的任一排法, （i ） 如果其中存在一组运动员()12,, (1)i i i a a a m k ≤≤，他们的编号恰好就是其位置序号组k i i i ,...,,21的一个排列，则由归纳假设，这组运动员可经至多两轮操作，分别到位于自然位置（使i 号运动员到位于i 位），而剩下的1k m +-个运动员，显然也是其所处位置号的排列，他们也可经过至多两轮对换到位于自然位置，这样，队列121,,...,k a a a +可经两轮对换化为1,2,,1k +（ii ） 若（i ）中的情形不出现，为叙述方便，设1号位置上所站的运动员编号为1b ， （11≠b ），1b 号位置上的运动员编号为2b ，（{}12,1b b ∉），2b 号位置上的运动员编号为3b ，（{}213,,1b b b ∉），...，j b 号位置上的运动员编号为1+j b ，（{}j j b b b ,...,,111∉+），...，k b 号位置上的运动员编号为1。

3.1题（宗传玉）某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也没有遇见的有5次，问某甲共参加了几次会议解:设A i为甲与第i个朋友相遇的会议集，i＝1，…，6．则故甲参加的会议数为:28+5=33.3.2题（宗传玉）求从1到500的整数中被3和5整除但不被7整除的数的个数.解:设A3：被3整除的数的集合A5：被5整除的数的集合A7：被7整除的数的集合所以3.3.题（宗传玉）n个代表参加会议，试证其中至少有2人各自的朋友数相等。

解:每个人的朋友数只能取0，1，…，n－1．但若有人的朋友数为0，即此人和其他人都不认识，则其他人的最大取数不超过n－2．故这n个人的朋友数的实际取数只有n－1种可能．，所以至少有２人的朋友数相等．3.4题（宗传玉）试给出下列等式的组合意义.解:(a) 从n 个元素中取k 个元素的组合，总含有指定的m 个元素的组合数为)()(kn m n mk m n --=--。

设这m 个元素为a 1,a 2,…,a m ,Ai 为不含a i 的组合（子集），i=1,…,m.()∑∑∑==∈⊄==⎪⎪⎭⎫⎝⎛-⎪⎪⎭⎫ ⎝⎛-=-+⎪⎪⎭⎫ ⎝⎛==⎪⎪⎭⎫ ⎝⎛--⎪⎪⎭⎫⎝⎛-=ml l m l l m i i lj i lk l n k m A k n k n m n k l n l j 01),(),...,(1m1i i i i i 1)1(A A A A 111213.5题（宗传玉）设有三个7位的二进制数：a1a2a3a4a5a6a7，b1b2b3b4b5b6b7，c1c2c3c4c5c6c7．试证存在整数i 和j，1≤i≤j≤7，使得下列之一必定成立：a i=a j=b i=b j，a i=a j=c i=c j，b i=b j=c i=c j．证：显然，每列中必有两数字相同，共有种模式，有０或１两种选择．故共有·2种选择．·2=6．现有7列，．即必有２列在相同的两行选择相同的数字，即有一矩形，四角的数字相等．3.6题（宗传玉）在边长为1的正方形内任取5个点试证其中至少有两点，其间距离小于证：把１×１正方形分成四个(1/2)×(1/2)的正方形．如上图.则这５点中必有两点落在同一个小正方形内．而小正方形内的任两点的距离都小于．3.7题（王星）在边长为1的等边三角形内任取5个点试证其中至少有两点，期间距离小于1/2．证：把边长为１的三角形分成四个边长为1/2的三角形，如上图：则这５点中必有两点落在同一个小三角形中．小三角形中任意两点间的距离都小于1/2．3.8题（王星）任取11个整数，求证其中至少有两个数它们的差是10的倍数。

第三章递推关系1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限区域数记为f(n),求f(n)满足的递推关系.解： f(n)=f(n-1)+2f(1)=2,f(2)=4解得f(n)=2n.2.n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求f(n)满足的递推关系.解：设a n-1a n-2…a1是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1)表示。

a n可以有两种情况：1）不管上述序列中是否有2，因为a n的位置在最左边，因此0和1均可选；2）当上述序列中没有1时，2可选；故满足条件的序列数为f(n)=2f(n-1)+2n-1 n 1,f(1)=3解得f(n)=2n-1(2+n).3.n位四进制数中,2和3出现偶数次的序列的数目记为f(n),求f(n)满足的递推关系.解：设h(n)表示2出现偶数次的序列的数目，g(n)表示有偶数个2奇数个3的序列的数目，由对称性它同时还可以表示奇数个2偶数个3的序列的数目。

则有h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1）f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2）将（1）得到的h(n)=(2n+4n)/2代入（2），可得f(n+1)= (2n+4n)/2-2f(n),f(1)=2.4.求满足相邻位不同为0的n位二进制序列中0的个数f(n).解：这种序列有两种情况：1)最后一位为0，这种情况有f(n-3)个；2)最后一位为1，这种情况有2f(n-2)个；所以f(n)=f(n-3)+2f(n-2)f(1)=2,f(2)=3,f(3)=5.5.求n位0,1序列中“00”只在最后两位才出现的序列数f(n).解：最后两位是“00”的序列共有2n-2个。

f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在n-1位第一次出现“00”的可能；f(n-1)表示在第n-1位第一次出现“00”的序列数，同时同时排除了在n-2位第一次出现“00”的可能；依此类推，有f(n)+f(n-1)+f(n-2)+…+f(2)=2n-2f(2)=1,f(3)=1,f(4)=2.6.求n 位0,1序列中“010”只出现一次且在第n 位出现的序列数f(n).解：最后三位是“010”的序列共有2n-3个。

组合优化与组合构造讲义林常§1.概述一.组合数学题型1.计数2.存在性3.构造4.最值二.主要方法1.递推与归纳.(1).I型归纳法.定跨度:起点个数等于跨度.不定跨度:起点个数等于1.递推关系的阶数与初始条件.(2).II型归纳法(最小数原理).设P(n)是关于正整数的命题.若由P(n)不成立可推出存在正整数n′<n使得P(n′)不成立.则P(n)对一切正整数成立.(3).倒推归纳法.设A是N*的无穷子集.若P(n)在A上成立,且由P(n)成立及n>1可推出P(n－1)成立.则P(n)对一切正整数成立.(4).乘积归纳法.若P(n)对全体素数成立,且由P(m)及P(n)成立可推出P(mn)成立.则P(n)对一切大于1的正整数成立.若P(n)对全体素数幂成立,且由P(m),P(n)成立及(m,n)=1可推出P(mn)成立.则P(n)对一切大于1的正整数成立.2.调整法(向较优目标逼近).设φ: S→R有最大(小)值(例如,当φ(S)为有限集或φ在紧集S上连续时).若S 的子集A满足:对任一x∈S\A,都有x′∈S使得φ(x′)>(<) φ(x).则φ的最大(小)值点在A中.3.化归(类比,对应)常用的化归模型:赋值(代数化),填表(二元关系),画图(几何,图论),剩余类(整除关系),不定方程解数.棋盘路线.Veen图.数量关系:设φ : A→B, A,B为有限集.则当φ为单射,满射,双射时分别有|A|≤|B|, |A|≥|B|, |A|=|B|.4.算两次(Fubini原理)从不同角度计算(估计)特征量的和数或特征形的个数.累次求和式的换序.由求和区域的边界定上下限.§2.组合优化(最值)一.优化方法(无表达式函数的最值)1.界的估计(对适当的特征量作合理的放缩)与实现(构造),或根据美学观点猜测最优对象再证明相应的不等式.2.调整法.在定义集内(保持约束条件)向较优方向(平均,极端,排序)逼近.离散最值(函数型,排序型)的基本手段.3.递推法二.例题选讲1.设a 1, a 2, ... , a 10是10个两两不同的正整数,它们的和为1995， 试求a 1a 2+a 2a 3+...+a 9a 10+a 10a 1的最小值。

中科⼤-组合数学复习知识点⼀、鸽巢原理定理：n+1个物品放⼊n个盒⼦中，那⾄少有 1 个盒⼦中⾄少有 2 个物品。

解题思路：构造部分和序列正整数a i=2s i×r i,s i为⾮负整数,r i为奇数加强形式：m个物品放⼊n个盒⼦中，⾄少有 1 个盒⼦中⾄少有mn个物品。

若物品数与盒⼦数相等，则⾄少 1 个盒⼦中⾄少有 1 个物品。

若m=n+1，则⾄少 1 ⼀个盒⼦中⾄少有 2 个物品。

解题思路：递增⼦序列问题：构造{m k},m k表⽰从a k开始的最长递增⼦序列长度将集合分成 n 部分，使⽤加强形式取余⼆、排列与组合2.1 集合的排列组合r排列=P(n,r)=A rn =n! (n−r)!r圆排列=1r P(n,r)=1r A rn=n!r(n−r)!r组合数=nr=C rn=n!r!(n−r)!定理：(n0)+(n1)+⋯+(nn)=2n解题思路：能被 3 整除的数，各位数字之和也要能被 3 整除2.2 多重集合定理：多重集合M={∞⋅a1,∞⋅a2,⋯,∞⋅a k}的r排列数为k r.定理：多重集合M={k1⋅a1,k2⋅a2,⋯,k n⋅a n}的全排列数为(k1+k2+⋯+k n)!k1!k2!⋯k n!.只适⽤全排列，如果 k 排列，则⽤指数型⽣成函数。

定理：多重集合M={∞⋅a1,∞⋅a2,⋯,∞⋅a k}的r组合数为(k+r−1r)=C rk+r−1.证明⽅法：对应求⾮负整数解⽅案数x1+x2+⋯+x k=r =>r 个相同的球放⼊ k 个不同的盒⼦中定理：多重集合M={∞⋅a1,∞⋅a2,⋯,∞⋅a k}，要求各元素⾄少出现⼀次的r组合数为(r−1k−1)=C k−1r−1.证明⽅法：对应求满⾜⼀定条件的整数解⽅案数x1+x2+⋯+x k=r,x i≥1例题：求⽅程x1+x2+x3+x4=18满⾜条件x1≥3,x2≥1,x3≥4,x4≥2的整数解数⽬。

解：令y1=x1−3,y2=x2−1,y3=x3−4.y4=x4−2，则原⽅程变为y1+y2+y3+y4=8的⾮负整数解数⽬，(8+4−1 8)⌈⌉()课后习题 13，不穿过直线y=x课后习题 13，不穿过直线y=x的⾮降路径数？三、⼆项式系数⼆项式定理：(x+y)n=x n+(n1)x n−1y+(n2)x n−1y2+⋯+y n=∑ni=0(ni)x n−i y i⽜顿⼆项式定理：(1+x)α=∑∞r=0(αr)x r,(αr)=α(α−1)⋯(α−r+1)r!,α为⼀切实数,|x|<1α=−n 时，有(αr)=(−1)r(n+r−1r)(1+x)−n=∑∞r=0(−1)r(n+r−1 r)x r(1−x)−n=∑∞r=0(n+r−1 r)x r(1+x)−1=1−x+x2−x3+⋯(1−x)−1=1+x+x2+x3+⋯α=12时，有(αr)=(−1)r−11r22r−1(2r−2r−1)(1+x)12=∑∞r=1(−1)r−11r22r−1(2r−2r−1)x r,Catalan数基本性质：对称关系：(nr)=(nn−r)递推关系：(nr)=(n−1r)+(n−1r−1)=C rn−1+C r−1n−1组合恒等式：C1 n +2C2n+3C3n+⋯+nC nn=n2n−1C k 0+C k1+C k2+⋯+C kn=C k+1n+1∑n i=0(C in)2=C n2n∑r i=0C imC r−in=C rm+n,Vandermonde恒等式∑m i=0C imC r+in=C m+rm+n多项式定理：(x1+x2+⋯+x t)n=∑(nn1n2⋯n t)x n11x n22⋯x n tt,(nn1n2⋯n t)=n!n1!n2!⋯n t!例题：展开 (2x1−3x2+5x3)6，则 x31x2x23系数为解：6!3!1!2!23(−3)52多项式定理性质：展开式项数为n1+n2+⋯+n t=n的⾮负整数解个数，为(n+t−1 n)∑(nn1n2⋯n t)=t n,令所有xi都为1四、容斥原理定理：|¯A1∩¯A2∩⋯∩¯A m|=|S|−∑|Ai|+∑|A i∩A j|+⋯+(−1)m|A1∩A2∩⋯∩A m|推论：|A1∪A2∪⋯∪A m|=|S|−|¯A1∩¯A2∩⋯∩¯A m|欧拉函数的证明欧拉函数表⽰⼩于 n 且与 n 互素的整数的个数n =p i 11p i 12⋯p iq q 记 A i ={x |x ≤n 且p i |x} ，表⽰与 p i 成倍数的那些数那么 φ(n)=|¯A 1∩¯A 2∩⋯∩¯A q |=n ∏q i=1(1−1p i )定义：N (P i 1,P i 2,⋯,P i k ) 表⽰ S 中具有性质 P i 1,P i 2,⋯,P i k的元素个数ω(k )=∑N (P i 1,P i 2,⋯,P i k) 表⽰具备 k 个性质的元素计数，其中⼀个元素会被多次计数。

组合数学中的生成函数理论生成函数是组合数学中的重要工具，它在数论、组合数学、离散数学等领域得到广泛应用。

生成函数可以将一个序列转化为一个多项式，通过运算和变换可以得到序列的各种性质和计算方法。

在组合数学中，生成函数理论被广泛用于解决计数问题、组合恒等式、递推关系等。

本文将介绍生成函数理论的基本概念和应用。

一、生成函数的定义和基本性质生成函数是一种特殊类型的函数，它将序列中的每个元素与变量的幂指数相对应。

设有序列 {a0, a1, a2, ...}，其生成函数定义为：G(x) = a0 + a1x + a2x^2 + ...生成函数可以是普通生成函数或指数生成函数，取决于序列元素的性质。

普通生成函数适用于有限序列，而指数生成函数适用于无限序列。

生成函数具有以下基本性质：1. 加法性：若序列 {a_n} 和 {b_n} 的生成函数分别为 G(x) 和 F(x)，则它们的和的生成函数为 G(x) + F(x)。

2. 乘法性：若序列 {a_n} 和 {b_n} 的生成函数分别为 G(x) 和 F(x)，则它们的乘积的生成函数为 G(x) * F(x)。

3. 幂次性：若序列 {a_n} 的生成函数为 G(x)，则 a_k 的生成函数为[G(x)]^k。

二、生成函数的应用生成函数理论在组合数学中有广泛的应用，以下是几个典型的应用例子：1. 计数问题：生成函数可以用于计算集合中元素的个数。

例如，设有一堆硬币，其中有若干个1元硬币和2元硬币，求总金额为n元的组合个数。

我们可以设定序列 {c_n} 表示总金额为n元的组合个数，得到其生成函数C(x)。

通过对序列的运算和变换，可以得到C(x) 的表达式，进而计算出总金额为n元的组合个数。

2. 组合恒等式：生成函数可以用于证明组合恒等式。

通过构造适当的生成函数，并利用生成函数的运算性质，可以证明一些看似复杂的组合恒等式。

这为组合数学的证明提供了简洁且直观的方法。

3. 递推关系：生成函数可以用于求解递推关系。

作业习题答案习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。

证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。

假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。

证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。

证明：方法一：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。

由鸽巢原理知，至少有2个坐标的情况相同。

又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。

因为奇数+奇数 = 偶数；偶数+偶数=偶数。

因此只需找以上2个情况相同的点。

而已证明：存在至少2个坐标的情况相同。

证明成立。

方法二：对于平面上的任意整数坐标的点而言，其坐标值对2取模后的可能取值只有4种情况，即：(0,0) ,(0,1) ,(1,0), (1,1)，根据鸽巢原理5个点中必有2个点的坐标对2取模后是相同类型的，那么这两点的连线中点也必为整数。

一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果证明：根据推论，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。

将一个矩形分成(m +1)行112m m +⎛⎫+⎪⎝⎭列的网格每个格子涂1种颜色，有m 种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。

证明：（1）对每一列而言，有（m+1）行，m 种颜色，有鸽巢原理，则必有两个单元格颜色相同。

（2）每列中两个单元格的不同位置组合有12m +⎛⎫⎪⎝⎭种，这样一列中两个同色单元格的位置组合共有 12m m +⎛⎫⎪⎝⎭种情况（3）现在有112m m +⎛⎫+⎪⎝⎭列，根据鸽巢原理，必有两列相同。