组合数学参考答案卢开澄第四版-修改版

111题从1，2，50中找两个数A，B，使其满足（1）|AB|5；（2）|AB|5；解（1）由|AB|5AB5或者AB5，由列举法得出，当AB5时，两数的序列为（6，1）（7，2）（50，45），共有45对。当AB5时，两数的序列为（1，6），（2，7）（45，50）也有45对。所以这样的序列有90对。（2）由题意知，|AB|5|AB|1或|AB|2或|AB|3或|AB|4或|AB|5或|AB|0；由上题知当|AB|5时有90对序列。当|AB|1时两数的序列有（1，2），（3，4），（2，1）（1，2）（49，50），（50，49）这样的序列有49298对。当此类推当|AB|2，序列有48296对，当|AB|3时，序列有47294对，当|AB|4时，序列有46292对，当|AB|0时有50对所以总的序列数90989694925052012题5个女生，7个男生进行排列，A若女生在一起有多少种不同的排列B女生两两不相邻有多少种不同的排列C两男生A和B之间正好有3个女生的排列是多少解（A）可将5个女生看作一个单位，共八个单位进行全排列得到排列数为85，（B）用X表示男生，Y表示空缺，先将男生放置好，共有8个空缺，YXYXYXYXYXYXYXY在其中任取5个得到女生两两不相邻的排列数C（8，5）75（C）先取两个男生和3个女生做排列，情况如下6若A，B之间存在0个男生，A，B之间共有3个人，所有的排列应为P6C5,33821若A，B之间存在1个男生，A，B之间共有4个人，所有的排列应为P1C5,1C5,34722若A，B之间存在2个男生，A，B之间共有5个人，所有的排列应为P2C5,2C5,35623若A，B之间存在3个男生，A，B之间共有6个人，所有的排列应为P3C5,3C5,36524若A，B之间存在4个男生，A，B之间共有7个人，所有的排列应为P4C5,4C5,37425若A，B之间存在5个男生，A，B之间共有8个人，所有的排列应为P5C5,5C5,3832所以总的排列数为上述6种情况之和。13题M个男生，N个女生，排成一行，其中M,N都是正整数，若A男生不相邻BN个女生形成一个整体；C男生A和女生B排在一起；1分别讨论有多少种方案。解A可以考虑插空的方法。N个女生先排成一排，形成N1个空。因为正好M个男生可以插在N1个空中，形成不相邻的关系。1N则男生不相邻的排列个数为PNM1BN个女生形成一个整体有N种可能，把它看作一个整体和M个男生排在一起，则排列数有M1种可能。因此，共有种可能。1C男生A和女生B排在一起，因为男生和女生可以交换位置，因此有2种可能，A、B组合在一起和剩下的学生组成排列有MN1这里实际上是MN2个学生和AB的组合形成的种可能。共有组合数为1N14题26个英文字母进行排列，求X和Y之间有5个字母的排列数解C（24，5）1315题求3000到8000之间的奇整数的数目，而且没有相同的数字。解根据题意，千位可以从3，4，5，7，6中选取，个位可以从1，3，5，7，9中选取；因此25873487123216题计算，112233。NN解由序数法公式可知11222111333221114NNN1N1。22111N1所以112233。NNN117题试证被2N除尽。1N证明因22122121NNNN因为2N1是整数所以能被2N除尽。18题求和的公因数数目。403解因为1034055130240360355它们最大公因子为转化为求最大公因子能除尽的整数个数，能除尽它的整数是2,2BABA根据乘法法则，能除尽它的数个数为4131127119题试证的正除数的数目是奇数。N证明设有,则一定有表达式，20,N2NAB则可知符合范围的和必成对出现，所以为偶数。又当ABN时，表达式AB仍然成立。所以的正除数的数目是“偶数”为奇数。21110题证任一正整数N可唯一地表成如下形式,0AII,I1,2,。证对N用归纳法。先证可表示性当N0,1时，命题成立。假设对小于N的非负整数，命题成立。对于N,设KNK1,即0NKKK由假设对NK,命题成立，设，其中AKK1,，命题成立。再证表示的唯一性设,不妨设AJBJ,令JMAXI|AIBIAJJAJ1J1A11BJJBJ1J1B11,矛盾，命题成立。IIIIABJIIIJ111题证明NCN1,RR1CN,R1,并给予组合解释证1111,1,NRNRNNCRRCNRR所以左边等于右边组合意义等式左边N个不同的球，先任取出1个，再从余下的N1个中取R个；等式右边N个不同球中任意取出R1个，并指定其中任意一个为第一个。所以两种方案数相同。112题证明等式112,NKC证明111101,0,2NNNNKKSCNCNL等式左边右边113题有N个不同的整数，从中间取出两组来，要求第1组的最小数大于另一组的最大数。解题思路（取法由大到小）第1步从N个数由大到小取一个数做为第一组，其它N1个数为第二组，组合数为C（N,1）CN1,1CN1,2CN1,N1第2步从N个数由大到小取两个数做为第一组，其它N2个数为第二组，组合数为C（N,2）CN2,1CN2,2CN2,N2第N2步从N个数由大到小取N2个数做为第一组，其它2个数为第二组，组合数为C（N,N2）C2,1第N1步从N个数由大到小取N1个数做为第一组，其它1个数为第二组，组合数为C（N,N1）C1,13总的组合数为,1,1,21,2,12,2,CNCNNCNCNN114题6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少种方案解第1步从特定引擎对面的3个中取1个有C3,1种取法，第2步从特定引擎一边的2个中取1个有C2,1种取法，第3步从特定引擎对面的2个中取1个有C2,1中取法，剩下的每边1个取法固定。所以共有C3,1C2,1C2,112种方案。115题求1至1000000中0出现的次数。解当第一位为0时，后面6位组成的数可以从1100000，共100000个0；当第二位为0时，当第一位取09时，后面5位可以取19999，此外当第一位取0时，后面5位还可以取为10000，这样共有999910199991个0；同理第三位为0时，共有99901个0；第四位为0时，共有99001个0；第五位为0时，共有90001个0；第六位为0时，只有1个0；这样总共的0数为100000999919990199001900011488895。116题N个相同的球放到R个不同的盒子里，且每个盒子里不空的放法。解如果用“O”表示球，用“|”表示分界线，就相当于用R1个“|”把N个“O”分成R份，要求是每份至少有一个球。如下图所示00|00000000|00000000|00000|000000对于第一个分界线，它有N1种选择，对于第二个分界线只有N2个选择，因为分界线不能相临，如果相临它们之间就没有了球，这不合要求，依次第R1个分界线只有NR1种选择。但是这样的分法中存在重复，重复度为R1,所以总得放法为N1N2NR1/R1CN1,R1。118题8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案解要求空盒不相邻，这样球的位置共有8种。而不同标志的球的排列有。所以共有85种排列。5P8种排列如下两类。因为要求空盒不相邻，途中1代表球A1111B1111在A中剩下的一个球有四种位置，B中剩下的一个球也有四种位置，两者合起来一共有8种117题和都是正整数，而且，试证下列等式NRNR111111,NNNRRRRRRNNNRRABCDEPPPL解A等式成立。NRRRB等式成立。NRN11C等式成立。PPRRNRD1111NNRRNNRPE利用D的结论可证明本题。111121111NRRNRRRRNRRRRRNPPLL119题NM位由M个0，N个1组成的符号串，其中NM1,试问不存在两个1相邻的符号串的数目。4解M个0进行排列，留出M1个空挡，任选N个空挡放1，共有CM1,N种方案121题一个盒子里有7个无区别的白球，5个无区别的黑球，每次从中随机取走一个球，已知前面取走6个，其中3个是白的，试问取第6个球是白球的概率。解C（6,2）C5,2C5,3/C5,3C7,3C6,33/14120题甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志占5人，试问有多少中方案解1甲单位出4个男同志，乙单位出1个男同志，从乙单位出2个女同志C10,4C15,1C10,21417502甲单位出3个男同志，乙单位出2个男同志，从甲单位出1个女同志,从乙单位出1个女同志。C10,3C15,2C41C10,15040003甲单位出2个男同志，乙单位出3个男同志，从甲单位出2个女同志C10,2C15,3C4,2122850123即为所求，总的方案数为768600122题求图122中从O到P的路经数A路径必须经过A点B路径必须过道路ABC路径必须过A和CD道路AB封锁但A,B两点开放解A分两步走O0,0A3,2A3,2P8,5，根据乘法法则56032NB分两步走O0,0A3,2,B4,2P8,5，根据乘法法则350423NC分三步走O0,0A3,2,A3,2C6,3,C6,3P8,5,根据乘法法则24012N（D）AB封锁路径数加必经AB路径数即O0,0P8,5的所有路径数有加法法则可得9375012834258N123题令S1,2,N1,N2,TX,Y,Z|X,Y,ZS,XR得CM,0CM,NCM,NCN,0同理CM,1CM1,N1CM,NCN,1CM,NCMN,0CM,NCN,N8由上知左边CN,0CN,1CN,NCM,N由CN,0CN,1CN,2CN,NNXYNX1NY2NXYNY令XY1可得CN,0CN,1CN,2CN,N左边2NCM,N右边命题得证。N140题从N个人中选R个围成一圆圈，问有多少种不同的方案解圆排列共有PN,R/R种不同的方案。148题在由N个0及N个1构成的字符串中，在任意前K个字符中，0的个数不少于1的个数的字符串有多少解转化为格路问题弱领先条件,即从0,0到N,N,只能从对角线上方走,可以碰到对角线,故方案数为C2N,NC2N,N1。142题A按照141的要求，写出邻位对换法（排列的生成算法之二）的相应算法B写出按照邻位对换法由给定排列生成其下一个排列的算法解1给定排列求相应序号设INTI为每一排列的对应序号I1（初始化）假定A1N和E2N；D2N；B1N都是整数数组，其中B1N为给定序列123S1Q0ANBI1KIIDIES从到作始，终；判断是否与相等若相等则输出值否则；从降到作始KEPKP10,Q若则作否则作始若则作始终2PRAP11S否则作始转终终终2给定序号求相应排列设INTI为每一排列的对应序号I1（初始化）M为给定序列号MN假定A1N和E2N；D2N；都是整数数组123S1Q0II1NAIKAINIDIEIMS从到作始，终；判断是否与相等若相等则从到输出；否则；从N2DKEPDKP01,Q降到作始若则作否则作始若则作始终2PRAP1S否则作始转终终终A由给定排列生成其下一个排列的算法。转指向；大的数一律改变箭头的比数互换位置。和它箭头所指一侧相邻，设为的数值最大者，求处于活动状态各数中停止。中无一处于活动状态则若在生成下一个排列从排列1211SMP143题对于给定的正整数N，证明，当时，CN,K是最大值。12NK或若是奇数若是偶数证明要证明C（N，K）是最大值，只需证明C（N，K）大于C（N，K1）即可根据以往证明大小值的经验，可以用相减或是相除的方法来证明，就此题，相减不合适，采用相除可以消除等式中的一些项C（N，K）/C（N，K1）（N/K（NK）（K1）（NK1）/N）（NK1）/K当N为偶数，KN/2时（NK1）/K（N2）/N）（2/N）（N2）/N1当N为奇数,KN1/2时（NK1）/KN3/22/N114/N11当N为奇数,KN1/2时（NK1）/KN122/N119综上所述,当N取以上三种情况,C（N，K）取最大值146题证明在由字母表0,1,2生成的长度为N的字符串中A0出现偶数次的字符串有个；312NB，其中131220NNNQ2Q证A归纳法当N1时,0出现偶数次的字符串有311/22个即1,2,成立。假设当NK时,0出现偶数次的字符串有3K1/2种。总的字符串有3种。0出现奇数次的字符串有3K1/2种。当NK1时，0出现偶数次的字符串包括两部分NK时,0出现偶数次再增加一位不是0的，共有23K1/2种，0出现奇数次再增加一位0,共有3K1/2种。所以共有23K1/23K1/23K11/2种，证毕。B等式左边第M项是0出现M次的字符串数，总和就是0出现偶数次的字符串数，右边由A得是0出现偶数次的字符串数，两边显然相等。144题（A）用组合方法证明和都是整数。（B）证明是整数。N2N312N解A方法一因为所以12N122NNN是整数，因此是整数。12NN2方法二设有2N个不同球放入N个不同的盒子里，每盒两个，这个方案数应该是整数。对2N个球进行排列得到方案数为2N。而把2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，N个盒子内部的排列共重复计算了2次。得到2N个不同球放入N个不同的盒子里，每盒两个的方案数N2若有3N个不同的球,放入N个不同盒子,每个盒子放三个，这个方案应该是整数。对这3N个球进行排列得到方案数为3N。而把3个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，N个盒子内部的排列共重复计算了3次。得到3N个不同的球放入N个不同的盒子里，每盒三个的方案数NN23B有个不同的球，放入N个相同的盒子里，每盒N个，求方案数，方案数应该是一个整数。2按前面A的方法，应该得到N2/NN是整数。另外由于N个盒子相同，放入不同的盒子是没有区别的，应该把N个盒子的排列数N除去。因此得到N2/NN1是整数。149题在1到N的自然数中选取不同且互不相邻的K个数,有多少种选取方案解设从1N中选取互不相邻的K个数的方案为GN,K。若选N，则方案为GN2,K1,若不选N,则方案数位GN1,K显然GN,KGN2,K1GN1,K，且只有当N2K1时,GN,K0,否则GN,K0,可给定初始值G2K1,K1,G2K2,K0145题A在2N个球中，有N个相同求从这2N个球中选取N个的方案数B在3N1个球中，有N个相同求从这3N1个球中选取N个的方案数解A）有N个相同就有N个不相同取N个不相同和0个相同的为CN,N,取N1个不相同的球和1个相同的球为CN,N1，等等。所以总的方案数为NCC2,1,解B）方法同上，方案数为C,02由于C2N1,0C2N1,2N1,C2N1,NC2N1,N112,2,12NNNC10则21221,021,21,NNCNNCN147题5台教学机器M个学生使用，使用第一台和第二台的人数相等，有多少种分配方案解当使用第1台机器的学生为N个时，使用第2台机器的学生也为N,从M个学生中选出2N个使用这两台机器，剩余的学生可以任意使用剩下的机器的组合数为CM,2NC2N,N3M2N。所以总的方案数为23,2,02QCQNNM150题1在有5个0，4个1组成的字符串中，出现01或10的总次数为4的字符串，有多少个2在有M个0，N个1组成的字符串中，出现01或10的总次数为K的字符串，有多少个解1、先将5个00000排成一排，1若插在两个0中间，即“010”则出现2个“01”或“10”；若插在两端，则出现1个“01”或“10”；要使出现“01”，“10”总次数为4，有两种办法1、把两个1插入0的空当内，剩下的1插入1的后面（类似010111000）。2、把1个1插入0的空当，再取两个1分别插入两端，剩下的1插入1的前面。（类似10100011）。由1和2得303424C2、M个0产生M1个空当。若K为偶数时要得到出现“01”与“10”总次数为K，可以先按上题中1的情况讨论，则在M1个空当中分别插入个1即可，也就是。剩下的1如何插入的问题与书P20页的定理12类似在N个不同元素中取R个允许重复21KM的组合，其组合数为（C（NR1,R），在这里无区别的球的个数也就是剩下的1的个数（即N），盒子的个数也就是2K插入到M1个空当中的1的个数即，则得出剩下的1的插入方法有。即第一种情况的总的插入方法为2K21KNC。212KNKM同理可得，按2的情况讨论后的第二种情况的总的插入方法为。212KNKM1和2得总的插入方法为。21212KNKMNKMCC若K为奇数时则必有且只有一个1插入字符串的头或尾,剩下的1按照1的方法插入,只有这样才能使K为奇数。所以插入的总方法为。212KNKM151题从N1,2,20中选出3个数，使得没有两个数相邻，问有多少种方案解相当于从N1,2,20个数中取3个作不相邻的组合，故方案数为C2031,3C18,3种152题从S1,2,N中连取K个数，使之没有两个数相邻，求不同方案数。解在N个数中选K个数，使之没有两个数相邻，相当于在NK1位置中插入K个数，K个数中没有俩个数相邻。有种方案。有定理14直接可得。11CKN153题把N个无区别的球放进有标志1，2，N的N个盒子中，每个盒子可放多于一个球，求有多少种方案解把N个无标志的球放进N个有标志的盒子中，每个盒子允许多于一个球是允许重复的组合所以是12154题M个1，N个0进行排列，求1不相邻的排列数设NM解相当于N个0排列后,使M个1做不相邻的插入，共产生N1个位置第一个1插入有N1种情况，11第二个是N种情况第M个1插入就有NM1种情况。所以是（N1）（N）（N1）（NM1），即此题解为PN1M。155题偶数位的对称数，即从左向右读法与从优向左的读法相同，如3223。试证这样的数可被11整除。证明根据所有偶数位置上的数字及所有奇数位置上的数字分别相加，再求出两个和的差，如果所得的差能被11整除，那么这个整数必能被11整除。例如12344321，偶数位上是2，4，3，1。奇数位上是1，3，4，2因为对称数是偶数个，所以偶数为相加与奇数为相加的和是相等的，他们的差是零，而零能能被任何数整除，所以原题成立。证毕。156题N个男人与N个女人沿一圆桌坐下，问两个女人之间坐1个男人的方案数。又M个女人N个男人，且M0,N213NB213NNBB特征方程特征根通解02,21NBA13初值，解得10B3BA4128故此，于是，134134NNNNB221316NNNBA（2）若NBAN265求142434N4的和解是N的4次方4N1S满足递推关系N0S615S201566N54N3NN代入可解得24A6055322N266题求矩阵。10解设N20320131NA1203NA所以NNNNA,111110231023267题000,22,NNNKKKSSSK解（1）因为11SN同理221NN同理3SS21NN同理4306421NNNSSS所以特征方程为X1是4重根124XXNDCBA3A0BCD02B4C8D23B9C27D841解方程得A0C0所以31B31D131NSN2和第一题同理（3）有二项式定理可设21NSN432NDCBASNS1A6S22AB30S33A3BC90S44A6B4CD210联立解A6B18C18D6所以4631826SN268题在一个平面上画一个圆，然后一条一条地画N条与圆相交的直线。当R是大于1的奇数时，第R条直线只与前R1条直线之一在圆内相交。当R是偶数时，第R条直线与前R1条直线在圆内部相交。如果无3条直线在圆内共点，这N条直线把圆分割成多少个不重叠的部分解当R是奇数（1）时121AARR当R是偶数时2R为偶数为奇数NAN4631269题用AN记具有整数边长、周长为N的三角形的个数。（1）证明是奇数，当是偶数，当NNANN41,23（2）求序列AN的普通形母函数。解1当N是偶数时对所有符合条件的AR3来说，每边增加1各单位，则可构成符合条件的AR。3R设短边为A、B，长边为C，则ABC2即AB2C1，对所有符合条件的AR来说，每边减少1各单位，则可构成符合条件的AR333RRA当N为奇数时由I的讨论知，AR比AR3多了ABC1的三角形。而这种三角形可知当能被2整除时，这种三角形有个41N当不能被2整除时，这种三角形有个41N2下面求它的普通母函数，32KA4121KKA记，02KKXAF012KXG那么3232002XGAFKKKK421212201323212211044144KKKKKKKKKGXAXAXXXFXXXF所以642711XXF64211XXG的普通母函数就是NA4324GF270（A）证明边长为整数、最大边长为L的三角形的个数是21L当是奇数时当是偶数时（B）设FN记边长不超过2N的三角形的个数，而GN记边长不超过2N1的三角形的个数，求FN和GN的表达式。解AL1时，只有一种可能（即3边都是长度为1）。241LL2时，有两种可能（即“1，2，2”、“2，2，2”）。设三角形的3边边长为X、Y、Z，且XYZL,XYZ。L2K1时XY2K2时，有K1种方案，即“1，2K1”、“2，2K”、“K1，K1”。XY2K3时，有K种方案，即“2，2K1”、“3，2K”、“K1，K2”。XY2K4时，有K种方案，即“3，2K1”、“4，2K”、“K2，K2”。XY4K1时，有1种方案，即“2K，2K1”。XY4K2时，有1种方案，即“2K1，2K1”。2211242K1KLIKL总和L2K时XY2K1时，有K种方案，即“1，2K”、“2，2K1”、“K，K1”。XY2K2时，有K种方案，即“2，2K”、“3，2K1”、“K1，K1”。XY2K3时，有K种方案，即“3，2K”、“4，2K”、“K2，K2”。XY4K1时，有1种方案，即“2K1，2K”。XY4K时，有1种方案，即“2K，2K”。12124KILL总和（B）4KKA，当是奇数，当是偶数1221,NKNKAGF22122121144NNNNFGFANGA43A11,A22,A34,A46,F1A1A23,F213,F00,F334,G1A1A2A37,G222,G01,G350,3210NANAFNA00,A20,F2136A2A27F334921A3A37,210NBBGNB01,G171B1B16,G222B02B1B2B29G350B03B13B2B3B34,47NNF342961NNGN271第一类STIRLING数01,NNRRXCXYX,Y证明1YN左边N0001,1,RNNNXYXYXYSKSSKNR0右边CX左边右边。272试证，有个非负整数解，其中M和N都是正整数。XXM21,/MCN解该题为第一类斯特林数，略。273已知非负整数，求满足的整数解的数目。S,21ISXNXI,2,21解由题已知故,IIX0I因为所以有12MN121MMIXSN设则，其方案数为IIYXS121MIYYNS0IY1IMISN所以，满足的整数解的数目为ISXNXIM,21,211IMISN275设F1F21,FNFN1FN2（A）证明。,1KFFNKNKN44（B）证明FM|FN的充要条件是M|N。M被N整除（C）证明。2,211062NMNFFMMN是偶数，当是奇数，当（D）证明FM,FNFM,N,M,N为M,N的最大公约数。解A证（对K用归纳法）K2时，FNF2FN21F1FN2，等式成立。假设对于K，等式成立。下证对于K1等式成立。由归纳假设，FNFKFNK1FK1FNKFKFNKFNK1FK1FNKFKFK1FNKFKFNK1FK1FNKFKFNK1。证毕。B证对M用数学归纳法。M0时，命题成立。假设对小于M的正整数，命题成立，设MN,，因（FN,FN1）1,故,有归纳假设NMN1NMN1NMNMN1MNC证对N用归纳法N2时，等式成立。N3时，FMF3FM32FM31FM1FM2FMFM1FMFM12FM,等式成立。假设对小于N的正整数，等式成立。是偶数。，当是奇数，当N,216222NMNNN利用FMFNFMN1FM1FN1FMN1FM1N11FM2FN2FMN2FM2FN2故有是偶数。，当是奇数，当N,2162MM（D）证对MAXM,N用归纳法，当MN时，等式成立。设MN，假设对小于MAXM,N的正整数，等式成立。因，NNMFF1NMFFFNMNN,1276从1到N的自然数中选取K个不同且不相邻的数，设此选取的方案为FN,K。（A）求FN,K的递推关系。（B）用归纳法求FN,K。（C）若设1与N算是相邻的数，并设在此假定下从1到N的自然数中选取K个不同且不相邻的K个数的方案数为GN,K，利用FN,K求GN,K。解（A）（B）（C）1421,4,21,2NKKGNKFFNKFFK277题设SN,K是第二类STIRLING数，证明SN1,MNKM1NKSK,M1证明当N2,M2左边S3,22S1,1S2,13右边C2,1S1,1C2,2S2,1213左边右边等式成立假设当NNK时等式成立即SNK1,MCNK,MSK,M1当NNK1时SNK2,MMSNK1,MSNK1,M1MCNK,KSK,M1SNK1,M1CNK1SK,M1即等式成立SNK1,MCN,KSK,M1278题求下图中从A点出发到N点的路径数135N2N45A24N1解设从A点到N点的路径数为AN,则得到递推公式为ANAN1AN2其中A11,A22特征方程为X2X10解得特征根为X1,2故ANANBN,25125将初始值A11,A22代入上式,解得A,B所以,ANNN010105231题某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也没有遇见的有5次，问某甲共参加了几次会议解设AI为甲与第I个朋友相遇的会议集，I1，6则故甲参加的会议数为2853332题求从1到500的整数中被3和5整除但不被7整除的数的个数解设A3被3整除的数的集合A5被5整除的数的集合A7被7整除的数的集合所以33题N个代表参加会议，试证其中至少有2人各自的朋友数相等。解每个人的朋友数只能取0，1，N1但若有人的朋友数为0，即此人和其他人都不认识，则其他人的最大取数不超过N2故这N个人的朋友数的实际取数只有N1种可能，12N所以至少有人的朋友数相等34题试给出下列等式的组合意义解A从N个元素中取K个元素的组合，总含有指定的M个元素的组合数为。KNMK设这M个元素为A1,A2,AM,AI为不含AI的组合（子集），I1,M12111IIII,0I11AJLLMLLILIMLLJNLKNNLAKK4635题设有三个7位的二进制数A1A2A3A4A5A6A7，B1B2B3B4B5B6B7，C1C2C3C4C5C6C7试证存在整数I和J，1IJ7，使得下列之一必定成立AIAJBIBJ，AIAJCICJ，BIBJCICJ证显然，每列中必有两数字相同，共有种模式，有或两种选择故共有2种选32择2632现有7列，即必有列在相同的两行选择相同的数字，即有一矩形，四角的数字相等6236题在边长为1的正方形内任取5个点试证其中至少有两点，其间距离小于12证把正方形分成四个1/21/2的正方形如上图则这点中必有两点落在同一个小正方形内而小正方形内的任两点的距离都小于1237题在边长为1的等边三角形内任取5个点试证其中至少有两点，期间距离小于1/2证把边长为的三角形分成四个边长为1/2的三角形，如上图则这点中必有两点落在同一个小三角形中小三角形中任意两点间的距离都小于1/238题任取11个整数，求证其中至少有两个数它们的差是10的倍数。证整数的个位数的可能取值为，共种可能11个整数中必有个数的个位数相同，即这两个数之差能被整除39题把从1到326的326个整数任意分为5个部分，试证其中有一部分至少有一个数是某两个数之和，或是另一个数的两倍。证用反证法。设存在划分P1P2P3P4P51，326，PI中没有数是两数之差，则有一PI中至少有66个数，AA1,A66，A1A2A66，以下按书上174页的例题证明可得310题A、B、C三种材料用作产品I、II、III的原料，但要求I禁止用B、C作原料，II不能用B作原料，III不允许用A作原料，问有多少种安排方案（假定每种材料只做一种产品的原料）解按题意可得如下的带禁区的棋盘,其中有阴影的表示禁区棋盘多项式为RRR1X13XX214X4X2X3故方案数34241101311题N个球放到M个盒子中去，NM/2M1，试证其中必有两个盒子有相同的球数。解设M个盒子的球的个数是A1,AM，各不相等，且有0A1A2AM则有A21、AMM1，故12M1M/2M1，与NM/2M1相矛盾所以必有两个盒子的球数相等312题一年级有100名学生参加中文、英语和数学的考试，其中92人通过中文考试，75人通过英语考试，65人通过数学考试；其中65人通过中、英文考试，54人通过中文和数学考试，45人通过英语和数学考试，求通过3门学科47考试的学生数。解设通过中文考试的92人为集合A，通过英语考试的75人为集合B，通过数学考试的65人为集合C则AB65，AC54，BC45由ABCABCABACBCABC故ABCABCABCABACBC10092756565544532通过3门学科考试的学生数为32。313题试证12|CBA证明1BABAB所以成立AB2CCABAC又因为由（A）得原式CAB314题，求其中不被5和7除尽，但被3除尽的数的数目。10,2N解设为被3除尽的集合为被5除尽的集合为被7除尽的集合A所以由题意得5733573336647922910100357315题,求其中被2，3，5，7中M个数除尽的数的数目，M0，1，2，3，4。求不超过120的素2,N数的数目。解1M0时不被2，3，5，7除尽的数为120235A2357232527AAA557337273257120（60402417）（2012888）（4211）27M0时2310251027108375A573AM3时23512043237120257357548M4时2357120357A2因为，故不超过120的合数必然是2，3，5，7的倍数1而且不超过120的合数的因子不可能超过11设为不超过120的数的倍数集合，I2，3，5，7I排除2，3，5，7这四个数又包含1这个非素数2，3，5，7本身是素数，故所求不超过120的素数个数应该为274130316题求正整数N的数目，N除尽，中的至少一个数。40302解N为正整数设为被除尽为被除尽401A30A302404030230N403040312N319题1000，1001，。，3000，求其中是4的倍数但不是100的倍数的数目。解设A，B分是4，100的倍数。301301502050248ABAB320题在由A,A,A,B,B,B,C,C,C,组成的排列中，求满足下列条件的排列数，（1）不存在相邻3元素相同；解A，B，C分别表示AAA,BBB,CCC则233275933751ABCABCSABS（2）相邻两元素不相同。321题求从O（0，0）点到（8，4）点的路径数。已知（2，1）到（4，1）的线段，（3，1）到（3，2）的线段被封锁解设A点坐标（2，1），B点坐标（4，1），C点坐标（3，1），D点坐标（3，2）令A为从O点到M点经过ACB为从O点到M点经过CBC为从O点到M点经过CD,31864,17,340,17,28405271SACBCCBCABSABCABCABC322题求满足下列条件X1X2X320,的整数解数目3,80,913XX49解令Y1X13,Y2X2,Y3X37016,028,031234ZYZYZY则所求整数解的数目C1431,14C16,2120324题求满足下列条件的整数解数目X1X2X3X4201X15,0X27,4X38,2X46解设Y1X11,Y2X2,Y3X34,Y4X42,Y1Y2Y3Y4130Y14,0Y27,0Y34,0Y44,若不附加上界条件的解根据公式应为65对于有上界的问题要作变换14Y1,27Y2,34Y3,44Y4,10,20,30,40,于是问题变为12346整数解的数目698325题证明满足下列条件X1X2XNR0XIK,I1,2,，N的整数解数目为01NIIRKIN解S,|S|令S中具有X1K1的子集A1，XIK1的子集AI,问题转化为求|A1A2AN|R1|A1|2NK|A1A2|4RNK|A1A2AN|01IIRKI326题证明满足下列条件X1X2XNR1XIK,I1,2,，N的整数解数目为01NIIIR证明令YIXI1则Y1Y2YNRN0YIK,I1,2,，N由上题知代入得整数解数目为01NIIRKI011IIRKI327题求N对夫妻排成一行，夫妻不相邻的排列数。解1N个人排成一行方案数为NN对夫妻排成一行方案数为N2N令AI第I对夫妻相邻而坐的集合，I1,2,，N22N个人排成一行方案数为2N|AI|相当于将第I对夫妻作为一个对象排列一行然后换位，故|A1|22N1|A1A2|222N2|A1A2AN|2NN故夫妻不相邻排列数为N2N22N1222N21N2NN2NH0H328题设P,QN，P是奇数，现在有PQ个珠子，着Q种颜色，每种颜色有P个珠子。假定相同颜色的珠子无区别。试分别求满足以下条件的珠子的排列数。（1）同颜色的珠子在一起；（2）同颜色的珠子处于不同的块；（3）同颜色的珠子最多在两个块。解同颜色的珠子在一起的排列数P同颜色的珠子处于不同的块的排列数PQP同颜色的珠子最多在两个块的排列数AI相当于第I个某色球处于不同块|A1|QPQ|A1A2|Q2PQ1|A1A2AP|QPPQP50NQPQQ2PQ11PQPQPP1P0PIQI329题将R个相同的球放进N个有标志的盒子里，无一空盒，求方案数。解先拿出N个球在每个盒子里放一个球，再将剩下的RN个球无限制地放入N个盒子中。根据定理13，RN个球无限制地放到N个盒子中共有CNRN1,RNCR1,RNCR1,N1种放法。330题试证，R，NN，RN10IIRI1解设共有R1个不同的红球和N个不同的白球，从中取出N1个球等式左边每个累加项（不考虑符号）可化为CN,ICNR1I,N1I表示从这些球中取I个白球和N1I个红球，表示至少取I个白球的组合数，即I。等式右边表示只从R1个红球中取出N1个球的组合数，表示恰好取0个白球的组合数，即0。根据广义容斥定理00121N1N1。原式证毕。332题M,R,NN,满足MRN,试证RNMII01RIN证明从N个元素中取K个的组合，总含有制定的M个元素的组合数为，MKNK设这M个元素为为不含的组合（子集），I1，,M12,MAKAKAKIKA21RINRNMIA1RNMII1IJKJMIKAI1,21KR333题求证A,0KDK证明右边01RIRKININ0001RKRKIRKINI左边RK0RKIRKIIC,1,1NKDNN证明0111KIINKINKIIKNKII100NKNKIINKII得证。100NKNKIINKIID,KRTTDTT51证明0011KRRTKRKTTIRKIRKIINININ001RKRKIRKIRKIITKTRTKININR反过程可证。001RKRKIRKIRKIIKTTRKTNIINE,1,1,DNRKNRKDNRK证明01100111RKIRKIRRKRKKIRKIRKIIINININN0110011RKIRKIRKRKIRKIRKIIIRNININN100011RKRKRKIIIIIIIIIRK当I0时，各项左右相等，对应当NRK1时候，左右也相等。剩余左右当IRK时候也相等，得证。335题令DNKDN,N,K,试证ADNKDNKK证明I11,00KNIKNIINKKIIIKIN1000IIKIDIKNIIKNIKNKNNB21NDD52证明上面等式可变换为021NDND考虑N元素的集合S1,2,N，设T为S的排列全体，则|T|N。设是S中恰有I个在其自然位置的N排列全体，则所以，IANIJIATA0NIIAT0|而，因此，INID|NIID0CK1DN1K1N1DNK证明11110100IKNIKNIKNIKNKIKIIKIN100INKNKNNIIKDIDI337题试证对于素数,I,1P1IIIP证明KKPNN12121则根据1IIIIIPPNP338题试证AND/证明/DNDN根据反演定理可得342题一组人有1990个人，每个人至少有1327个朋友，试证其中四位，使得彼此都是好朋友解；令外边的都与括号里的1327个是朋友，11989，从里边不是外边人朋友的找出219886631327再从里边找人出来662，11，1236直至663663664按上面的方法继续6636636631把里边的1拿出外边一个进去为662，11663663这样1与里边的都是朋友，括号里前面括号的人与后边的都是朋友，所以一定有四个人彼此是朋友。343题在边长为1的等边三角形内任取5个点试证其中至少有两点，期间距离小于1/2证把边长为的三角形分成四个边长为1/2的三角形，如上图则这点中必有两点落在同一个小三角形中小三角形中任意两点间的距离都小于1/253344题单位圆圆周上任意个不同的点至少存在两点其间距离不超过。1N2SIN证明把圆周等分成段相等的弧，每段弧所对的最大弦长为，把个点放到这个圆弧上，根据鸽巢原理，必有两个点在同一段弧上，这两点的距离必小于等于。2SI346题任给5个整数，试证其中必存在3个数的和被3除尽。证明所有整数可分为3类，MOD30,MOD31,MOD32，分别标记为A,B,C如果在这五个数中，任何一类的个数大于等于3，那么在这个类中任取三个元素，它们的和一定能被三整除。如果没有任何一类的个数大于等于3，那么只能是2，2，1的组合如果A类元素只有一个，那么B类，C类各有2个元素。A，B，C各类各取一个，它们的和一定能被三整除。如果B类元素只有一个，那么A类，C类各有2个元素。A，B，C各类各取一个，它们的和一定能被三整除。如果C类元素只有一个，那么A类，B类各有2个元素。A，B，C各类各取一个，它们的和一定能被三整除。345题边长为1的正方形内任取9点，试证存在3个不同的点，由此构成的三角形面积不超过。18证明把正方形等分为8个三角形，每个三角形的面积为,产生以正方形中心的8条边，18把9