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

组合数学题目及标准答案组合数学例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)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 个的方案数。

组合数学试题及答案一、选择题（每题3分，共30分）1. 在组合数学中，从n个不同元素中取出m个元素的组合数表示为：A. C(n, m)B. P(n, m)C. A(n, m)D. nCm答案：A2. 如果一个集合有10个元素，从中任取3个元素的组合数为：A. 120B. 210C. 1001D. 1000答案：B3. 组合数学中的排列数与组合数的关系是：A. P(n, m) = C(n, m) * m!B. C(n, m) = P(n, m) / m!C. P(n, m) = C(n, m) + m!D. P(n, m) = C(n, m) * n!答案：B4. 以下哪个公式用于计算组合数？A. C(n, m) = n! / (m! * (n-m)!)B. P(n, m) = n! / (n-m)!C. A(n, m) = n! / (m! * (n-m)!)D. B(n, m) = n! / (m! * (n-m)!)答案：A5. 如果一个集合有8个元素，从中任取2个元素的排列数为：A. 28B. 56C. 8!D. 7!答案：B6. 组合数学中，排列数P(n, m)的定义是：A. 从n个元素中取出m个元素的所有可能的排列方式的数量B. 从n个元素中取出m个元素的所有可能的组合方式的数量C. 从n个元素中取出m个元素的所有可能的排列方式的数量，不考虑顺序D. 从n个元素中取出m个元素的所有可能的组合方式的数量，考虑顺序答案：A7. 以下哪个公式用于计算排列数？A. P(n, m) = n! / (n-m)!B. C(n, m) = n! / (m! * (n-m)!)C. A(n, m) = n! / (m! * (n-m)!)D. B(n, m) = n! / (m! * (n-m)!)答案：A8. 如果一个集合有15个元素，从中任取5个元素的组合数为：A. 3003B. 3000C. 1365D. 15504答案：D9. 组合数学中的二项式系数表示为：A. C(n, m)B. P(n, m)C. A(n, m)D. B(n, m)答案：A10. 以下哪个公式用于计算二项式系数？A. C(n, m) = n! / (m! * (n-m)!)B. P(n, m) = n! / (n-m)!C. A(n, m) = n! / (m! * (n-m)!)D. B(n, m) = n! / (m! * (n-m)!)答案：A二、填空题（每题2分，共20分）1. 从5个不同元素中取出3个元素的组合数为 ________。

第一章：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）=35x 1+x 2+x 3+x 4=3 的非负整数解，其个数为F （4，3）=20x 1+x 2+x 3+x 4=2 的非负整数解，其个数为F （4，2）=10x 1+x 2+x 3+x 4=1 的非负整数解，其个数为F （4，1）=4x 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章 排列与组合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 -++种方案。