下载文档原格式
组合几何例讲 答案及讲稿（陶平生）基本内容与方法：组合计数；组合构造；组合结构；映射与对应；分类与染色；归纳与递推；容斥原理；极端原理；调整法；补集法；算两次；数形结合法，等等．1、矩形玻璃台板碎裂成一些小玻璃片，每块碎片都是凸多边形，将其重新粘合成原矩形后，有交结点30个，其中20个点在原矩形的周界上（包括原矩形的四个顶点），其余10点在矩形内部.在矩形的内部有45条粘缝（两个结点之间的线段算是一条粘缝，如图所示）. 试求该矩形台板所碎裂成的各种类型（指三角形、四边形、五边形等等）的碎片块数. （若凸多边形的周界上有n 个点，就将其算作n 边形）.解：设全部碎片中，共有三角形3a 个，四边形4a 个， … …，k 边形k a 个（34,,,k a a a 为非负整数），一个多边形，若其周界上有n 个顶点，就将其看成是n 边形，（例如图中的多边形ABCDE 要看成五边形）.于是这些多边形的内角和S 角为：S 角()3422k a a a k πππ=⋅+⋅++⋅-.从另一方面看，矩形内部有10个结点，对于每个点，围绕它的多边形顶角和为2,π10个内结点共获得102π⋅弧度；矩形边界线段内共有16个结点，在每个这种结点处，各多边形的顶角在此汇合成一个平角，16个这种结点共获得16π弧度；而原矩形的四个顶点处，共收集到多边形碎片的2π弧度.因此，S 角2016238ππππ=++=，于是，()342238k a a k a +++-= ……○1. 再计算边数和S 边：由于每个n 边形有n 条边，则S 边3434k a a ka =+++.另一方面，在矩形的内部的45条粘缝，每条都是两个多边形的公共边，故都计算了两遍，矩形周界上的20条线段各被计算了一遍，因此，S 边24520110=⋅+=，则3434110k a a ka +++= (2)○2-○1得，()34272k a a a +++=，因此碎片的块数为:3436k a a a +++= (3)○1—○3得，()4562332k a a a k a ++++-= …… ○4. 注意所有i a 为非负整数，故670k a a a ====，4522a a += (5)○5式中，或者452, 0a a ==；或者450, 1a a ==，……○6. 因此由○3、○5、○6得，本题的解共有两种情况：即全部碎片共36块，其中，或含有34个三角形，2个四边形；或含有35个三角形，1个五边形.2、将圆周2011等分于点122011,,,A A A ，在以其中每三点为顶点的三角形中，求含有圆心的三角形的个数．解：一般地讨论圆周21n +等分的情况，任取其中一个分点，记为P ，然后将其余2n 个分点这样标志，自P 点后， 反时针方向的连续n 个点依次记为12,,,n A A A ； 顺时针方向的连续n 个点依次记为12,,,n B B B ；先考虑以P 为顶点且含有圆心的三角形，如图，显然，这种三角形的另两个顶点必须一个属于点集{}12,,,n A A A ，而另一个属于点集{}12,,,n B B B ．且这种i j PA B ∆含有圆心当且仅当1i j n +≥+，{},1,2,,i j n ∈，今计算合于条件的三角形个数：当i k =时，j 可取值,1,,1n n n k --+，共计k 个值，因此这种含有圆心的n n3i j PA B ∆个数为()1112nk k n n ==+∑，当点P 取遍21n +个位置，共得 ()()11212n n n +⋅+个三角形，由每个三角形有三个顶点，故每个三角形重复计算了三遍，因此，合于条件的三角形个数为()()1216n n n ++．3、在一个圆周上给定十二个红点；求n 的最小值，使得存在以红点为顶点的n 个三角形，满足：以红点为端点的每条弦，都是其中某个三角形的一条边．解：设红点集为：{}1212,,,A A A A =，过点1A 的弦有11条，而任一个含顶点1A 的三角形，恰含两条过点1A 的弦，故这11条过点1A 的弦，至少要分布于6个含顶点1A 的三角形中；同理知，过点(2,3,,12)i A i =的弦，也各要分布于6个含顶点i A 的三角形中，这样就需要12672⨯=个三角形，而每个三角形有三个顶点，故都被重复计算了三次，因此至少需要72243=个三角形． 再说明，下界24可以被取到．不失一般性，考虑周长为12的圆周，其十二等分点为红点，以红点为端点的弦共有21266C =条．若某弦所对的劣弧长为k ，就称该弦的刻度为k ；于是红端点的弦只有6种刻度，其中，刻度为1,2,,5的弦各12条，刻度为6的弦共6条；如果刻度为,,a b c （a b c ≤≤）的弦构成三角形，则必满足以下两条件之一：或者a b c +=；或者12a b c ++=；于是红点三角形边长的刻度组(),,a b c 只有如下12种可能：()()()1,1,2,2,2,4,3,3,6,()()()()()()()()()2,5,5,1,2,3,1,3,4,1,4,5,1,5,6,2,3,5,2,4,6,3,4,5,4,4,4；下面是刻度组的一种搭配：取()()()1,2,3,1,5,6,2,3,5型各六个，()4,4,4型四个；这时恰好得到66条弦，且其中含刻度为1,2,,5的弦各12条，刻度为6的弦共6条；今构造如下：先作()()()1,2,3,1,5,6,2,3,5型三角形各六个，再用()4,4,4等型来补充． ()1,2,3型六个：其顶点标号为：{}{}{}{}{}{}2,3,5,4,5,7,6,7,9,8,9,11,10,11,1,12,1,3； ()1,5,6型六个：其顶点标号为：{}{}{}{}{}{}1,2,7,3,4,9,5,6,11,7,8,1,9,10,3,11,12,5；3()2,3,5型六个：其顶点标号为：{}{}{}{}{}{}2,4,11,4,6,1,6,8,3,8,10,5,10,12,7,12,2,9；()4,4,4型三个：其顶点标号为：{}{}{}1,5,9,2,6,10,3,7,11；()2,4,6型三个：其顶点标号为：{}{}{}2,8,12,6,12,4,4,10,8．（每种情况下的其余三角形可由其中一个三角形绕圆心适当旋转而得）． 这样共得到24个三角形，因此，n 的最小值为24．4、在一个圆周上给定8个点128,,,A A A ．求最小的正整数n ，使得以这8个点为顶点的任意n 个三角形中，必存在两个有公共边的三角形．解：先考虑两两无公共边的三角形个数的最大值r ．八个点，每两点连一条弦，共得2828C =条弦，若每条弦只属于一个三角形，则这些弦至多能构成两两无公共边的三角形个数2893r ⎡⎤≤=⎢⎥⎣⎦个，但若有9个这样的三角形，共得27个顶点，则八边形必有一顶点，至少属于4个三角形，设为8A ，共顶点8A 的4个三角形，8A 的对边都是127,,,A A A 之中的两点连线，其中必有一点，设为k A ，出现了两次，那么相应的两个三角形将有一条公共边8k A A ，这不可能；故8r ≤．另一方面，当8r =时，我们确实可以作出这样的8个三角形，使得其中任两个三角形都无公共边；注意这样的8个三角形，共产生24个顶点，若使每点所参与的三角形个数都小于4，那么每点恰好属于3个三角形，也就是说，每个点，恰与其余七点中的6点有边相连，而与另一点不连边；考虑每点度数皆为6的八阶图G ：为简明起见，取圆周的八等分点作为图G 的八个顶点，作8阶完全图，然后去掉其中4条直径，这样共得24条边，且每点均属于6条边；在由这些边所构成的三角形中，选取八个等腰三角形： (1,2,3),(3,4,5),(5,6,7),(7,8,1)以及 (1,4,6),(3,6,8),(5,8,2),(7,2,4)，它们两两无公共边；（每一组的四个三角形，皆可由其中一个三角形绕圆心适当旋转而得到）．因此，8r =，从而所求的最小值19n r =+=．5、试确定，是否能将1,2,,10这十个数分别标于五角星的十个结点上，使得每一条边上的四个数之和都相等？证明你的结论．解：不能．反证法，假若有一种填法，使得五角星每条边上的四数之和都相等，记此和值为S ，则由于五角星的任两条边都相交，每一点恰有两条边经过，则52(1210)110S =+++=，所以，22S =．即每条边上的四数之和皆为22．先证明，10与1必共线，事实上，假若10与1不共线，考虑经过10的两根线，设10所在的一条线上的四数为12310,,,x x x ，另一条线上的四数为12310,,,y y y ，则123123442(10)(10)S x x x y y y ==+++++++12312320()x x x y y y =++++++20(234567)47≥++++++=，矛盾！故10与1必共线．下面用两种方法证明本题结论：方法一：记10与1所共的线为l ，l 上所填的另两数设为12,a a ，则1211a a +=，它有四种情况：{}{}{}{}{}12,2,9,3,8,4,7,5,6a a =；数10所在的另一根线记为10l ，10l 上的另三数设为123,,b b b ，则12312b b b ++=，它有三种情况：{}{}{}{}123,,2,3,7,2,4,6,3,4,5b b b =；数1所在的另一根线记为1l ，1l 上的另三数设为123,,c c c ，则12321c c c ++=，它有三种情况：{}{}{}{}123,,5,7,9,6,7,8,4,8,9c c c =；由于110,,l l l 两两之间恰有一个公共点，假若{}1,10,2,9l =，则{}{}1101,6,7,8,10,3,4,5l l ==，而110l l =∅，矛盾！ 假若{}1,10,3,8l =，则{}{}1101,5,7,9,10,2,4,6l l ==，而110l l =∅，矛盾！ 假若{}1,10,5,6l =，则{}{}1101,4,8,9,10,2,4,6l l ==，而110l l =∅，矛盾！假若{}1,10,4,7l =，则1l 与10l 各有两个点在l 上，这时110,,l l l 三线重合，矛盾！ 因此所述结论成立．方法二：删去10所在的两根线（1所在的点也被删去），五角星上剩下不共线的三个点，它们构成ABC ∆，这三顶点的填数和为：55222121a b c ++=-⨯+=．ABC ∆恰有一条边在1l （1所在的另一线）上，即1l 上有异于1的两点是ABC ∆的两个顶点，设为,B C ，1l 上的另一点记为D ，由于1l 上除1之外的另三数的和也是21，设点D 上的填数为d ，那么21a b c b c d ++==++，所以a d =，矛盾！（因D 在边BC 上而,,A B C 不共线），因此所述结论成立．6、两个正三角形交叠成一个六角星（如图），现将前12个正整数1,2,,12分别填于图中的12个结点处，使得每条直线上所填的四数之和相等．()01、试求六角星的六个顶点126,,,a a a 处填数之和的最小值；()02、证明适合条件的不同填数方案有偶数个．（对于填数方案π与T ，若方案π经旋转、翻转后能与方案T 重合，则认为是相同的填数方案）()01、解：对于满足条件的任一填法，将点ia 处所填的数仍记为ia ，1,2,,12i =，若每条直线上的四数之和为s ，则由()621212s =+++，得到26s =；在135a a a ∆的三条边上，有()()()1893310115512713a a a a a a a a a a a a s +++++++++++= ……○1 在246a a a ∆的三条边上，有()()()2910441112667823a a a a a a a a a a a a s +++++++++++= ……○2 两式相减得 135246a a a a a a ++=++ ……○3，由此知，两个三角形顶点处填数之和相等，若记 ()()135246m a a a a a a =+++++，则m 为偶数． 因为在1,2,,12中，最小的六数之和12621+++=为奇数，则22m ≥．若22m =，由于在1,2,,12中，和为22的六数只有1,2,3,4,5,7，将其分为和相等的两组，每组三个数，只有唯一的分法： {1,3,7}与{2,4,5}．今忽略外圈的具体数字，而将{1,3,7}与{2,4,5}分别改记为{奇，奇，奇}与{偶，偶，奇}，那么在旋转意义下，六个顶点处的填字方式唯一.现在再来考虑内圈六数的填法，用记号a b 表示整数,a b 同奇偶，由于每线上四数之和s 为偶数，则987121011 , a a a a a a ，而在内圈六数6,8,9,10,11,12之中，恰有四个偶数，两个奇数，因此{}{}1011, 9, 11a a =，由于1011, a a 落在奇顶三角形的一条边上，该边两顶点的填数之和应是()9116s -+=，但是在{}1,3,7中不存在和为6的两个数，矛盾。
第一章答案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。
习题一（排列与组合）1．在1到9999之间，有多少个每位上数字全不相同而且由奇数构成的整数？解：该题相当于从“1，3，5，7，9”五个数字中分别选出1，2，3，4作排列的方案数；（1）选1个，即构成1位数，共有15P 个；（2）选2个，即构成两位数，共有25P 个；（3）选3个，即构成3位数，共有35P 个；（4）选4个，即构成4位数，共有45P 个；由加法法则可知，所求的整数共有：12345555205P P P P +++=个。
2．比5400小并具有下列性质的正整数有多少个？（1）每位的数字全不同；（2）每位数字不同且不出现数字2与7；解：（1）比5400小且每位数字全不同的正整数；按正整数的位数可分为以下几种情况：① 一位数，可从1～9中任取一个，共有9个；② 两位数。
十位上的数可从1～9中选取，个位数上的数可从其余9个数字中选取，根据乘法法则，共有9981⨯=个；③ 三位数。
百位上的数可从1～9中选取，剩下的两位数可从其余9个数中选2个进行排列，根据乘法法则，共有299648P ⨯=个；④ 四位数。
又可分三种情况：⏹ 千位上的数从1～4中选取，剩下的三位数从剩下的9个数字中选3个进行排列，根据乘法法则，共有3942016P ⨯=个；⏹ 千位上的数取5，百位上的数从1～3中选取，剩下的两位数从剩下的8个数字中选2个进行排列，共有283168P ⨯=个；⏹ 千位上的数取5，百位上的数取0，剩下的两位数从剩下的8个数字中选2个进行排列，共有2856P =个；根据加法法则，满足条件的正整数共有：9816482016168562978+++++=个；（2）比5400小且每位数字不同且不出现数字2与7的正整数；按正整数的位数可分为以下几种情况：设{0,1,3,4,5,6,8,9}A =① 一位数，可从{0}A -中任取一个，共有7个；② 两位数。
十位上的数可从{0}A -中选取，个位数上的数可从A 中其余7个数字中选取，根据乘法法则，共有7749⨯=个；③ 三位数。
习题三（递推关系）1．解下列递推关系：（1）120171000,1n n n a a a a a ---+=⎧⎨==⎩ （2）12016900,1n n n a a a a a --++=⎧⎨==⎩ （3）20100,2n n a a a a -+=⎧⎨==⎩ （4）120121n n n a a a a a --=-⎧⎨==⎩ （5）123012990,1,2n n n n a a a a a a a ---=+-⎧⎨===⎩ 解：（1）对应的特征方程为：27100x x -+=，解得122,5x x ==。
所以齐次递推方程的通解为：25n n n a A B =+，代入初始条件，得：00a A B =+=，1251a A B =+=，解得：11,33A B =-=， 故 112533n n n a =-+。
（2）对应的特征方程为：2690x x ++=，解得：123x x ==-，所以，齐次递推方程的通解为：()(3)n n a A Bn =+-，代入初始条件，00a A ==，1()(3)1a A B =+-=，解得：10,3A B ==-，故1(3)3n n a n =--。
（3）对应的特征方程为：210x +=，解得：12,x i x i ==-，所以，齐次递推方程的通解为：()()n n n a A i B i =+-，代入初始条件，00a A B =+=，12a A i B i =-=，解得：,A i B i =-=，故 11()()n n n a i i --=+-。
（4）对应的特征方程为：2210x x -+=，解得：121x x ==，所以，齐次递推方程的通解为：n a A Bn =+，代入初始条件，01a A ==，11a A B =+=，解得：1,0A B ==，故 1n a =。
（5）对应的特征方程为：32990x x x --+=，解得：1231,3,3x x x ===-，所以，齐次递推方程的通解为：3(3)n n n a A B C =++-，代入初始条件，00a A B C =++=，1331a A B C =+-=，2992a A B C =++=， 解得，111,,4312A B C =-==-，故 1113(3)412n n n a -=-+--2．求由A ，B ，C ，D 组成的允许重复的排列中AB 至少出现一次的排列数。
第1章 排列与组合1.1 从{1,2,…,50}中找一双数{a,b}，使其满足：()5;() 5.a ab b a b -=-≤[解] (a) 5=-b a将上式分解，得到55a b a b -=+⎧⎨-=-⎩a =b –5，a=1，2，…，45时，b ＝6，7，…，50。
满足a=b-5的点共50-5=45个点. a = b+5，a=5，6，…，50时，b ＝0，1，2，…，45。
满足a=b+5的点共45个点. 所以，共计2×45=90个点. (b) 5≤-b a(610)511(454)1651141531+⨯+⨯-=⨯+⨯=个点。
1.2 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？ (b) 女生两两不相邻有多少种不同的排列？(c) 两男生A 和B 之间正好有3个女生的排列是多少？[解] (a) 女生在一起当作一个人，先排列，然后将女生重新排列。
（7＋1）!×5!=8!×5!＝40320×120=4838400(b) 先将男生排列有7!种方案，共有8个空隙，将5个女生插入，故需从8个空中选5个空隙，有58C 种选择。
将女生插入，有5!种方案。
故按乘法原理，有：7!×58C ×5!=33868800(种)方案。
(c) 先从5个女生中选3个女生放入A ，B 之间，有35C 种方案，在让3个女生排列，有3!种排列，将这5个人看作一个人，再与其余7个人一块排列，有(7+1)! = 8!由于A ，B 可交换，如图**A***B** 或 **B***A**故按乘法原理，有：2×35C ×3!×8!=4838400（种）1.3 m 个男生，n 个女生，排成一行，其中m ，n 都是正整数，若(a) 男生不相邻(m ≢n+1)； (b) n 个女生形成一个整体； (c) 男生A 和女生B 排在一起； 分别讨论有多少种方案.[解] (a) 先将n 个女生排列，有n!种方法，共有n+1个空隙，选出m 个空隙，共有mn C 1+种方法，再插入男生，有m!种方法，按乘法原理，有：n!×mn C 1+×m!＝n!×)!1(!)!1(m n m n -++×m!=)!1()!1(!m n n n -++种方案。
习题二（母函数及其应用）1．求下列数列的母函数(0,1,2,)n =（1）(1)n a n ⎧⎫⎛⎫-⎨⎬ ⎪⎝⎭⎩⎭；（2）{5}n +； （3）{(1)}n n -； （4）{(2)}n n +；解：（1）母函数为：00()(1)()(1)nn n a n n a a G x x x x n n ∞∞==⎛⎫⎛⎫=-=-=- ⎪ ⎪⎝⎭⎝⎭∑∑；（2）母函数为：22554()(5)5(1)1(1)nnn n n n x xG x n x nx x x x x ∞∞∞===-=+=+=+=---∑∑∑； ♦ 方法二：()()()001022()(5)14414111114541(1)1nnnn n n n n G x n x n x x x x x x x x x x ∞∞∞===∞+==+=++''⎛⎫=+=-+⎪---⎝⎭-=+=---∑∑∑∑ （3）母函数为：2323000222()(1)(1)2(1)(1)(1)nnnn n n x x x G x n n x n n x nx x x x ∞∞∞====-=+-=-=---∑∑∑； ♦ 方法二：()()()()()2202222002222023()(1)00121121nn n n nn n n n n G x n n x xn n xxn n x xx x x x x x x x ∞∞-==∞∞+==∞+==-=++-"=++=""⎛⎫⎛⎫== ⎪⎪-⎝⎭⎝⎭=-∑∑∑∑∑（4）母函数为：232300023()(2)(1)(1)(1)(1)nnnn n n x x x x G x n n x n n x nx x x x ∞∞∞===-=+=++=+=---∑∑∑。
♦ 方法二：()()()()()()()()00212100023223()(2)1211111121111111131nnnnn n n n n n n n n n n n G x n n x n n x n x x x x x x x xx x x x x x x x x x x ∞∞∞∞====∞∞∞∞++++=====+=++-+-"'"'⎛⎫⎛⎫=--=-- ⎪ ⎪--⎝⎭⎝⎭"'⎛⎫⎛⎫=--=-- ⎪ ⎪----⎝⎭--⎝⎭-=-∑∑∑∑∑∑∑∑2．证明序列(,),(1,),(2,),C n n C n n C n n ++ 的母函数为 11(1)n x +- 。
