吉林大学组合数学习题答案

组合数学题目及标准答案组合数学例1: 将8个“车”放在8×8的国际象棋棋盘上，如果它们两两均不能互吃，那么称8个“车”处于一个安全状态。

问共有多少种不同的安全状态?解：8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。

用一个排列a1,a2,…,a8 ，对应于一个安全状态，使ai 表示第i 行的ai 列上放置一个“车”。

这种对应显然是一对一的。

因此，安全状态的总数等于这8个数的全排列总数8!＝40320。

例4：n 位客人在晚会上每人与他人握手d 次，d 是奇数。

证明n 偶数。

证：由于每一次握手均使握手的两人各增加一次与他人握手的次数，因此n 位客人与他人握手次数的总和 nd 是偶数—握手次数的2倍。

根据奇偶性质，已知d 是奇数，那么n 必定是偶数。

例４从1到2n 的正整数中任取n +1个，则这n +1个数中，至少有一对数，其中一个是另一个的倍数。

证设n +1个数是a 1, a 2, ···, an +1。

每个数去掉一切2的因子，直至剩下一个奇数为止。

组成序列r 1, r 2,, ···, rn +1。

这n +1个数仍在[1 , 2n ]中，且都是奇数。

而[1, 2n ]中只有n 个奇数，故必有ri =rj = r , 则ai = 2αi r , aj = 2αj r 。

若ai ＞aj ，则ai 是aj 的倍数。

例5 设a 1, a 2, ···, am 是正整数，则至少存在一对k 和l , 0≤k<="" ，使得和ak+1+="">证设Sh = , Sh ≡rh mod m, 0≤rh ≤m -1，h = 1 , 2 , ···, m . 若存在l , Sl ≡0 mod m 则命题成立．否则，1≤rh ≤m -1．但h = 1 , 2 , ···,m ．由鸽巢原理，故存在rk= rl , 即Sk ≡Sl mod m ，不妨设l ＞k ．则Sl －Sk= ak+1+ ak+2+…+ al ≡0 mod m例6 设a 1, a 2, a3是任意三个整数，b1 b2 b3为a1, a2, a3的任一排列，则a1－b1, a2－b2 ,a3－b3中至少有一个是偶数．证由鸽巢原理：a1, a2, a3至少有两个奇偶性相同．则这３个数被２除的余数至少有两个是相同的，不妨设为x; 同样b1, b2, b3中被２除的余数也至少有２个x ．这样a1－b1, a2－b2 , a3－b3被２除的余数至少有一个为０．例7 设a 1, a 2,…, a100是由数字1和２组成的序列, 已知从其任一数开始的顺序10个数的和不超过16．即ai+ ai+1+…+ ai+9≤16，1≤i ≤91。

