《组合数学》姜建国著（第二版）.docx

本文格式为Word版，下载可任意编辑《组合数学》姜建国著（第二版） 组合数学（其次版） 组合数学(第2版)-姜建国,岳建国 习题一（排列与组合） 1．在1到9999之间，有多少个每位上数字全不一致而且由奇数构成的整数？ 解：该题相当于从“1，3，5，7，9”五个数字中分别选出1，2，3，4作排列的 方案数； （1）选1个，即构成1位数，共有P51个； （2）选2个，即构成两位数，共有P52个； （3）选3个，即构成3位数，共有P53个； （4）选4个，即构成4位数，共有P54个； 由加法法那么可知，所求的整数共有：P51?P52?P53?P54?205个 2．比5400小并具有以下性质的正整数有多少个？ （1）每位的数字全不同； （2）每位数字不同且不展现数字2与7； 解：（1）比5400小且每位数字全不同的正整数； 按正整数的位数可分为以下几种处境： ① 一位数，可从1～9中任取一个，共有9个； ② 两位数十位上的数可从1～9中选取，个位数上的数可从其余9个数 字中选取，根据乘法法那么，共有9?9?81个； ③ 三位数。

百位上的数可从1～9中选取，剩下的两位数可从其余9个数 中选2个举行排列，根据乘法法那么，共有9?P92?648个； ④ 四位数又可分三种处境： ? 千位上的数从1～4中选取，剩下的三位数从剩下的9个数字中选 3个举行排列，根据乘法法那么，共有4?P93?2022个； ? 千位上的数取5，百位上的数从1～3中选取，剩下的两位数从剩 下的8个数字中选2个举行排列，共有3?P82?168个； ? 千位上的数取5，百位上的数取0，剩下的两位数从剩下的8个数 字中选2个举行排列，共有P82?56个； 根据加法法那么，得志条件的正整数共有： 9?81?648?2022?168?56?2978个； 第1页（共93页） 组合数学（其次版） （2）比5400小且每位数字不同且不展现数字2与7的正整数； 按正整数的位数可分为以下几种处境：设A?{0,1,3,4,5,6,8,9} ① 一位数，可从A?{0}中任取一个，共有7个； ② 两位数十位上的数可从A?{0}中选取，个位数上的数可从A中其余7 个数字中选取，根据乘法法那么，共有7?7?49个； ③ 三位数。

百位上的数可从A?{0}中选取，剩下的两位数可从A其余7 个数中选2个举行排列，根据乘法法那么，共有7?P72?294个； ④ 四位数又可分三种处境： ? 千位上的数从1，3，4中选取，剩下的三位数从A中剩下的7个 数字中选3个举行排列，根据乘法法那么，共有3?P73?630个； ? 千位上的数取5，百位上的数从0，1，3中选取，剩下的两位数从 A中剩下的6个数字中选2个举行排列，共有3?P62?90个； 根据加法法那么，得志条件的正整数共有：7?49?294?630?90?1070个； 3．一教室有两排，每排8个座位，今有14名学生，问按以下不同的方式入座，各有多少种做法？ （1）规定某5人总坐在前排，某4人总坐在后排，但每人概括座位不指定； （2）要求前排至少坐5人，后排至少坐4人 解：（1）由于就坐是有次序的，全体是排列问题 5人坐前排，其坐法数为P(8,5)，4人坐后排，其坐法数为P(8,4)， 剩下的5个人在其余座位的就坐方式有P(7,5)种， 根据乘法原理，就座方式总共有： P(8,5)P(8,4)P(7,5)?28449792000（种） （2）因前排至少需坐6人，最多坐8人，后排也是如此。

可分成三种处境分别议论： ① 前排恰好坐6人，入座方式有C(14,6)P(8,6)P(8,8)； ② 前排恰好坐7人，入座方式有C(14,7)P(8,7)P(8,7)； ③ 前排恰好坐8人，入座方式有C(14,8)P(8,8)P(8,6)； 各类入座方式彼此不同，由加法法那么，总的入座方式总数为： C(14,6)P(8,6)P(8,8)?C(14,7)P(8,7)P(8,7)?C(14,8)P(8,8)P(8,6) ?10461394944000? 典型错误： 先选6人坐前排，再选4人坐后排，剩下的4人坐入余下的6个座位故总的入坐方式共有：C(14,6)P?8,6?C(8,4)P?8,4?P?6,4?种 第2页（共93页） 组合数学（其次版） 但这样计算无疑是有重复的，例如恰好选6人坐前排，其余8人全坐后排，那么上式中的C(8,4)P?8,4?就有重复 4．一位学者要在一周内安置50个小时的工作时间，而且每天至少工作5小时， 问共有多少种安置方案？ 解：用xi表示第i天的工作时间，i?1,2,,7，那么问题转化为求不定方程 x1?x2?x3?x4?x5?x6?x7?50的整数解的组数，且xi?5，于是又可以转 化为求不定方程y1?y2?y3?y4?y5?y6?y7?15的整数解的组数。

