《组合数学》姜建国著(第二版)-课后习题答案完全版

《组合数学》姜建国著(第二版)-课后习 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 答案完全版组合数学(第2版)-姜建国,岳建国习题一（排列与组合）1．在1到9999之间，有多少个每位上数字全不相同而且由奇数构成的整数？解：该题相当于从“1，3，5，7，9”五个数字中分别选出1，2，3，4作排列的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 数；（1）选1个，即构成1位数，共有个；（2）选2个，即构成两位数，共有个；（3）选3个，即构成3位数，共有个；（4）选4个，即构成4位数，共有个；由加法法则可知，所求的整数共有：个。2．比5400小并具有下列性质的正整数有多少个？（1）每位的数字全不同；（2）每位数字不同且不出现数字2与7；解：（1）比5400小且每位数字全不同的正整数；按正整数的位数可分为以下几种情况：①一位数，可从1～9中任取一个，共有9个；②两位数。十位上的数可从1～9中选取，个位数上的数可从其余9个数字中选取，根据乘法法则，共有个；③三位数。百位上的数可从1～9中选取，剩下的两位数可从其余9个数中选2个进行排列，根据乘法法则，共有个；④四位数。又可分三种情况：千位上的数从1～4中选取，剩下的三位数从剩下的9个数字中选3个进行排列，根据乘法法则，共有个；千位上的数取5，百位上的数从1～3中选取，剩下的两位数从剩下的8个数字中选2个进行排列，共有个；千位上的数取5，百位上的数取0，剩下的两位数从剩下的8个数字中选2个进行排列，共有个；根据加法法则，满足条件的正整数共有：个；（2）比5400小且每位数字不同且不出现数字2与7的正整数；按正整数的位数可分为以下几种情况：设①一位数，可从中任取一个，共有7个；②两位数。十位上的数可从中选取，个位数上的数可从A中其余7个数字中选取，根据乘法法则，共有个；③三位数。百位上的数可从中选取，剩下的两位数可从A其余7个数中选2个进行排列，根据乘法法则，共有个；④四位数。又可分三种情况：千位上的数从1，3，4中选取，剩下的三位数从A中剩下的7个数字中选3个进行排列，根据乘法法则，共有个；千位上的数取5，百位上的数从0，1，3中选取，剩下的两位数从A中剩下的6个数字中选2个进行排列，共有个；根据加法法则，满足条件的正整数共有：个；3．一教室有两排，每排8个座位，今有14名学生，问按下列不同的方式入座，各有多少种做法？（1） 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 某5人总坐在前排，某4人总坐在后排，但每人具体座位不指定；（2）要求前排至少坐5人，后排至少坐4人。解：（1）因为就坐是有次序的，所有是排列问题。5人坐前排，其坐法数为，4人坐后排，其坐法数为，剩下的5个人在其余座位的就坐方式有种，根据乘法原理，就座方式总共有：（种）（2）因前排至少需坐6人，最多坐8人，后排也是如此。可分成三种情况分别讨论：①前排恰好坐6人，入座方式有；②前排恰好坐7人，入座方式有；③前排恰好坐8人，入座方式有；各类入座方式互相不同，由加法法则，总的入座方式总数为：典型错误：先选6人坐前排，再选4人坐后排，剩下的4人坐入余下的6个座位。故总的入坐方式共有：种。但这样计算无疑是有重复的，例如恰好选6人坐前排，其余8人全坐后排，那么上式中的就有重复。4．一位学者要在一周内安排50个小时的工作时间，而且每天至少工作5小时，问共有多少种安排方案？解：用 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示第i天的工作时间，，则问题转化为求不定方程的整数解的组数，且，于是又可以转化为求不定方程的整数解的组数。该问题等价于：将15个没有区别的球，放入7个不同的盒子中，每盒球数不限，即相异元素允许重复的组合问题。故安排方案共有：（种）另解：因为允许，所以问题转化为长度为1的15条线段中间有14个空，再加上前后两个空，共16个空，在这16个空中放入6个“＋”号，每个空放置的“＋”号数不限，未放“＋”号的线段合成一条线段，求放法的总数。从而不定方程的整数解共有：（组）即共有54264种安排方案。5．若某两人拒绝相邻而坐，问12个人围圆周就坐有多少种方式？解：12个人围圆周就坐的方式有：种，设不愿坐在一起的两人为甲和乙，将这两个人相邻而坐，可看为1人，则这样的就坐方式有：种；由于甲乙相邻而坐，可能是“甲乙”也可能是“乙甲”；所以则满足条件的就坐方式有：种。6．有15名选手，其中5名只能打后卫，8名只能打前锋，2名只能打前锋或后卫，今欲选出11人组成一支球队，而且需要7人打前锋，4人打后卫，试问有多少种选法？解：用A、B、C分别代表5名打后卫、8名打前锋、2名可打前锋或后卫的集合，则可分为以下几种情况：（1）7个前锋从B中选取，有种选法，4个后卫从A中选取，有种，根据乘法法则，这种选取方案有：种；（2）7个前锋从B中选取，从A中选取3名后卫，从C中选1名后卫，根据乘法法则，这种选取方案有：种；（3）7个前锋从B中选取，从A中选取2名后卫，C中2名当后卫，根据乘法法则，这种选取方案有：种；（4）从B中选6个前锋，从C中选1个前锋，从A中选4个后卫，根据乘法法则，这种选取方案有：种；（5）从B中选6个前锋，从C中选1个前锋，从A中选3个后卫，C中剩下的一个当后卫，选取方案有：种；（6）从B中选5个前锋，C中2个当前锋，从A中选4个后卫，选取方案有：种；根据加法法则，总的方案数为：7．求展开式中项的系数。解：令，则中项的系数为，即中，的系数，因此，的系数为：。8．求的展开式。解：，展开式共有（项），所以，9．求展开式中的系数。解：的系数为：10．试证任一整数n可唯一表示成如下形式：证明：（1）可表示性。令，显然，，显然，定义函数，，显然，即，由于f是用普通乘法和普通加法所定义的，故f无歧义，肯定是一个函数。从而必有一确定的数，使得，为了证明N中的任一数n均可表示成的形式，只需证明f是满射函数即可。又因为f是定义在两个有限且基数相等的函数上，因此如果能证明f单射，则f必是满射。假设f不是单射，则存在，，且有，使得由于，故必存在，使得。不妨设这个j是第一个使之不相等的，即，且，因为所以，产生矛盾，所以f必是单射函数。因为，所以f必然也是满射函数，故对任意的，都存在，使得这说明对任意的整数，都可以表示成的形式。（2）唯一性。由于函数是一个单射，也是满射，即f是双射函数，故，对任意的，都存在唯一的，使得。否则，若存在另一个，使得将与f是单射函数矛盾。证毕。11．证明，并给出组合意义。证明：因为，现令，，则可得，即组合意义：将n个元素分为3堆，1堆1个元素，1堆r个元素，1堆个元素。可以有下面两种不同的分法：（1）先从n个元素中选出个元素，剩下的个作为1堆；再将选出的个元素分为两堆，1堆1个，1堆r个。（2）先从n个元素中选出1人作为1堆，再从剩下的个中选出r个作为1堆，剩下的作为1堆。显然，两种分法是等价的，所以等式成立。12．证明。证明：采用殊途同归法。组合意义一：考虑从n个人中选出1名正式代表和若干名列席代表的选法（列席代表人数不限，可以为0）。可以有以下两种不同的选法：（1）先选定正式代表，有种选法；然后从人中选列席代表，这个人都有选和不选的两种状态，共有种选法；根据乘法法则，共有种选法；（2）可以先选出人，然后再从中选出1名正式代表，其余k人作为列席代表，对于每个k，这样的选法有：，从而总选法有：显然，两种选法是等价的，所以等式成立。组合意义二：将n个不同的球放入标号为A、B、C的3个盒子，其中要求A盒只放1个球，其余两盒的球数不限。那么，有两种不同的放法：（1）先从n个不同的球中选出1个，放入A盒，再将其余个球放入另外两盒，有种放法；（2）先从n个球中选出k个，再从所选的k个球中选出1个放入A盒，将其余的个球放入B盒，剩下的个球放入C盒，根据乘法法则，对于不同的k，有种放法。当时，各种情况互不重复，且包含了所有放法，根据加法法则，总的放法有：。显然两种放法是等价的，故等式成立。另法：根据二项式定理：，两边求导，得：，令，即得13．有n个不同的整数，从中取出两组来，要求第一组数里的最小数大于第二组的最大数，问有多少种方案？解：设这n个不同的数为，若假定第一组取个数，第二组取个数，并且令，则要求第一组数里的最小数大于第二组里的最大数，我们可以这样来选：先从n个数中任选m个数出来，有种选法；再从这m个数中从大到小取个数作为第一组数，，有种取法；再将其余的个数作为第二组数。故总方案数有：14．六个引擎分列两排，要求引擎的点火次序两排交错开来，试求从某一特定引擎开始点火有多少种方案？解：第一次点火仅有一种选择，即点某个特定引擎的火；第二次点另一组某个引擎的火，有三种选择；第三次有2种,……。所以方案数为：（种）如果只指定从第一排先开始点火，不指定某一个，则方案数为（种）如果第一个引擎任意选，只要求点火过程是交错的，则方案数为（种）15．试求从1到1000000的整数中，0出现了几次？解：分别计算0出现在各个位上的次数。（1）0出现在个位，此时符合条件的2位数有9个；3位数有个；4位数有个；5位数有个；6位数有个；（2）0出现在十位，此时符合条件的3位数有个；4位数有个；5位数有个；6位数有个；（3）0出现在百位，此时符合条件的4位数有个；5位数有个；6位数有个；（4）0出现在千位，此时符合条件的5位数有个；6位数有个；（5）0出现在万位，此时符合条件的6位数有个；另外1000000中有6个0。所以，从1到1000000的整数中，0出现的次数总共有：（次）另法：先不考虑1000000本身，那么任一个000000～999999之间的数都可以表示成如下形式：，其中每个是0到9的数字。因为每位数字可以有10种选择，根据乘法法则，共有个“6位数”，又每个“6位数”由6个数字组成（包括无效0），所以共有个数字，又每个数字出现的概率相等，所以0出现的次数应是，但习惯上在计算0的个数时，不包括无效0（即高位的0），因而要从中去掉无效0，其中：（1）1位数有9个（不包括0），其无效0共有个（即00000）；（2）2位数有90个，其无效0共个。依次类推，无效0的总数为因为全为0时的6个0和1000000本身的6个0相互抵消，所以1到1000000之间的自然数中0出现的次数为（次）注意：1出现的次数为（要考虑1000000这个数的首位1），2，3，…，9各自出现的次数为。16．n个男n个女排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又有多少种不同的方案？解：排成男女相间的队伍：先将n个男的排成1行，共有种排法；再将n个女的往n个空里插，有种排法；由于可以先男后女，也可以先女后男，因此共有种排法；根据乘法法则，男女相间的队伍共有：种方案。若围成一圆周坐下，同理先将n个男的围成一圆周，共有种排法，再将n个女的往n个空中插，有种排法，根据乘法法则，围成圆周坐下，总的方案数有：种。17．n个完全一样的球，放到r个有标志的盒子，，要求无一空盒，试证其方案数为。证明：因为没有空盒，可先每盒放入一个球，再将剩余的球放入r个盒子中，即将个无区别的球，放入r个不同的盒子中，每盒的球数不受限制，因此方案数有：。另法：插空法。问题可看为：n个球排成1行，球与球之间形成个空，再在这个空中，插入个隔板，这样就可形成r个盒子，每盒球不空的方案，其方案数为。18．设，是k个素数，试求能整除尽数n的正整数数目。解：能整除数n的正整数即n的正约数，其个数为：。19．试求n个完全一样的骰子能掷出多少种不同的方案？解：每个骰子有六个面，每个面的点数可以是中的一种。由于n个骰子完全一样，故这样相当于将n个完全一样的球放到6个不同的盒子中，每盒球数不限。故方案数有（种）20．凸十边形的任意三个对角线不共点，试求这凸十边形的对角线交于多少个点又把所有的对角线分割成多少段解：（1）从一个顶点可引出7条对角线，这7条对角线和其他顶点引出的对角线的交点情况如下：从右到左，和第一条对角线的交点有：个，和第二条的交点有，和第三条的交点有条，…，故和一个顶点引出的7条线相交的点为：，故和从10点引出的对角线交的点有个，但每个点重复了四次（因为每个点在两条线上，而每条线又有两个端点），故凸十边形对角线交于个点。也可以直接这样看：因为一个交点需要两条对角线相交，而两条对角线又需要多边形的四个点构成一四边形。反之，从n个顶点中任取四个顶点，连成一四边形，而四边形的两条对角线必须确定唯一的一个交点，故凸十边形的对角线的交点共有：（个）（前提：任三个对角线不共点，否则，一个交点不能对应n边形的唯一四个顶点）（2）由（1）知，一个点引出的7条对角线中，第一条线上有7个点，故将该线段分成8段；第二条线上有12个点，故将该线段分成13段，…，故从一个点出发的7条线上的段数为：。现有10个点。故总的段数为：。但每段重复计算了2次（因为每条线有2个端点）故总的段数应为：。另法：一个交点给相交的两条对角线各增加1段，所以对角线总的段数为：对角线数＋2倍交点数＝（段）21．试证一整数n是另一整数的平方的充要条件是除尽n的正整数的数目为奇数。证明：必要性：整数n可表示为，，且为素数，，则除尽n的正整数个数为：，若为偶数，则必存在为奇数，则n不可能写成令一个数的平方。所以n是另一整数的平方的必要条件是除尽n的正整数数目为奇数。充分性：若除尽n的正整数的数目为奇数，则均为偶数，则可写成另一整数的平方。证毕。22．统计力学需要计算r个质点放到n个盒子里去，并分别服从下列假定之一，问有多少种不同的图像？假设盒子始终是不同的。（1）Maxwell-Boltzmann假定：r个质点是不同的，任何盒子可以放任意个；（2）Bose-Einstein假定：r个质点完全相同，每一个盒子可以放任意个。（3）Fermi-Dirac假定：r个质点都完全相同，每盒不得超过一个。解：（1）问题即：将r个不同的质点放到n个不同的盒子，每个盒子放的质点数不受限制，即相异元素允许重复排列，其方案数有：（2）问题即：将r个没有区别的质点放到n个不同的盒子，每个盒子方的质点数不受限制，即相异元素允许重复组合，其方案数有：（3）问题即：将r个没有区别的质点放到n个不同的盒子，每盒不超过一个，即相异元素不允许重复的组合，其方案数有：23．从26个英文字母中取出6个字母组成一字，若其中有2或3个母音，问分别可构成多少个字（不允许重复）解：母音指元音，即a，e，i，o，u（1）有2个元音。先从5个元音中取出2个，再从剩下的21个字母中选出4个，再将6个字母进行全排列，则可构成的字总共有：（个）（2）有3个元音。先从5个元音中取出3个，再从剩下的21个字母中选出4个，再将6个字母进行全排列，则可构成的字总共有：（个）24．给出的组合意义。证明：组合意义一：从个元素中取出个元素的组合数为：，且，其中第位置上的元素可取，当取时（），前边的r个数可在这个数中取，故有种取法；后边的个数可在这个数中取，故有种取法。根据乘法法则，当时，这样的组合数为：再根据加法法则，对进行求和，就有。组合意义二：（格路 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ）等式左端：从点到点（），直接经过点再到点的路径数。从A到C的路径数为：，从D到B的路径数为：，根据乘法法则和加法法则，从A到B的路径数有：。等式右端：从点到点的路径数为：25．给出的组合意义。证明：（1）等式右端：从个元素中，任选个元素的组合方案数为：。（2）等式左端：从不同元素中选取个元素，一定选元素，但不选元素的方案数。根据乘法法则，当k值取定时，这样的方案数为从其余的个元素中任取r个的方案数，即，再根据加法法则，总的方案数有：26．证明。证明：考虑从m双互不相同的鞋中取出n只，，要求其中没有任何两只是成对的，求方案数。一方面，先从m双鞋中选取n双，共有种选法，再从此n双中每双抽掉一只，有种取法，由乘法原理，总的方案数为：。另一方面，先取出只左脚的鞋，再在其余的双中取出只右脚的鞋，则总的方案数为：所以，。另法：根据（）（）从而有：27．对于给定的正整数n，证明在所有中，当时，取得最大值。证明：取与进行比较。，当时，，即，当时，，即，因此，只有当或最接近时，取得最大值。28．（1）用组合方法证明和都是整数。（2）证明是整数。证明：（1）考虑个有区别的球放入n个不同的盒子里，每盒两个，盒中球不计顺序，则方案数为：，方案数是整数，所以是整数。同理，考虑个有区别的球放入n个不同的盒子里，每盒3个，盒中球不计顺，则方案数为：，方案数是整数，所以是整数。（2）考虑个不同的球放入n个相同的盒子，每盒n个，盒中球不计顺序的方案。先假设盒子是不同的，则这样的方案数为：，又盒子是相同的，所以方案数应为：，方案数必然是整数，所以是整数。29．（1）在2n个球中，有n个相同，求从这2n个球中选取n个的方案数。（2）在个球中，有n个相同，求从这个球中选取n个的方案数。解：（1）问题即：从集合中，选取n个的方案数，即多项式中的系数，即从这2n个球中选取n个的方案数为种。（2）问题即：从集合中，选取n个的方案数，即多项式中的系数，即30．证明在由字母表生成的长度为n的字符串中，（1）0出现偶数次的字符串有个；（2），其中。证明：（1）采用数学归纳法当时，0出现偶数次（0次），长度为1的字符串为“1”和“2”两个字符串，而，故结论成立。假设当时，结论成立，即0出现偶数次，长度为k的字符串有个，当时，0出现偶数次，长度为的字符串包括两部分：①在0出现偶数次，长度为k的字符串后面再增加一位不是0的数（只能是1或2），因此，这样的字符串有个。②给0出现奇数次，长度为k的字符串后面再增加一个0，因此，这样的字符串有：。根据加法法则，0出现偶数次，长度为的字符串共有：，即时，结论也成立。所以，根据数学归纳法，结论成立。（2）由（1）知，右端表示0出现偶数次的字符串数。而左端代表的组合问题是：长度为n的字符串中，有0个0的字符串数有：，有2个0的字符串数有：，…，有q个0的字符串数有：，根据加法法则，可知，左端代表的是长度为n的字符串中0出现偶数次的字符串数，因此31．5台教学仪器供m个学生使用，要求使用第1台和第2台的人数相等，有多少种分配方案？解：方法一：先从m个学生中选取k个使用第1台机器，再从剩下的个学生中选取k个使用第2台机器，其余个学生可以任意使用剩下的3台机器，按乘法原理，其组合数为，这里，于是，按加法原理，共有种使用方案。方法二：先从m个学生种选出2k个，再将选出2k个学生平均分到1、2台机器上，其余的个学生可以任意使用剩下的3台机器，按乘法法则，其组合数为，这里于是，按加法原理，共有种使用方案。32．由n个0及n个1组成的字符串，其任意前k个字符中，0的个数不少于1的个数的字符串有多少？解：（参见P21，例1.8.8）转化为格路问题。即从点到，只能从对角线上方走，但可以碰到对角线的所有最短路径数。显然，第一步必然要走到点，因此可以转换为从点到的所有满足条件的路径数，进一步，可以转换为从点到，只能从对角线上方走，但不可以碰到对角线的所有路径数，因为从点到的所有经过对角线的路径数与从点到点的所有路径数是一一对应的，因此，所求的字符串有：（个）方法二：由n个1和n个0组成的2n位二进制数共有个(2n个不尽相异元素的全排列)，设所求的二进制数共有个，不符合要求的数有个。而不合要求的数的特征是从左向右扫描时，必然在某一位首次出现0的个数小于1的个数，即从左向右累计到第2k＋1位时出现k个0和个1。此时，后位上有个1，个0。将后部分的0改写为1，1改写为0。结果整个数变成由个和个0组成的2n位数z。即一个不合要求的数唯一对应于这样的一个数z。反之，给定一个由个1和个0组成的2n位数z．由于1比0多2个，故一定在某一位首次出现0的累计数少于1的累计数。依同法将此位后的0与1互换，使z变成由n个1和n个0组成的2n位数。所以，这两种二进制数一一对应。即故。习题二（母函数及其应用）1．求下列数列的母函数（1）；（2）；（3）；（4）；解：（1）母函数为：； （2）母函数为：；方法二：（3）母函数为：；方法二：（4）母函数为：。方法二：2．证明序列的母函数为。证明：因为令，则，而故又所以方法二：已知的k-组合数为，其母函数为：序列的母函数为3．设，求序列的母函数。其中，是S的满足下列条件的n组合数。（1）S的每个元素都出现奇数次；（2）S的每个元素都出现3的倍数次；（3）不出现，至多出现一次；（4）只出现1、3或11次，只出现2、4或5次；（5）S的每个元素至少出现10次。解：（1）（2）（3）（4）（5）4．投掷两个骰子，点数之和为r，其组合数是多少？解：用表示骰子的点数为i，（1）若两个骰子不同，则问题等价于r的特殊有序2-分拆故相应的母函数为则点数之和为r的方案总数就是的系数。（2）若两个骰子相同，则问题等价于r的特殊无序2-分拆而此问题又可转化为求r的最大分项等于2，且项数不超过6的分拆数，即求方程的非负整数解的个数。相应的母函数为其中点数之和为r的方案数就是的系数。5．投掷4个骰子，其点数之和为12的组合数是多少？解：参考第4题。（第二版第5题）居民小区组织义务活动，号召每家出一到两个人参加。设该小区共有n个家庭，现从中选出r人，问：（1）设每个家庭都是3口之家，有多少种不同的选法当n=50时，选法有多少种（2）设n个家庭中两家有4口人，其余家庭都是3口人，有多少种选法？解：（1）（2）（第二版第6题）把n个相同的小球放入编号为的m个盒子中，使得每个盒子内的球数不小于它的编号数。已知，求不同的放球方法数。解：对应母函数为：故6．红、黄、蓝三色的球各8个，从中取出9个，要求每种颜色的球至少一个，问有多少种不同的取法？解：对应的母函数为：从中取9个对应的组合数为的系数，即（种）方法二：原问题等价于从集合中取出9个元素，且每个元素至少取一个。现在先把元素a、b、c各取一个，然后再随意选出6个，则问题转变为从集合中取出6个元素，且每个元素个数不限，求重复组合的方案数。又由于每个元素的个数大于6，故从中取6个元素与从集合中取出6个元素的组合数一样多，因此不同的取法为（种）7．将币值为2角的人民币，兑换成硬币（壹分、贰分和伍分）可有多少种兑换方法？解：该题用1分、2分、5分的硬币组成20分。是可重复的无序拆分：其母函数为：则不同的兑换方法为的系数，即即有29种兑换方法。8．有1克重砝码2枚，2克重砝码3枚，5克重砝码3枚，要求这8个砝码只许放在天平的一端，能称几种重量的物品有多少种不同的称法解：该题属于有限重复的无序拆分问题。对应的母函数为：所以能称1～23克等23种重量的物品。总共的称法为母函数的各项系数之和，再减去常数项，即总共有（种）不同的称法。其中，称1、3、20、22、23克重量各有1种称法；称2、4、5、8、9、10、13、14、15、18、19、21克重量各有2种称法；称6、7、11、12、16、17克重量各有3种乘法；若要枚举出各种方案，则可作母函数：项即为称克重量的一种方案。9．证明不定方程的正整数解组的个数为。解：该问题即，求正整数r的n有序分拆。问题可转换为：将r个无区别的球，放入n个不同的盒子中，每盒至少1个的组合问题。可以先在每个盒子中放1球，再将个无区别的球，放入n个不同的盒子中，每盒球数不限，则其方案数为：故该不定方程的正整数解组的个数为。方法二：问题可以视为将r个相同的1放入n个盒子。由于将之间的值互换，对应不同的解，所以盒子不同。设共有个解，则的母函数为所以10．求方程的大于1的整数解的个数。解：该题相当于将24的3有序分拆，并且要求每个分项大于1。其母函数为：所求的整数解的个数即为的系数：。11．设，，其中，。试证：（1），；（2）求出、的母函数，。证明：（1）（2）因为所以同理，所以，，解联立方程组，即可得，12．设，求序列的母函数，其中是S的满足下列条件的n排列数：（1）S的每个元素都出现奇数次；（2）S的每个元素至少出现4次；（3）至少出现i次；（4）至多出现i次；解：（1）母函数为：；（2）母函数为：；（3）母函数为：；（4）母函数为：；13．把23本书分给甲乙丙丁四人，要求这四个人得到的书的数量分别不超过9本、8本、7本、6本，问：（1）若23本书相同，有多少种不同的分法？（2）若23本书都不相同，又有多少种不同的分法？解：（1）对应的母函数为：所求的分法数就是的系数，即（种）（2）对应的母函数为：所求的分法数就是的系数，即14．8台计算机分给3个单位，第一个单位的分配量不超过3台，第二个单位不超过4台，第三个单位不超过5台，问共有几种分配方案？解：对应的母函数为：所求的分配方案数即的系数，即分配方案数为：（种）15．用母函数证明下列等式成立：（1）；（2）。证明：（1）方法一：根据范德蒙恒等式令，即得方法二：因为，两边展开得比较次方的系数，即得（2）方法一：令，则，且，令则即因为，所以，故所以。证毕。方法二：比较两边的系数，即可得：。方法三（组合意义法）等式右端：相当于从个不同的球中取个球的组合，其组合方案数为；等式左端：把这个球编号为，按取出的球中最小的编号，可分为如下的m+1类：如果取出的个球中最小编号是1，其余n个球要从去掉1号球后剩下的个球中选取，此类组合方案数为；如果取出的个球中最小编号是2，则1不能被选取，其余n个球要从去掉1，2号球后剩下的个球中选取，此类组合方案数为；…，依次类推，如果取出的个球中最小编号是m，则不能被选取，其余n个球要从去掉号球后剩下的个球中选取，此类组合方案数为；如果取出的个球中最小编号是，则不能被选取，其余n个球要从去掉号球后剩下的n个球中选取，此类组合方案数为；因此，按加法原理，从个不同的球中取个球的组合方案数为。故等式两边相等。16．证明自然数n分拆为互异的正整数之和的分拆数等于n分拆为奇数之和的分拆数。证明：将n分拆为互异的正整数之和的分拆数的母函数为：将n分拆为奇数之和的分拆数的母函数为：所以，两种分拆的方案数相同。17．求自然数50的分拆总数，要求分拆的每个分项不超过3。解：其母函数为：则所求的分拆数为的系数，即习题三（递推关系）1．解下列递推关系：（1）（2）（3）（4）（5）解：（1）对应的特征方程为：，解得。所以齐次递推方程的通解为：，代入初始条件，得：，，解得：，故。（2）对应的特征方程为：，解得：，所以，齐次递推方程的通解为：，代入初始条件，，，解得：，故。（3）对应的特征方程为：，解得：，所以，齐次递推方程的通解为：，代入初始条件，，，解得：，故。（4）对应的特征方程为：，解得：，所以，齐次递推方程的通解为：，代入初始条件，，，解得：，故。（5）对应的特征方程为：，解得：，所以，齐次递推方程的通解为：，代入初始条件，，，，解得，，故2．求由A，B，C，D组成的允许重复的排列中AB至少出现一次的排列数。解：方法一：我们只要求出n位排列中不出现AB的排列个数，则至少出现一次AB的排列个数为。可以分成两部分：：在n位排列中不出现AB且在第n位出现A的排列数目。：在n位排列中不出现AB且在第n位出现B或C或D的排列的数目。因此，，显然，若在n位排列中不出现AB，则在前位中也不会出现AB，考虑第n位：（1）若第n位为A，则第位可以是A、B、C、D中的任何一位；（2）若第n位为B，则第位只能是B、C、D中任何一位；（3）若第n位为C或D，则第为可以是A、B、C、D中任一位；故可得递推关系：令，，方程两边同乘于，即将上面的式子进行累加，可得：，故，即方程两边同乘于，即同样，将上面的式子进行累加，可得故，即故可得关于的联立方程组，解得：故，因此，所以。方法二：设表示由A，B，C，D组成的允许重复的不出现AB的n位排列数目；由A，B，C，D组成的允许重复的不出现AB的n位排列数目，可分为两个部分：（1）第n位是A，C或D，则前位不出现AB的排列数为，则此类排列数为；（2）第n位是B，前位形成的不出现AB的排列数有个。其中，要去掉第位是A的排列，这样的排列由前位形成的不出现AB的个位排列，再加上AB形成，于是此类排列的数目为；根据加法法则，可得到递推关系：对应齐次方程的特征方程为：，解得，，故齐次方程的通解为：，代入初始条件：，，解得：，故因此，由A，B，C，D组成的允许重复的且AB至少出现一次的n位排列数目为。3．求n位二进制数中相邻两位不出现11的数的个数。解：设所求的n位二进制数有个，对第1位数的数值有两种可能：（1）0，则余下的位数，满足条件的个数有个；（2）1，则第2位数只能为0，余下的位数，满足条件的个数有个；由加法法则，可得：，且，由递推关系反推，可得，所以，4．利用递推关系求下列和：（1）（2）（3）（4）解：（1）显然，，对应的齐次方程的特征方程为：，解得，所以对应的齐次方程对应的通解为：，因为1是特征根，所以对应的特解为：所以方程的通解为，显然，，，，，代入上式，可得，，，，解得：，，，，所以方法二：显然，类似，可得，两式相减，可得，同理，可得，两式再相减，可得，同理，可得，两式再相减，可得关于的齐次定解问题：其特征方程为：，解得：，故，代入初始条件，，，，，解得：，故方法三（快速求系数）通解为：，初始条件：，代入得，，，，解得：，，，所以，（2）显然，，同理对应的齐次方程的特征根为1，通解为，非齐次方程的特解为：，所以，非齐次方程的通解为：，初始条件为：，代入上式，可得，，，，解得：，，，，所以方法二：显然，，类似可得，，两式相减得，同理可得，两式再相减得，同理得，两式再相减，可得关于的齐次定解问题：由（1）知，方程的通解为：，代入初始条件得：，，，，解得：，故方法三（快速求系数）通解为：，初始条件：，代入得，，，，解得：，，，所以，（3）显然，，同理对应的齐次方程的特征根为1，特解为，非齐次方程的特解为：，所以，非齐次方程的通解为：，初始条件为：，代入上式，可得，，，，解得：，，，，所以方法二：显然，，类似可得，，两式相减得，同理可得，两式再相减得，同理得，两式再相减，可得关于的齐次定解问题：由（1）知，方程的通解为：，代入初始条件得：，，，，解得：，故方法三（快速求系数）通解为：，初始条件：，代入得，，，，解得：，，，所以，（4）显然，，同理对应的齐次方程的特征根为1，特解为，非齐次方程的特解为：，所以，非齐次方程的通解为：，初始条件为：，代入上式，可得，，，，解得：，，，，所以方法二：显然，，类似可得，，两式相减得，同理可得，两式再相减得，同理得，两式再相减得，同理可得，两式再相减，可得关于的齐次定解问题：其特征方程为：，是五重特征根，所以方程的通解为：，代入初始条件得：，，，，，解得：，故方法三（快速求系数）通解为：，初始条件：，代入得，，，，解得：，，，，所以，5．求n位四进制数中2和3必须出现偶数次的数目。解：设符合条件的n位四进制数有个，2出现奇数次3出现偶数次的数有个，2出现偶数次3出现奇数次的数有个，两者都出现奇数次的数有个。（1）对2和3出现偶数次的n位四进制数，考虑最高位，可分为三种情况：①最高位是0或1，则在后续的个数字中2和3还必须出现偶数次，这样的四进制数共有个；②最高位是2，后位必须有奇数个2偶数个3，这样的数有个；③最高位是3，后位必须有偶数个2奇数个3，这样的数有个。各类情形，没有重复的数。由加法法则，得满足的递推关系为：（2）对2出现奇数次3出现偶数次的n位四进制数，考虑最高位，可分为三种情况：①最高位是0或1，则在后续的个数字中2出现奇数次3出现偶数次，这样的四进制数共有个；②最高位是2，后位必须有偶数个2偶数个3，这样的数有个；③最高位是3，后位必须有奇数个2奇数个3，这样的数有个。各类情形，没有重复的数。由加法法则，得满足的递推关系为：（3）对2出现偶数次3出现奇数次的n位四进制数，考虑最高位，可分为三种情况：①最高位是0或1，则在后续的个数字中2出现偶数次3出现奇数次，这样的四进制数共有个；②最高位是2，后位必须有奇数个2奇数个3，这样的数有个；③最高位是3，后位必须有偶数个2偶数个3，这样的数有个。各类情形，没有重复的数。由加法法则，得满足的递推关系为：（4）对2出现奇数次3出现奇数次的n位四进制数，考虑最高位，可分为三种情况：①最高位是0或1，则在后续的个数字中2出现奇数次3出现奇数次，这样的四进制数共有个；②最高位是2，后位必须有偶数个2奇数个3，这样的数有个；③最高位是3，后位必须有奇数个2偶数个3，这样的数有个。各类情形，没有重复的数。由加法法则，得满足的递推关系为：故可得联立方程组：初始条件为：，对应的母函数分别为：，，，，从而可以得到关于母函数的联立方程：解得：则即的系数，所以（）6．试求由a，b，c三个字母组成的n位符号串中不出现aa图像的符号串的数目。解：假设符合条件的符合串的数目为，考虑第1位数的数值，有两种情况：（1）第1位为a，则第2位只能是b或c，余下的位满足条件的有个；根据乘法法则，这类情况总共有个；（2）第1位为b或c，则余下的满足条件的有个；根据加法法则，可得递推关系，且；对应的特征方程为：，解得：，因此，通解为，代入初始条件，，，解得，故7．利用递推关系解行列式：解：设行列式的值为，则故可得到递推关系：对应齐次方程的特征方程为：，解得：，对于通解，根据a与b的关系分情况讨论：（1），则通解为，代入初始条件，得，，解得，所以行列式的值为；（）。（2）：则通解为：，代入初始条件，得，，解得，，，所以行列式的值为：（）8．在方格的棋盘上，放有k枚相同的车，设任意两枚不能相互吃掉的放法数为，证明满足递推关系：证明：考虑第一行有两种情况：（1）有1枚棋子，则余下的枚放在余下的棋盘上，有种放法；考虑棋子不能同行同列，棋盘上放了枚棋子后，要在第一行放1枚棋子，则该棋子可放的位置有：种，根据乘法法则，这类放法共有：（2）没有棋子，则k枚棋子要放在余下的棋盘上，有放法；根据加法法则，可得。9．在方格的棋盘中，令表示棋盘里正方形的个数（不同的正方形可以叠交），试建立满足的递推关系。解：设每个正方形方格的面积为单位1，当棋盘大小由变为时，所增加的正方形为（1）个面积为1的小正方形；（2）包含（1）中小正方形且面积为4的正方形有：个；（3）包含（1）中小正方形且面积为9的正方形有：个；……（n）所有方格组成的最大的正方形（面积为），只有1个；因此，可以得到递推关系：，即满足的递推关系为：10．过一个球的中心做n个平面，其中无3个平面过同一直径，问这些平面可把球的内部分成多少个两两无公共部分的区域？解：设这n个平面把球内部分成个两两无公共部分的区域，显然：，，。当时，去掉所给的n个平面中的一个平面P，则剩下的平面把球分成个区域，。现把平面P放回原处，则P与其余个平面都相交，且所得的条交线都不同（因为无3个平面过同一直径），这条交线把平面P分成部分，每部分把原来的一个区域划分成两个区域，故把平面P放回原处后增加了个区域，从而满足递推关系：解得：11．设空间的n个平面两两相交，每3个平面有且仅有一个公共点，任意4个平面都不共点，这样的n个平面把空间分割成多少个不重叠的区域？解：设n个的平面把空间所分割成的不重叠的区域数为；显然，，，，当时，去掉所给的n个平面中的一个平面P，则剩下的平面把空间分割成个区域，。现把平面P放回原处，则P与其余个平面都相交，且所得的条交线两两相交（每3个平面只有一个公共点），且任意三条不共点（任意4个平面都不共点），这条交线将平面P分割成：（个）不重叠的区域（n条直线能将平面分割成个不重叠的区域，参见习题第13题）每部分把原来的一个区域划分成两个区域，故把平面P放回原处后增加了个区域，从而满足递推关系：下面解递推方程，采用迭代法：（见第一章习题第25题，）12．相邻位不同为0的n位二进制数中一共出现了多少个0？解：假设符合条件的n位二进制数有个，出现的0的个数为，考虑第一位数，有两种情况：（1）第1位数为0，则第2位必为1，余下的位的二进制数有个，故这类情况，共出现0的个数为：；（2）第1位数为1，则余下的位二进制数有个，这类情况下，共出现0的个数位：根据加法法则，可得到递推关系：，有递推关系可反推得：，所以，，令，，则，对应的齐次方程的特征方程为，解得，所以非齐次方程的通解为：，同理，的通解为：，则非齐次方程的通解为：，代入初始条件，可得：，，，，解得：，，，，所以，13．平面上有两两相交，无3线共点的n条直线，试求这n条直线把平面分成多少个区域？解：设这n条直线，把平面分成个区域，显然。当时，去掉所给的n条直线中的一条直线L，则剩下的条直线把平面划分成个区域。现在把L放回原处，则L与其余条直线都相交，且所得的个交点都不同（无三线共点）。这个交点把直线L分成n段，每段把原来的区域划分成两个小区域，故把直线L放回原处后增加了n个区域，因此满足递推关系：，用迭代法解：所有式子相加，便可得：14．证明Fibonacci数列的性质，当时，（1）（2）（3）（4）证明：（1）用数学归纳法：时，，命题成立；时，，命题成立；假设当时，命题成立，即，当时，所以，时，命题也成立；由归纳原理知，命题成立。方法二：（2）证明：定义，则有，并且，因此有：将上述式子两端各自相加并代入，即可得：（3）证明：与（2）类似，，同理，将上述式子两端各自相加并代入，即可得：（4）证明：采用数学归纳法。时，，命题成立；时，，命题成立；假设时，命题成立，即，当时，即时，命题也成立，根据归纳法，命题成立。15．证明：（1）当时，（2）当时，证明：用数学归纳法。（1）当时，，等式成立；当时，，等式成立；假设当时，等式成立，即，则，时有即当时，等式也成立，由归纳原理知，等式成立。（2）由Fibonacci数列的定义，反推得当时，，等式成立，当时，，等式成立；假设当时，等式成立，即，则，时有即当时，等式也成立，由归纳原理知，等式成立。16．有2n个人在戏院售票处排队，每张戏票票价为5角，其中n个人各有一张5角钱，另外n个人各有一张1元钱，售票处无零钱可换。现将这2n个人看成一个序列，从第一个人开始，任何部分子序列内，都保证有5角钱的人不比有1元钱的人少，则售票工作能依次序进行，否则，只能中断，而请后面有5角钱的人先上来买票。前一种情况，售票工作能顺利进行，对应的序列称为依次可进行的。问有多少种这样的序列？解：将持有5角的人看为1，持有1元的人看为0，则该问题等价于：在由n个1和n个0组成的2n位二进制数中，从左到右扫描，1的累计数不小于0的累计数，求这样的二进制数的个数。见P73例3.4.11。这样的序列有：（种）17．用表示具有整数边长且周长为n的三角形的个数，证明证明：三边构成三角形的充要条件是：任二边之和都大于第三边。（1）当n是偶数时一方面，对于任一周长为的整边三角形，设其两较短边为a、b，较长边为c（三边可以相等，即可以a=b=c），则必有a+b>c。于是可以知道：，从而三边a+1，b+1，c+1可构成一周长为n的整边三角形，因此，有。另一方面，对于任一周长为n的整边三角形，设其两较短边为a、b，较长边为c（三边可以相等，即可以a=b=c），则必有a+b>c。由于n是偶数，故可设；由，可知，即，因此，从而，因此，即，所以，，因此三边可构成一周长为的整边三角形，因此有：。综上所述，就可以得到：。（2）当n为奇数时对于任一周长为n的整边三角形，设其两较短边为a、b，较长边为c（三边可以相等，即可以a=b=c），则必有a+b>c。由于n是奇数，故可设（因为）；由于，所以，即，故，从而，因此，即，所以，即，可分两种情况来讨论：①这时能构成一周长为的整边三角形，这种情况下，周长为n的整边三角形有个。②这时三边不能构成周长为的整边三角形，而此时有：，因此。当为偶数时这时三边有种构成方案，即“”，“”，“”，……，“”因此三边a，b，c也有种构成方案，它们可构成周长为n的整边三角形的数目为：（个）当为奇数时这时三边也有种构成方案，即“”，“”，“”，……，“”因此三边a，b，c也有种构成方案，它们可构成的周长为n的整边三角形的数目为：（个）综上，满足条件的周长为n的整边三角形的个数为：（个）根据加法法则，由①②知，当n为奇数时周长为n的整边三角形的总个数为：（个）18．（1）证明边长为整数且最大边长为r的三角形的个数是（2）设为边长不超过的三角形的个数，为边长不超过的三角形的个数，求和的解析表达式。（1）证明：设三角形的三边长分别为，且，显然，下面对r进行讨论。时，这时符合条件的三角形只有1个，即“”，显然，结论成立。时，符合条件的三角形只有2个，即“”、“”，这时，结论成立。①为偶数时，若，则有k种方案，即“”，“”，……，“”；若，则有k种方案，即“”，“”，……，“”；若，则有种方案，即“”，“”，……，“”；若，则有种方案，即“”，“”，……，“”；………………若，则有1种方案，即“”；若，则有1种方案，即“”；综上，为偶数时，总的方案数为：，结论成立。②为奇数时，若，则有种方案，即“”，“”，……，“”；若，则有k种方案，即“”，“”，……，“”；若，则有k种方案，即“”，“”，……，“”；若，则有种方案，即“”，“”，……，“”；若，则有种方案，即“”，“”，……，“”；………………若，则有1种方案，即“”；若，则有1种方案，即“”；综上，为奇数时，总的方案数为：，结论成立。（2）解：令则边长不超过的三角形的个数为：，而边长不超过的三角形的个数，于是有：，，初始条件为：，，用迭代法解递推关系：，将上面式子两端分别相加，便可得：同理：，将上面式子两端分别相加，便可得：19．从1到n的自然数中选取k个不同且不相邻的整数，设此选取的方案数为。（1）求的递推关系及其解析表达式；（2）将1与n也算作相邻的数，对应的选取方案数记作，利用求。解：（1）对元素n来说，不外乎两种情况：①n被选进某一k元子集。这种情况下，就不能选进这一k元子集，故其余个元素得从中选取，共有种选法。②n没有选进任一k元子集。这种情况下，k元素子集中的k个数可以从中去选取，故有种选法。由加法法则可得：根据组合公式，我们推断，它满足递推公式，下面利用递推关系对n进行归纳证明。规定，，当时，显然有，，当时，，则，，所以，时，有成立。假设小于n时结论成立，则当n时就有结论也成立，由归纳原理知，所以对一切正整数n，有方法二：已知是中的没有两个连续整数的k元子集的数目。先在中任取k个不相邻元素构成组合，不失一般性，可设，则，令，则　且有　，因此所求组合数为从1至中任取k个的组合数，即有。（注意：若，则符合条件的组合数不存在）（2）若1与n算是相邻的数时，从1到n的自然数中选取k个不同且不相邻的数的方案数是从1到n的自然数中选取k个不同且不相邻的数的方案数，去掉不满足此假定的选数方案数：即所选k个数中既有数1又有数n，这时数2和n-1都不能入选（因它们分别与数1和数n相邻），因此，其余个数只能从剩下的个数中选取，其方案数为。所以，在1与n算是相邻的数时，从1到n的自然数中选取k个不同且不相邻的数的总方案数20．球面上有n个大圆，其中任何两个圆都相交于两点，但没有三个大圆通过同一点，用表示这些大圆所形成的区域数，例如，，试证明：（1）；（2）解：（1）当，增加1个大圆C，则C与其他n个圆都相交于2点，且都不相同，共有个交点，这个交点，把圆C分成段弧，每段弧把原来的区域一分为二，故增加圆C后将增加个区域，故可得递推公式：（2）用迭代法求解递推公式。因为：，将这些式子相加，可得，所以。21．（1）试计算从平面坐标点到点在对角线OA之上但可以经过OA上的点的递增路径的条数。（2）试证明从平面坐标上点到点在对角线OA之上且不触及OA的递增路径的条数是。解：（1）从到的最短路径必然是由n个x和n个y组成的长度为2n的路径，将x看为0，y看为1，则从平面坐标点到点在对角线OA之上但可以经过OA上的点的递增路径是：由n个1和n个0组成的2n位的二进制数，并且从左到右扫描，1的累计数不小于0的累计数。见P73例3.4.11。这样的最短路径有：（条）。（2）因为不触及对角线OA，所以满足条件的最短路径必然要经过点和点，且在对角线PB之上，但可经过PB上的点，即与（1）情况类似，故这样的路径有：。22．有多少个长度为n的0与1串，在这些串中，既不包含子串010，也不包含子串101？解：设长度为n而满足条件的串有个，显然，，，可将串分为两类：（1）最后两位相同。这种串可由长为而满足条件的串a，再加上与a的末位相同的数字构成，如：，因此这种串共有个。（2）最后两位不同。这种串可由长为的满足条件的串a，再加上与a的末位先同而后异的两个数字构成，例如：，，因此这种串共有个。由加法法则，可得到递推关系：由递推关系反推，可得，所以，第二版新增的部分习题7．求由0，1，2，3作成的含有偶数个2的n可重排列的个数。解：方法一（利用递推关系）设由0,1,2,3作成的含有偶数个2的n可重复排列共有个，显然=3，当n≥2时，在满足题意的个n-可重复排列中，根据第1位数可分为两种情况：（1）第1位为2，则剩下的n-1位，只能含有奇数个2，这样的数共有；（2）第1位不为2，则剩下的n－1位，含有偶数个2，这样的数有个。故由加法原则，有∴=…==所以　　。显见当n=1时，上式仍成立，从而有方法二（母函数法）对应的指母函数为：所以，24．设把2n个人分成n个组且每组恰好有2个人的不同分组方法有种，请给出满足的递推关系并求解。解：显然，，考虑2个人，（1）2个人单独成一组，则剩下的2(n-1)个人的分组方法有种；（2）2人在不同的组中，则得从剩下的2(n-1)个人种选出2人，有种取法，再将2人分到已有的2组中，有2种分法，剩下的2(n-2)人有种分法；根据乘法法则和加法法则，有：解得：（用归纳法证明）方法二：先将组看为是不同的，2n个不同的人分到n个组，每组2人的分法有：，又组是没有区别的，所以分法应为：习题四（容斥原理）1．试求不超过200的正整数中素数的个数。解：因为，所以不超过200的合数必是的倍数，而且其因子又不可能都超过13。设为数i不超过200的倍数集，，则，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，…，，…，，所以但这41个数未包括本身，却将非素数1包含其中，故所求的素数个数为：2．问由1到2000的整数中：（1）至少能被2，3，5之一整除的数有多少个？（2）至少能被2，3，5中2个数同时整除的数有多少个？（3）能且只能被2，3，5中1个数整除的数有多少个？解：设为1到2000的整数中能被i整除的数的集合，，则，，，，，，，（1）即求，根据容斥原理有：（2）即求，根据容斥原理有：（3）即求，根据Jordan公式有：3．求从1到500的整数中能被3和5整除但不能被7整除的数的个数。解：设为1到500的整数中能被i整除的数的集合，，则，，，，，，，满足条件的整数个数为：，根据容斥原理有：4．某人参加一种会议，会上有6位朋友，他和其中每一人在会上各相遇12次，每二人各相遇6次，每三人各相遇4次，每四人各相遇3次，每五人各相遇2次，与六人都相遇1次，一人也没遇见的有5次。问该人共参加几次会议？解：设S为该人参加的所有会议组成的集合，设表示该人与第i个朋友相遇的所有会议构成的子集，，则，，，，，，则，则该人共参加会议次数为：（次）。5．n位的四进制数中，数字1，2，3各自至少出现一次的数有多少个？解：设S表示所有n位四进制数构成的集合，为不出现i的数的集合，，则，，，则由逐步淘汰原理，可得6．某照相馆给n个人分别照相后，装入每人的纸袋里，问出现以下情况有多少种可能？（1）没有任何一个人得到自己的照片；（2）至少有一人得到自己的相片；（3）至少有两人得到自己的照片；解：以任一种装法为元素构成的集合记为S，则。设表示第i个人拿到自己的照片的所有装法组成的集合。则公共数，同理，……，（1）即求，由问题的性质可知，这是一个错排问题，所以（2）即求，方法二：问题即：将所有可能的分配方案－没有任何一人得到自己的照片的方案，则，符合条件的方案数为：，方法三：问题即求：（3）问题即求：，7．把排成相同字母互不相邻的排列，有多少种排法？解：设为所有排列的组成的集合，则，设：表示排列中有相邻i个元素都是a的排列集合；；设：表示排列中有相邻i个元素都是