现在来看看定理151的应用 (I23)的第二个证明.由定理151,集[1,n]的r可重排 列的指母函数是 1十t十 r2 十 是即 由此立得U一n,证毕 定理15,2.集l1,n]的r可重排列,每个元i(1≤i≤n) 必须至少在其中出现一次,这样的排列数是 ∑(:)(-1)(n-1y (154) 0<;≤n了 证明.由定理151,符合所述条件的排列的计数母函数为 十2十十 是即 (-1)(n一i) 由此立得(1.54).证毕 因为今后还将遇到(154),这里再作一点说明,如果引进差 分算子△ △a(n)(n+1)-u(n) 和移位箅子E: Eucn=u(n+1) 则(1.54)可简写为 x,;)+(0-y-.(,)x-yE 0=△”0 3
这里,I为恒等箅子: lu(n)=u(n) 有时为了方便也可将I写为1 自然地,当r=0时,有 1y(n-j)° 0 系.当 时,△"0〓0 对于前几个n,有(当r>0时) 0-(E-1)0=1 20=(E-1)20=2-2 △30=(E-1)-3-3·2+3 母函数不仅对组合论是一个重要的工具、而且它还是其他一 些数学分支,诸如数论、概率论等的重要工具.关于母函数理论的 进一步叙述,将用下章整个一章的篇幅.至于它对组合论的应用, 请见本书以后的章节.这两节只是有关母函数的一个简单的导 引.如能细心领会,灵活应用,将是很有益处的 51.6例 本节再补充一些例子 例161.在一个凸m边形(n≥3)C的内部,如果没有三 条对角线共点,求其全部对角线在C的内部的交点的个数 所谓凸形,就是其中任二内点的联线全部落在该图形内部的 那种图形;所谓对角线指的是不相邻二顶点的联线 解.为叙述方便起见,按反时针方向把C的顶点依次记为 P{,P2,…,Pn,设X是C的对角线在C内部的一个交点,由于没 有三条对角线共点,故X恰为两条对角线,记为P,P,和P,P4,的 交点.因为PP,P1P为相交的对角线故以PP,P1,P,为 顶点的四边形是一个凸四边形,其对角线正好是PP4和PP4
不失一般,可设i<i2<i<讠反之,若任给四个顶点B,P, P,,且n<1<1<1,则四边形P,PPP为凸四边形,故 其对角线PP和P1P相交于此四边形之内,因而也在C之内,这 四点的其他联线的交点就只有P,P2PP,本身.所以,C之 对角线在C内部的交点与P1,P2,…,P中任选四点的组合的个 数相同,为 1)(-2)(n一3) 24 解毕 这个问题初看起来似乎与组合数无关,自然,也可不借助于组 合方法来解决(例如,可用数学归纳法)但要麻烦一些. 例162.今有n1个1,n2个2,…n个r(n≥1).把它们 排成一行,使得丛开头依次读出时,任何一个饣+1不触出现在第 个之前,这里,1≤饣≤r一1.求这样的排列数F(n,… 解法一.如果n11≤i≤n一1)中有一个为零,由于n,≥ l,则没有一个排列符合条件,即这样的排列数为零.今设m≥1 (1≤i≤r-1).符合条件的任一排列的首元一定是1,其余 n1-1个1可在该排列中的其他任何位置.在该排列中把所有的 1都去掉,剩下的是n2个2,n个3,…t个r的具有类似性质的 排列:任何一个+1不能出现在第一个之前(2≤k≤r 1).因为后n-1个1定位的可能个数是 十 故 十 F 由此递归关系和 用数学归纳法,立得
十 F, ( n jr 十n t;! (I6.1) 当n,…m-1中有零出现时,(1.6.1)的右节化为零,故无论 n1……,n,是否为零,(1.61)恒成立, 解法二.由定理1.3,2,n1个1,n2个2 个r的全排列 的总数是 十n)! 首位是1的排列数占总排列数的—1,故首位是1的排 列总数是 十…+m) (16.2) 71! 十 十 在首位是1的排列中去掉所有的1,余下的排列的首位是2,这样 的排列的个数占首位是1的排列的总数(1.62)的 十·十 所以,首元为1,删去所有的1后余下的排列的首元为2的排列的 个数为 n++2+ 十 依此类推最后得到:首位是1删去所有的1后首位是2,再删去 所有的2后首位是3,…,这样的排列的个数为(1.6.1).然而,这 样的排列就是问题中所述的排列.解毕 例1.6.3,把分类为12m的n个物的r-组合数记为C( r),则 C(2,1-;t) >((m 36
且有递归关系 C(2m,1”-2m;r)=C(2m-1,1"1-;r)+C(2m, 1-;r-2) (164) 解.为了便于叙述,设A1,…,An是这n个物的m个两两 不同的类,每一类由两个相同的物组成;B1,B2…,Bn-是这 个物的其余n-2m个两两不同的类每一类只由一个物组成 今从A1,…,Am中取出(≥0)个类,它们的所有2个物都参 与组合,余下m一个类与B1,…,B”个类合在一起共n 2m+(m-k)=n-m一k个类,从中选出r一2个类,每 个类的一个物参与组合.这样得到的可能的组合数,由积则,是 对所有免≥0求和,便得(1.63) 把这n个物的全部r组合分为互斥的两种:第一种r组合 含有Am的两个物,第二种r组合不同时含有Am的两个物.前 种组合数为C(2m-1,1如;r-2),因为这个组合数等于把A 除外后,分类为1-m2m-1的n-2个物的(r-2)-组合数.后 种组合数为C(2m-1,1“+m;r),因为这个组合数等于由类 1……,lm-s;B1;…,Bn-m,Am(这里,Am由Am的一个物所 成的类)所形成的n一1个物的r组合数.由和则,立得(1.64) 解毕 例1.64.试证 0<r< (165) 证明.由定理1.21,集[1,n]的n可重排列数是 在集[1,n]中任选r(0≤r≤n)个数,选法数为 一当这 r个数选定之后,它们的r可重排列数是