《组合数学》练习题一参考答案《组合数学》练习题一参考答案一、填空：1.!()!m n P n m m n m =- 2.2)1(-n n 3. 0. 4. 2675.),2,1,0(3)2(2321 =+-+=n c c c a n n n n .6.4207.78.()()!!11...!31!21!111n n n ??-++-+-9.22 10.267二、选择：1. 1—10 A B D D A D A B B C三、计算： 1. 解因为]250[=25, ]450[=12, ]850[=6, ]1650[=3, ]3250[=1, ]6450[=0, 所以, 所求的最高次幂是2(50!)=25+12+6+3+1=47.2. 解由我们最初观察的式子,有614,1124,634,144=??===, 再利用定理1,我们得到24!415,102)15(545,155==??=-?==, 3511642434435=+?=???+=, 5061141424425=+?=??+=. 所以,x x x x x x f 24503510)(23455+-+-=.3. 解：设所求为N ，令}2000,,2,1{ =S ，以A ，B ，C 分别表示S 中能被32?，52?，53?整除的整数所成之集，则53466663133200333 532200053220003532000522000322000 =+?-++=+-???????+???????+???????=+---++==C B A C B C A B A C B A CB A N 4. 解：记7个来宾为1A ，2A ，…，7A ，则7个来宾的取帽子方法可看成是由1A ，2A ，…，7A 作成的这样的全排列：如果i A （1≤i ≤7）拿了j A 的帽子，则把i A 排在第j 位，于是（1）没有一位来宾取回的是他自己的帽子的取法种数等于7元重排数7D ，即等于1854。

测 试 题——组合数学一、选择题1. 把101本书分给10名学生，则下列说法正确的是（）A.有一名学生分得11本书B.至少有一名学生分得11本书C.至多有一名学生分得11本书D.有一名学生分得至少11本书2. 8人排队上车，其中A ，B 两人之间恰好有4人，则不同的排列方法是（）A.!63⨯B.!64⨯C. !66⨯D. !68⨯3. 10名嘉宾和4名领导站成一排参加剪彩，其中领导不能相邻，则站位方法总数为（）A.()4,11!10P ⨯B. ()4,9!10P ⨯C. ()4,10!10P ⨯D. !3!14-4. 把10个人分成两组，每组5人，共有多少种方法（）A.⎪⎪⎭⎫ ⎝⎛510B.⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛510510 C.⎪⎪⎭⎫ ⎝⎛49 D.⎪⎪⎭⎫ ⎝⎛⨯⎪⎪⎭⎫ ⎝⎛4949 5. 设x,y 均为正整数且20≤+y x ，则这样的有序数对()y x ,共有（）个A.190B.200C.210D.2206. 仅由数字1，2，3组成的七位数中，相邻数字均不相同的七位数的个数是（）A.128B.252C.343D.1927. 百位数字不是1且各位数字互异的三位数的个数为（）A.576B.504C.720D.3368. 设n 为正整数，则∑=⎪⎪⎭⎫ ⎝⎛nk k n 02等于（）A.n 2B. 12-nC. n n 2⋅D. 12-⋅n n9. 设n 为正整数，则()k k n k k n 310⎪⎪⎭⎫ ⎝⎛-∑=的值是（）A.n 2B. n 2-C. ()n2- D.0 10. 设n 为正整数，则当2≥n 时，∑=⎪⎪⎭⎫ ⎝⎛-nk k k 22=()A.⎪⎪⎭⎫⎝⎛3n B. ⎪⎪⎭⎫ ⎝⎛+21n C. ⎪⎪⎭⎫ ⎝⎛+31n D. 22+⎪⎪⎭⎫ ⎝⎛n 11. ()632132x x x +-中23231x x x 的系数是（）A.1440B.-1440C.0D.112. 在1和610之间只由数字1，2或3构成的整数个数为（） A.2136- B. 2336- C. 2137- D. 2337- 13. 在1和300之间的整数中能被3或5整除的整数共有（）个A.100B.120C.140D.16014. 已知(){}o n n f ≥是Fibonacci 数列且()()348,217==f f ，则()=10f （）A.89B.110C.144D.28815. 递推关系3143---=n n n a a a 的特征方程是（）A.0432=+-x xB. 0432=-+x xC. 04323=+-x xD. 04323=-+x x16. 已知()⋯⋯=⨯+=,2,1,0232n a n n ，则当2≥n 时，=n a （）A.2123--+n n a aB. 2123---n n a aC.2123--+-n n a aD. 2123----n n a a17. 递推关系()⎩⎨⎧=≥+=-312201a n a a n n n 的解为（） A.32+⨯=n n n a B. ()221+⨯+=n n n aC. ()122+⨯+=n n n aD. ()n n n a 23⨯+=18. 设()⋯⋯=⨯=,2,1,025n a n n ，则数列{}0≥n n a 的常生成函数是（）A.x 215-B. ()2215x - C.()x 215- D. ()2215x -19. 把15个相同的足球分给4个人，使得每人至少分得3个足球，不同的分法共有（）种A.45B.36C.28D.2020. 多重集{}b a S ⋅⋅=4,2的5-排列数为（）A.5B.10C.15D.2021. 部分数为3且没有等于1的部分的15-分拆的个数为（）A.10B.11C.12D.1322. 设n,k 都是正整数，以()n P k 表示部分数为k 的n-分拆的个数，则()116P 的值是（）A.6B.7C.8D.923. 设A ，B ，C 是实数且对任意正整数n 都有⎪⎪⎭⎫ ⎝⎛⋅+⎪⎪⎭⎫ ⎝⎛⋅+⎪⎪⎭⎫ ⎝⎛⋅=1233n C n B n A n ，则B 的值是（）A.9B.8C.7D.624. 不定方程1722321=++x x x 的正整数解的个数是（）A.26B.28C.30D.3225. 已知数列{}0≥n n a 的指数生成函数是()()t t e e t E 521⋅-=，则该数列的通项公式是（）A.n n n n a 567++=B. n n n n a 567+-=C. n n n n a 5627+⨯+=D. n n n n a 5627+⨯-= 二、填空题1. 在1和2000之间能被6整除但不能被15整除的正整数共有_________个2. 用红、黄、蓝、黑4种颜色去图n ⨯1棋盘，每个方格涂一种颜色，则使得被涂成红色的方格数是奇数的涂色方法共有_______种3. 已知递归推关系()31243321≥-+=---n a a a a n n n n 的一个特征根为2，则其通解为___________4. 把()3≥n n 个人分到3个不同的房间，每个房间至少1人的分法数为__________5. 棋盘⨯⨯⨯⨯⨯⨯⨯的车多项式为___________ 6. 由5个字母a,b,c,d,e 作成的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.2. 求在1000和9999之间各位数字都不相同，而且由奇数构成的整数个数。

解：由奇数构成的4位数只能是由1，3，5，7，9这5个数字构成，又要求各位数字都不相同，因此这是一组从5个不同元素中选4个的排列，所以，所求个数为：P(5,4)=120。

1.4. 10个人坐在一排看戏有多少种就坐方式？如果其中有两人不愿坐在一起，问有多少种就坐方式？解：这显然是一组10个人的全排列问题，故共有10！种就坐方式。

如果两个人坐在一起，则可把这两个人捆绑在一起，如是问题就变成9个人的全排列，共有9！种就坐方式。

而这两个人相捆绑的方式又有2种（甲在乙的左面或右面）。

故两人坐在一起的方式数共有2*9！，于是两人不坐在一 起的方式共有 10！- 2*9！。

1.5. 10个人围圆桌而坐，其中两人不愿坐在一起，问有多少种就坐方式？ 解：这是一组圆排列问题，10个人围圆就坐共有10!10 种方式。

两人坐在一起的方式数为9!92⨯,故两人不坐在一起的方式数为：9！-2*8！。

1.14. 求1到10000中，有多少正数，它的数字之和等于5？又有多少数字之和小于5的整数？解：(1)在1到9999中考虑，不是4位数的整数前面补足0， 例如235写成0235,则问题就变为求：x 1+x 2+x 3+x 4=5 的非负整数解的个数，故有 F （4，5）=⎪⎪⎭⎫⎝⎛-+=515456 (2)分为求：x 1+x 2+x 3+x 4=4 的非负整数解，其个数为F （4，4）=35 x 1+x 2+x 3+x 4=3 的非负整数解，其个数为F （4，3）=20 x 1+x 2+x 3+x 4=2 的非负整数解，其个数为F （4，2）=10 x 1+x 2+x 3+x 4=1 的非负整数解，其个数为F （4，1）=4 x 1+x 2+x 3+x 4=0 的非负整数解，其个数为F （4，0）=1 将它们相加即得，F （4，4）+F （4，3）+F （4，2）+F （4，1）+F （4，0）=70。

组合数学课后习题答案问题1求解以下组合数：(a)C(5, 2)(b)C(7, 3)(c)C(10, 5)解答：(a)C(5, 2) 表示从5个不同元素中选取2个的组合数。

根据组合数的定义，我们可以使用公式 C(n, k) = n! / (k! * (n-k)!) 来计算组合数。

计算 C(5, 2)： C(5, 2) = 5! / (2! * (5-2)!) = 5! / (2! * 3!) = (5 * 4 * 3!) / (2! * 3!) = (5 * 4) / 2 = 10所以 C(5, 2) = 10。

(b)C(7, 3) 表示从7个不同元素中选取3个的组合数。

计算 C(7, 3)： C(7, 3) = 7! / (3! * (7-3)!) = 7! / (3! * 4!) = (7 * 6 * 5 * 4!) / (3! * 4!) = (7 * 6 * 5) / 3 = 35 * 2 = 70所以 C(7, 3) = 70。

(c)C(10, 5) 表示从10个不同元素中选取5个的组合数。

计算 C(10, 5)： C(10, 5) = 10! / (5! * (10-5)!) = 10! / (5! * 5!) = (10 * 9 * 8 * 7 * 6 * 5!) / (5! * 5!) = (10 * 9 * 8 * 7 * 6) / (5 * 4 * 3 * 2 * 1) = 252所以 C(10, 5) = 252。

问题2在一个集合 {a, b, c, d, e} 中，求解以下问题：(a)有多少种不同的3个元素的子集？(b)有多少种不同的4个元素的子集？(c)有多少种不同的空集合？(a)在一个集合 {a, b, c, d, e} 中选取3个元素的子集。

子集的元素个数为3，所以我们需要从5个元素中选取3个。

利用组合数的公式 C(n, k) = n! / (k! * (n-k)!)，我们可以计算组合数。

3.1 某甲参加一种会议,会上有6位朋友,某甲和其中每一个人在会上各相遇12次,每两人各相遇6次,每3人各相遇4次,每4人各相遇3次,每5人各相遇2次,每6人各相遇1次,1人也没遇见的有5次,问某甲共参加几次会议?解:设A 为甲与第i 个朋友相遇的会议集.i=1,2,3,4,5,6.则 │∪A i │=12*C(6,1)-6*C(6,2)+4*C(6,3)-3*(6,4)+2*(6,5)-C(6,6) =28甲参加的会议数为 28+5=333.2：求从1到500的整数中被3和5整除但是不能被7整除的数的个数。

解：设 A 3：被3整除的数的集合A 5：被5整除的数的集合 A 7：被7整除的数的集合 所以 ||=||-||=-=33-4=29 3.3 n 个代表参加会议，试证其中至少有2个人各自的朋友数相等解：每个人的朋友数只能取0，1，…，n －1．但若有人的朋友数为0，即此人和其 他人都不认识，则其他人的最大取数不超过n －2．故这n 个人的朋友数的实际取数只 有n －1种可能．，根据鸽巢原理所以至少有２人的朋友数相等．3.4试给出下列等式的组合意义0j j 0(1)=(1), 1n-m-j+1(2)(1)1 j 1(3)...(1) 1 12m l l n m l n m m n l n k m n k l k l n m l n m l m l m l m l m l m l m m m m m l =-=--⎛⎫⎛⎫⎛⎫-≥≥ ⎪ ⎪⎪-⎝⎭⎝⎭⎝⎭---⎛⎫⎛⎫⎛⎫=- ⎪ ⎪⎪--⎝⎭⎝⎭⎝⎭+-++++⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫=-+-+- ⎪ ⎪ ⎪ ⎪ ⎪-+++⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭∑∑ 证明：（1）从n 个不同元素中取k ，使得其中必含有m 个特定元素的方案数为)()(kn mn m k mn --=--。

设这m 个元素为a 1,a 2,…,a m , Ai 为包含a i 的组合（子集），i=1,…,m.1212|...|(...)12 =(...(1))1 2 =(1) m m m l n A A A A A A k n m n m n m n m k k k m k m n l l k ⎛⎫=- ⎪⎝⎭---⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫--++- ⎪ ⎪⎪ ⎪⎪ ⎪⎪⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭-⎛⎫⎛- ⎪⎝⎭ 0ml =⎫ ⎪⎝⎭∑ （2）把l 个无区别的球放到n 个不同的盒子，但有m 个空盒子的方案数为11n l m n m -⎛⎫⎛⎫⎪⎪--⎝⎭⎝⎭令k=n-m ，设A i 为第i 个盒子有球，i=1，2，…k12k 121|...|(...)1k 11211 =(...(1)) 1 2 k k k l A A A A A A k k l k l k k l k k k l k l l k l +-⎛⎫=- ⎪⎝⎭+--+--+--+-⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫--++- ⎪ ⎪⎪ ⎪⎪ ⎪⎪⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭ kj j 0k k-j+1 =(1)j l l =-⎛⎫⎛⎫- ⎪⎪⎝⎭⎝⎭∑ （3）设A i 为m+l 个元素中去m+i 个，含特定元素a 的方案集；N i 为m+l 个元素中取m+i 个的方案数。

１.１ 从{}5021，，，⋅⋅⋅中找两个数{}b a ,，使其满足（1） 5||=-b a ；（2）5||≤-b a解：（1）根据5||=-b a 可得 55-=-=-b a b a 或 则有种种4545 共有90种。

（2）根据5||≤-b a 得 )50,,2,1(,55{⋅⋅⋅∈+≤≤-b a b a b则：当5≤b 时，有1=b ， 61≤≤a ， 则有 6种2=b ， 71≤≤a ， 则有7种3=b ， 81≤≤a ， 则有8种4=b ， 91≤≤a ， 则有 9种5=b ， 101≤≤a ， 则有10种 当455≤<b 时，有6=b ， 111≤≤a ， 则有 11种7=b ， 122≤≤a ， 则有 11种 . . . . . . . . .45=b ， 5040≤≤a ， 则有11种 当5045≤<b 时，有46=b ， 5041≤≤a ， 则有 10种47=b ， 5042≤≤a ， 则有 9种48=b ， 5043≤≤a ， 则有 8种49=b ， 5044≤≤a ， 则有 7种 50=b ， 5045≤≤a ， 则有 6种故：共 种520)678910(21140=+++++⨯1.2 （1）先把女生进行排列，方案为5！，然后把女生看成1个人和7个男生进行排列，总方案数为5！×8！（2）女生不相邻，则先把男生进行排列，方案为7！再把女生插入男生之间的8个空位种的任意5个，总方案数为7！×58P（3）应该是A 女生x 女生y 女生z B,或是B 女生x 女生y 女生z A 的形式，从5个女生中选出3人进行排列，方案为35P ，考虑A,B 可以换位，方案为2×35P ，然后把这个看成一个整体，和剩下的2个女生，5个男生，一共7个人进行排列，总方案数2×35P ×8！1.3 m 个男生,n 个女生,排成一行,其中m,n 都是正整数,若 （a ）男生不相邻（m ≤n+1）；（b ）n 个女生形成一个整体； （c ）男生A 和女生B 排在一起； 分别讨论有多少种方案。