组合数学题目及答案

4

例 试问(x+y+z)展开后有多少项？

解：这个问题相当于从3种元素中取可重复4-组合，或4个相同的球放进3个不同的盒子里，其组合数为：

C(3+4-1,4)=C(6,4)=15 即：(x+y+z)4共15项。

推论 设多重集S={n1·a1,n2·a2,…,nk·ak}，且对一切i=1,2,…,k有ni≥r，则S的r-组合数是C(r+k-1,r)。

推论 设多重集S={∞·a1, ∞·a2,…, ∞·ak}，r≥k，则S中每个元素至少取一个的r-组合数为

C(r-k+k-1,k-1)=C(r-1,k-1)。

推论 r个相同的球放到k个有标志的盒子中，不允许有空盒，共有C(r-1,k-1)种方案。

例 有一电冰箱厂生产15种电冰箱，将其装入集装箱销往外地，每个集装箱可装18台电冰箱，要求每个集装箱内各种电冰箱至少一台，问可能有多少种不同的集装箱装法？

答案：k=15,r=18

N=C(18-1,15-1)=C(17,14)=680

例 设多重集 S={10·a,10·b,10·c,10·d} ，要求每 种元素在组合中至少出现一次，求S的满足此条件的 10 组合的数目。

解 方程x1+x2+x3+x4=10的正整数解的个数即为 所求。

用变量代换

y1=x1-1，y2=x2-1，y3=x3-1，y4=x4-1， 变换成求 y1+y2+y3+y4=6的非负整数解的个 数。该数目为 C(6+4-1,6)=C(9,6)。

例 设方程x1+x2+x3+x4=20，求满足x1≥3, x2≥1, x3≥0, x4≥5 的整数解的个数。

解 作变量代换

y1=x1-3，y2=x2-1，y3=x3，y4=x4-5，

方程y1+y2+y3+y4=11的非负整数解的个数即为所求，该数为 C(11+4-1,11)=C(14,3)

例 某保密装置须同时使用若干把不同的钥匙才能打开。现有７人，每人持若干钥匙。须４人到场，所备钥匙才能开锁。问①至少有多少把不同的钥匙？②每人至少持几把钥匙？

5

解 ①每３人至少缺１把钥匙，且每３人所缺钥匙不同。故至少共有C(7,3)=35把不同的钥匙。

任一人对于其他６人中的每３人，都至少有１把钥匙与之相配才能开锁。故每人至少持C(6,3)＝20把不同的钥匙。

提供者：潘利强

6