该问题等价于：将15个没有识别的球，放入7个不同的盒子中，每盒球数不限，即相异元素允许重复的组合问题 故安置方案共有：RC(?,15)?C(15?7?1,15)?54264 （种） ? 另解： 由于允许yi?0，所以问题转化为长度为1的15条线段中间有14个空，再加上前后两个空，共16个空，在这16个空中放入6个“＋”号，每个空放置的“＋”号数不限，未放“＋”号的线段合成一条线段，求放法的总数从而不定方程的整数解共有： RC(?,6)?C(16?6?1,6)?21?20?19?18?17?16?54264（组） 6?5?4?3?2?1 即共有54 264种安置方案 5．若某两人拒绝相邻而坐，问12个人围圆周就坐有多少种方式？ 解：12个人围圆周就坐的方式有：CP(12,12)?11!种， 设不愿坐在一起的两人为甲和乙，将这两个人相邻而坐，可看为1人，那么这样的就坐方式有：CP(11,11)?10!种；由于甲乙相邻而坐，可能是“甲乙”也可能是“乙甲”；所以 那么得志条件的就坐方式有：11!?2?10!?32659200种 6．有15名选手，其中5名只能打后卫，8名只能打前锋，2名只能打前锋或后卫，今欲选出11人组成一支球队，而且需要7人打前锋，4人打后卫，试问有多少种选法？ 解：用A、B、C分别代表5名打后卫、8名打前锋、2名可打前锋或后卫的集合， 那么可分为以下几种处境： （1）7个前锋从B中选取，有C87种选法，4个后卫从A中选取，有C54种， 根据乘法法那么，这种选取方案有：C87C54种； （2）7个前锋从B中选取，从A中选取3名后卫，从C中选1名后卫， 第3页（共93页） 组合数学（其次版） 1 根据乘法法那么，这种选取方案有：C87C53C2种； （3）7个前锋从B中选取，从A中选取2名后卫，C中2名当后卫， 根据乘法法那么，这种选取方案有：C87C52种； （4）从B中选6个前锋，从C中选1个前锋，从A中选4个后卫， 1C54种； 根据乘法法那么，这种选取方案有：C86C2 （5）从B中选6个前锋，从C中选1个前锋，从A中选3个后卫，C中剩 13C5下的一个当后卫，选取方案有：C86C2种； （6）从B中选5个前锋，C中2个当前锋，从A中选4个后卫， 选取方案有：C85C54种； 根据加法法那么，总的方案数为： 311135C87C54?C87C5C2?C87C52?C86C2C54?C86C2C5?C8C54?1400 7．求(x?y?2z?w)8开展式中x2y2z2w2项的系数。

解：令a?x,b??y,c??2z,d?w，那么(a?b?c?d)8中a2b2c2z2项的系数为 ?8?8!7!82222(x?y?2z?w)x(?y)(?2z)w的系数， ?，即中， ????2222?2!2!2!2!2因此，x2y2z2w2的系数为：7!2(?1)2(?2)2?10080 8．求(x?y?z)4的开展式 解：n?4,t?3，开展式共有RC(?,4)?C(4?3?1,4)?15（项）， 所以， ?4?4?4?4?4?4?4?3?4?3(x?y?z)???x???y???z???xy???xz400040004310301???????????4?22?4?22?4?2???xy???xz???xyz220222211??????4?4?3?4?3?4??4?22??xy?xz?xyz????????xyz130103112121?????????4?3?4?3?4?22???yz???yz???yz?013??031??022??x4?y4?z4?4x3y?4x3z?4xy3?4xz3?4yz3?4y3z?6x2y2?6x2z2?6y2z2?12x2yz?12xyz2?12xy2z 36x3x49．求(x1?x2?x3?x4?x5)10开展式中x2的系数。

?10?10!36x3x4解：x2的系数为： ???840 ??03160?3!1!6!第4页（共93页） 组合数学（其次版） 10．试证任一整数n可唯一表示成如下形式： n??aii!i?1,0?ai?ii,?1,2 ,证明：（1）可表示性 令M?{(am?1,am?2, N?{0,1,2,f(am?1,am?2,,a2,a1)|0?ai?i,i?1,2,,m?1}，鲜明M?m!， ,m!?1}，鲜明N?m!， ,a2,a1)?am?1(m?1)!?am?2(m?2)!??a22!?a11!， 定义函数f:M?N， 0?0(m?1)!?0(m?2)!??02!?01!?am?1(m?1)!?am?2(m?2)!??a22!?a11!?(m?1)(m?1)!?(m?2)(m?2)!??m!?(m?1)!?(m?1)!?(m?2)!?,a2,a1)?m!?1， ,a2,a1)， 鲜明， ?22!?11!?3!?2!?2!?1!?m!?1 即0?f(am?1,am?2,由于f是用普遍乘法和普遍加法所定义的，故f无歧义，断定是一个函数。

从而必有一确定的数K(0?K?m!?1)，使得K?f(am?1,am?2,为了证明N中的任一数n均可表示成n??aii!的形式， i?1只需证明f是满射函数即可又由于f是定义在两个有限且基数相等的函数上，因此假设能证明f单射，那么f必是满射 假设f不是单射，那么存在(am?1,am?2,(am?1,am?2,,a2,a1)?(bm?1,bm?2,K0?f(am?1,am?2,,a2,a1),(bm?1,bm?2,,b2,b1) ,b2,b1，故必存在)j?m?1，使得 。