UP uRl; F:集A的r可重组合全体所组成的集, F〓F 此外,还用到一些缩写符号 !=r(r-1)…2·1,(r≥1);0!〓J (n)〓(n-1)…(n一+1),(1≤r≤n);(n)=1, (n) 于是,上述几种排列组合数可由下面的定理确定 定强121.若1≤r≤n,则 Pr o (#)r, (1.2』) cr= (121) Ut (1223) F (1.2H) 证明 (121的第一个证明,在一个无重排列a1a2·,中,a1 可以取n个元中的任何一个,故有n种取法;a1取定之后,a2可以 取其余m-1个元的任何一个,故有n一1种取法;…;在a a2x…,a都取定之后,a+可以取剩下的-:个元的任何 个,故有n-i种取法;;在a1,a2,…,an-1都取定之后,a可以 取剩下的n一r+1个元的任何一个,故有n-7+1种取法 由积则,总的取法数为 )…( 1) 这就是(121) (121的第二个证明.在A的n个元中,任何一个都可居 无重排列的首位,故首元有个取法.当菌元取定后,其他位上的 元只能从A屮另外a-1个元宇选政,故有P种取法,因此由 积则
p〓np= (125) 由此递归关系和初始值Pn-r+I,用数学归纳法即得 (121) (122)的证明.集A的一个r-无重组合就是A的一个 元子集.任葸一个r元子集,譬如说,{a1,a2……,a},都将导出A 的r个r一排列即集{a1,a2…,a,}的全部r无重排列.反之, 集{a1,a2,……,an}的全部r无重排列,仅导出A的一个y-无重组 合。A的r无重排列数为(n)故A的r无重组合数为 ( (L23)的证明.在A的r可重排列中,任意位置可以取A 中任意元,故每个位置都有n种取元的方法。由积则,(12.3)成 立 (124)的证明,与无重组合的情形不一样集A的r可重 组合不能简单地用某一个因子来除无重排列的个数UP来得出 因为不同的可重组合可以给出不同个数的可重排列.例如,当 A冖{a,b,c,d,e时,A的3-可重组合{a,b,c}可给出六个 可重排列: abc, acb, bac, bca, cab, cba; 组合{a,a,b可给出三个可重排列 abA2 baa3 而组合{a,a,a}只给出一个可重排列aa.所以,要采用另外 的办法 (1.24)的第一个证明.把A[1,n]的每一个r可重 组合依其自然顺序写出 ≤c2≤“≤ 令 d=c;十i-1(l≤i≤r) 尽管诸中可能有相同的数但诸d却都是不同的所以d1l2……d 为集B-1,n+r-1]的一个r无重组合.反之,对B的任
一依自然顺序写出的r无重组合4d2…d,由 d-i+1(1≤i≤r) 所定出的诸c的组合就是A的一一个r可重组合.因为这种对应 关系是(1-1)的,所以这两种组合的个数钼同,而前者的个数为 十 故(124)成立 L24)的第二个证明.对A=【l,n]的任一个依自然 顺序写出的r-可重组合i1·,添上A中全部元,再按自然顺序 写出: ··2···(2 i(十1) (12.6) 所以,对毎一可重组合≤i≤…≤有形如(12,6)的唯 序列与之对应,且反之亦然.在序列(12.6)中,于相同的数码 (1≤i≤m-I)的最末那个(如果某数码只出现一次,则“最末 那个“就是它自身)之后画一条竖线,于是(126)成为 2 (126) 这样一来,序列(1.26)与图(12.6)是(1-1)对应的.所以 二者的个数相同.例如,A〓{1,2,3,45}时,A的3可重组 合224所对应的序列(125)为 12223445 按要求画线后变为 1|222}3}441 在(1,26)中,每二个数码之间有一个空隙,共有m+r-1个空 隙.这些空隙中仅有n-1个可以画线,所以形如(12.6)的图 形的个数为 十 这就是所要证的 (124)的第三个证明当「≥2时,把A的全部r可重组合 分为两类,第一类的每一个组合都含有d中某个定元a,第二类的
每一个组合都不含此元a.第一类的每一组合删去一个元4后氽 下老为A的一个(r-1)-可重组合,且反之亦然,故其个数为 F-1.第二类的每一组合是集Aa}的一个r-可重组合,且反之 亦然,故其个数为F-1.因此, F=Fr1+F1-1(n≥2,r≥2) (127) 如果r1,则没有可能重复选取,故 FRa n 如果n=1,则无论「为何正整数,都只有一个r可重组合,故 由(1.27)得 FP+F2-1F1+F1十F F:十F-4十∴十F1+F 十(n-1十 十2 n(n+1) 1.2 2 再者 F〓F-1十F·F2十F1+F F+F十…+F-1十F 2+(r-1) 十1 2+ (129) 在(1.28)和(129)的基础上作归纳假设 瓦+s F 若S<r,k任意 或攵<打5任意 (1210) 由(1.,2,7), F7=F-1+F:1 (r-1) )+r 十r-1
再由 1)立得(1.24) (124)的第四个证明.设集A=[1,n1的r可重组 合i2…中,i出现了x次,则有 十x2 十 ≥0(1≤i≤n).(12.11) 反之,(1211)的任一非负整解(x1,x2,……,xn)都对应于A的唯 个r可重组合.因此,F为(1.2.11)的非负整解的个数 为求(1.2.11)的解数,令 1(1≤i≤n) 则(1.2.11)的解数与 1=1(1≤i≤n)(12,12) 的解数相同.方程 m=y1+y2+…+yny;≥1(1≤i≤n)m≥n(1.2.13 的一个解(y1,y2,……,y)与下列点阵(1.2.14)之间有一个(1 1)对应关系:将m个点 相邻两点之间的m一1个空隙中的某n-1个面上竖线,第一条 竖线之前与第n-1条竖线之后的点数分别记为y和yn第i I条竖线与第;条竖线之间的点数记为y(2≤i≤n-1),如 图 (12.14) 这样一来,方程(1.2.13)的解数与图(1.2.14)的可能的个数相同, 后者为 把mn+r代入(1215),得(1.2,I2)的解数 1 12