这就是(124) 至此,定理1.2.1已全部证毕, 值得一提的是,C与FF的表达式很相象: 十 F 二者的分母相同,而分子都是从n开始的r个数的连乘积,只不过 一个是递减的数串,而另一个却是递增的 下面讨论有关排列数与组合数的一些初等而重要的性质 定理122.P=n,nr≥2, 1216) P≌rPr+ (1.2.17) Cr= Cr+ Cr-i, F"一F-1+F,m,r≥2, 1.2.19) (1.2.20) Cin <Ci (1221) < Car 若p是素数,则p (1≤i≤p-1) 1223) 十r r≥1.(1.2,24) 证明.(1.2.16)即(1,2,5),(12.19)即(1,27). (1217)的第一个证明.当r≥2时,把A一11,n]的全 部r无重排列分为两类,一类含有d中某定元a,另一类不含此 a,对前一类中的排列,a有r个位置可供占取,去掉a后,剩下的 是集A{a的(r一1)-无重排列,故第一类排列数为rP-1.后 一类排列就是集A\{a}的r无重排列,故其个数为P-1.因此, 故(1.2.17)成立 (1217)的第二个证明.由(1,2.1)
P=(n),一n(n-1) 1),-1+(n-1)-(n-r) r(n-1)-+(n-1),n≥r≥2,(1225) 此即(1.2.17) (1.218)的第一个证明.当r≥2时,把A的r无重组合 分为两类,一类含A某定元4,一类不含此a,在第一类组合的 任一个中去掉a后,就是集A\(a}的一个(r-1)无重组合.反 之,A{4}的一个(r-1)-无重组合,添上a后就是A的一个 包含a的r无重组合,故二者之间有(1-1)对应关系.而A{a 的(r-1)-无重组合数为C,故第一类组合数也为C}.第 二类组合数就是A\{a}的r无重组合,其个数为C;1所以, CrmC#-1+C#,n≥r≥2 故(1218)成立 (1218)的第二个证明.由(12,2)和(12.25), c=()=(n=1)+(n=1 Cr-1+Cr-1,n≥r≥2, 此即(1.218) (1220)的第一个证明。由(1.22), C 此即(1,2,20), (1220)的第二个证明.若i2…i为集A的一个r无重 组合,则小\{i,n2,……,}就是A的-个(a-r)-无重组合,这样 一来,A的r无重组合与(n-r)-无重组合之间有(1-1)对应 关系,故二者的个数相同 14
(121)的证明,当1≤;≤n时,有2<2n+1,故还 2 十1.因此 1 由是 (2n) (!≤i≤n) i-1)!(2n-i+1)!计(2n-i) 这就是(1.2,21). (1222)的证明.当i<n时,有i<2n-i,故 2n、、<1,1≤i< 由是 (2n-1)! D(1≤1≤ 这就是(122)的不等式部分而最后的等式是显然的 1223)的证明.因1≤i≤p一1,故p与i互素,从而 p,1! 然而,由数()的组合意义知其为整数,即 p(p-1) 因此 ) 从而 LP (】224)的第一个证明.(1,2,24)的左节就是方程 饣=x+…十xn,打≥0(1≤i≤n)(1.2,26) 当由0取到r时的解(x1,…,xn)的个数的总和,即不等式 r≥x1十∴+xn,x≥0(1≤≤n)(12.27) 的解数,亦即方程 r〓x1+…十x十x+1,x≥0(1≤≤n+1)(1.228) ·15·
的解数.已知(1228)的解数为 ;;十1)一1 这就得到(12,24)的右节 (1224)的第二个证明.不等式(12.27)的任一解 (x1,x2,…,x),x≥)(1≤i≤n)(1.2.29) 可与[1,n+r]的n无重组合依大小顺序写出的数串 1≤y<y2<∷<yn≤n十r (123 之间有(1-1)对应.因为由变换 …+x;+;(1≤i≤n) 从(12.29)可得出唯一的(1.2.30);另一方面,借助于变换 yI (2≤i≤n), x;=y;一y;-1-1 从(1.2.30)可得出唯一的(12,29).所以,(12.27)的解数为[1, n+r]的n-无重组合数 (I224)的第三个证明.对r行数学归纳法.当r=1时 (12,24)是平凡的.今(1224)对r(r≥1)成立,则 I≤k 1≤< k-)++ 十 十1 n十 十 十1 十r 十 十r十 这就是说,(1224)对r+1也成立 至此,定理122巳全部证毕。 It
定理1.2.1中的证明方法,还可用来处理其他一些组合间题 定理123.集[1,n1的r无重组合,其中元二数码是相邻 的i,t+1(1≤t≤n-1),这样的组合数是 证明.按照自然数的顺序写强I,2,…,n,对应于一个符合 糸件的组合;i…,i,不失一般,可设i<i2<∷<l, 在上面写出的1,2,…,n中的i2…,讠这些数字之后画一条 竖线就有一个且只有一个如下的图形与这个组合相对应: 21, x1个囊 个 数 (1.2.3) 个 x,≥2 反之,对应于(12.31)形的一个图,由每条竖线前面的那个数所组 成的组合符合定理中的要求,它与(L231)相对应,这样的组合恰 有一个.因此二者之间的对应是(1-1)的.(1.2.31)形的图的 个数是方程 〓rt+∷x十x,x≥l,x2≥2,… x 0 的解数,亦即方程 ÷-|tsr.=Xm 一r十2〓y十…+y+1,y;≥1(1≤i≤r+1) 的解数.由(1.2.15),知其为 十2 (r+1)-1氵 证毕 在§96中,还将给这个定理以另一个证明 §1.3一些注记 这里对前节的内容作些必要的注记