1.4组合5 因此，(）就表示了从n个元素中一次取r个元素的可能取法的数目，如果不 考虑抽取顺序的话 例4a从20人当中选择3人组成委员会，一共有多少种选法？ 6 解。一共有()-0X91=110种选法 ■ 例4b有个12人组成的团体，其中5位女士，7位男士，现从中选取2位女士， 3位男士组成一个委员会，问有多少种取法？另外，如果其中有2位男士之间有矛 盾，并且坚决拒绝一起工作，那又有多少种取法？ 解：有（⑨）种方法选取女士，有()种方法选取男士，根据基本计数法则一共 有日们-兰9-种方式选取2位女士3位月士 现在来看如果有两位男士拒绝一起工作，那么选取3位男士的（③）=35种方 法中，有（份）()=5种同时包含了该两位男士，所以，一共有35-5=30种选取方 法不同时包含那两位有矛盾的男士；另外，选取女士的方法仍是(=0种，所以， 共有30×10=300种选取方式. 例4c假设一排n个天线中，有m个是失效的，另n-m个是有效的，并且假 设所有有效的天线之间不可区分，同样，所有失效的天线之间也不可区分.问有多少 种排列方式，使得没有两个连续的天线是失效的？ 解：先将n一m个有效天线排成一排，既然没有连续两个失效的，那么两个有 效天线之间，必然至多放置一个失效的.也即，在n-m+1个可能位置中（如图1.1 中的星号)，选择m个来放置失效天线.因此有（一m+1种可能方式确保在两 个失效天线之间至少存在一个有效天线。 *1*1*1.1*1* :有效天线 7 :放最多一个失效天线 图1.1天线的排列 以下是一个非常有用的组合恒等式： (）=(-）+(,)1≤r≤n (4.1)
6第1章组合分析 上述恒等式可用分析的方法证明，也可从组合的角度来证明.设想从个元素中取 ?个，一共有()种取法.从另一个角度来考虑，不妨设这几个元素里有一个特殊 的，记为元素1，那么取r个元素就有两种结果，取元素1或者不取元素1.取元素 1的方法一共有(（？二）种从n-1个元素里面取r-1个片不取元素1的方法一 共有(，)种（从去掉元素1的剩下n-1个元素中取r个）.两者之和就是从n 个元素里取r个的方法之和，所以恒等式成立. 值(C）经常也称为二项式亲(教(bnomial),这是因为它们是以下的二 项式定理中重要的系数， 二项式定理 e+r2 (4.2) 以下提供二项式定理的两个证明方法，其一是数学归纳法，其二是基于组合考 虑的证明 二项式定理的归纳法证明n=1时，(4.2)式化为x+g=(y+(什x- y+x假设(4.2)式对于n-1成立，那么对于n e+严=在+e+m-1=e+0（n)1- 、k k=0 8 -y+ k=0 在前面的求和公式里令=k+1,后面的求和公式里令i=k,那么 a+-=》w+（w +》+:4 =”+∑()y-+=∑(g)ry- 0 这样就证明了等式 二项式定理的组合法证明考虑乘积(c1+h)(2+2).(xn+)展开后一
1.5多项式亲数7 共包含2”项，每一项都是n个因子的乘积，而且每一项都包含因子或，例如： (x1+1)(x2+2)=工1x2+工12+hx2+12 这2n项和里面，一共有多少项含有k个x和n一k个：？ 含有k个：和n一k个站的每一项对应了从n个元素1，x2,·,正n里取k 个元素的取法.因此一共有()个这样的项这样，令=x,=y,=1,.,n 可以看出 +-三阅y 例4d展开(x+w) 解： e+3=()y3+()ry2+()v+(③)v =y3+3xy2+3x2y+x3 ■9☐ 例4e一个有n个元素的集合共有多少子集？ 解：含有k个元素的子集一共有()个，因此所求答案为： 含周-0+r=n 该结果还可以这样得到：给该集合里的每个元素都标上1或0，每种标法都一 对应了一个子集，例如，当把所有元素都标为1时候，就对应着一个含有所有元素 的子集.因为一共有2”种标法，所以一共有2”个子集 上述结论包含了一个元素都没有的子集（也即空集），所以至少有一个元素的子 集一共有2”-1个. 1.5多项式系数 本节考虑如下问题：有n个不同的元素，分成r组，每组分别有n1,2,·,n, 个元素，其中∑1=m,一共有多少种分法？注意到，第一组成员有（)种选 取方法，接下来，选定第一组成员后，选第二组成员时只能从剩下的n一个元素 中选一共有(？，）种取法接下来第三组有（一）种取法，等等因此 根据推广计数法则，将n个元素分成"组的分法总数一共是： ()）(（-m-n-w-
8第1章组合分析 “a-a二0a-m-2n业 n! (n-n1)！ 0lnr！ minaln! 用另一个方法也可以得到此结果：有n个球，其中n1个标有记号1,2个标 有记号2，.，nr个标有记号r.具有相同标号的球之间是不可分辨的.现在设有n 个对象，记为1,2，·，n.设想一个球里也只可放一个对象.把n个对象放到r个球 里边，等价于将n个对象分成"个组，因为每个球有一个标号，这个标号就是这个 对象的组号.现在问一共有多少不同的分组方式呢？先把这些对象排成一个固定的 顺序，然后将这些球进行排列.当球的排列确定以后，每一个对象就对应一个球的编 号.这就等价于将n个对象分成？个组，每个对象的组号就是这个对象所对应的球 号.这些排列数就是这n个对象的分组数.在1.3节里讨论了n个对象的排列数的 10计数方法，其中具有相同球号的球之间是不可分辨的.在这种情况下，几个球的排列 数为n1nr可 nI 记号 如果n1+2+.+n=n,定义(n1,2”,m,）为： (n n! (n1,2”,n)=n1ln2In 因此（，”，m）表示了n个不同的元素分成大小分别为 n1,n2,.,nr的r组的方法数， 例5a某小城市的警察局有10名警察，其中需要5名警察在街道巡逻，2名警 察在局里值班，另3名留在局里待命。问把10名警察分成这样的3组共有多少种 不同分法？ 解：一共有101/(512！3！)=2520种分法. 例5b10个小孩要分成A,B两队，每队5人.A队去参加一场比赛，B队则去 参加另一场比赛，一共有多少种分法？ 解：一共有10！/(5！5！)=252种分法 ◆ 例5c10个孩子分成两组，每组5人进行篮球比赛，一共有多少种分法？ 解：这个问题与例b不同的是，分成的两组是不用考虑顺序的.也就是说，这 儿没有A,B两组之分，仅仅分成各自为5人的两组，故所求答案为： 10:/515)=126 ■ 2:
*1.6方程的整数解个戴9 下面的定理是二项式定理的推广，其证明留作习题 11☑ 多项式定理 (x1+2+.+x,)n= ne n1,n2,.,n. n 上式的求和号是对一切满足n1+n2+·+nr=n的所有非负整向量 nn2,.,nr)求和 （n1,nz,”,n,）也称为多项式来数(6 icient。) 例5d a++P=(.60g+(0,20=+(0.8,28 +(,i.0t+(1,6)时=+(o品， =x子+x号+x号+2x1x2+2x13+2r2x3 1.6方程的整数解个数1 把n个可分辨的球分到r个可分辨的坛子里，一共有xn种方式.这是因为任一 个球都有可能放到π个坛子中的任一个.现在假设这n个球是不可分辨的，这种情 况下一共有多少种可能结果呢？由于球是不可分辨的，将n个球分到”个坛子里的 结果可以描述为向其(1,2，.，)，其中表示分到第i个坛子里球的数量.因 此，此问题也等同于求出满足1+x2+.+xr=n的非负整数向量(1,2，.，x) 的个数.为了计算它，先考虑该方程的整数解个数：设想有n个不可分辨的球排成 一排，现把它们分成”组，每组都不空.要做到这一点，我们可在n个球之间的n一1 个空隙里选取r一1个（如图1.2所示）.其证明留作习题 12 0*0*0*.*0*0 n个对象0 在处选择r-1个 图1.2n个球之间的n-1个空隙里选取r-1个 1.此处或以后打◆号表示这些材料是可以选读的，或是选作的题目