第十二章基本的组合计数公式分析

1、闽南师范大学计算机学院闽南师范大学计算机学院第十二章第十二章 基本的组合计数公式基本的组合计数公式第十二章第十二章 基本的组合计数公式基本的组合计数公式加法法则与乘法法则加法法则与乘法法则排列与组合排列与组合二项式定理与组合恒等式二项式定理与组合恒等式多项式定理多项式定理知知 识识 点：加法法则与乘法法则、排列和组合的定义、排列和组合的生点：加法法则与乘法法则、排列和组合的定义、排列和组合的生 成算法、基本恒等式成算法、基本恒等式、二项式定理、多项式定理二项式定理、多项式定理教学要求：深刻理解和掌握排列、组合的基本概念及基本应用。教学要求：深刻理解和掌握排列、组合的基本概念及基本应用。教学重点

2、：排列和组合的定义的概念及基本应用。教学重点：排列和组合的定义的概念及基本应用。学时学时: 412.1 加法法则与乘法法则加法法则与乘法法则加法法则加法法则: 如果事件如果事件 A 有有 m 种产生方式种产生方式 , 事件事件 B 有有n种产生方式种产生方式,当当A与与B产生的方式不重叠时产生的方式不重叠时, ”事件事件A或或B” 有有 m + n 种产生方式种产生方式n加法原理中事件的产生方式应是互相排斥的加法原理中事件的产生方式应是互相排斥的n加法法则加法法则 (集合形式集合形式): 若若 S=AB,AB=,则则 |S|=|A|+|B|n加法法则的推广加法法则的推广: 设设A1,A2,An

3、是是n个事件个事件,它们的产生方式分别它们的产生方式分别有有p1,p2,pn种种,当其中任何两个事件产生的方式都不重叠时当其中任何两个事件产生的方式都不重叠时,事事件件” A1或或A2或或或或An”有有p1+p2+pn种产生方式种产生方式汽车汽车火车火车甲地甲地乙地乙地飞机飞机轮船轮船陆路陆路水路水路甲地甲地乙地乙地12.1 加法法则与乘法法则加法法则与乘法法则乘法法则乘法法则: 事件事件 A 有有 m 种产生方式种产生方式, 事件事件B 有有n 种产生方式种产生方式,当当A与与B产生产生的方式彼此独立时的方式彼此独立时, “事件事件 A 与与 B ” 有有 mn 种产生方式种产生方式 n乘法

4、法则中各事件的出现应是相互独立的乘法法则中各事件的出现应是相互独立的, 也就是说也就是说B的出现不受的出现不受A的影响的影响, 同样同样A的出现也不受的出现也不受B的影响的影响n乘法法则乘法法则 (集合形式集合形式) : 若若 S=AB, 则则 |S|=|A|B|n乘法法则的推广乘法法则的推广: 设设A1,A2,An是是n个事件个事件,它们的产生方式分别它们的产生方式分别有有p1,p2,pn种种,当其中任何两个事件产生的方式都彼此独立时当其中任何两个事件产生的方式都彼此独立时,事件事件” A1与与A2与与与与An有有p1p2pn种产生方式种产生方式1甲地甲地乙地乙地32abcd丙地丙地1甲地甲

5、地乙地乙地32abcd丙地丙地丁地丁地戊地戊地stxyzA上的函数上的函数 f 可以用二元关系表示成可以用二元关系表示成f=,每个每个yi都有都有n种不同的选择种不同的选择,根据乘法法则根据乘法法则,有有nn个不同的函数个不同的函数当当 f 是双射时是双射时,yi y2,yn之间都互不相同之间都互不相同构造双射的方法构造双射的方法:第一步确定第一步确定y1,y1共有共有n种可能的取值种可能的取值第二步确定第二步确定y2,y1确定后确定后y2只有只有n-1种可能取值种可能取值第第n步确定步确定yn , yn只有一种取值只有一种取值根据乘法法则根据乘法法则 有有n(n-1)(n-2)1个不同的构造

6、方法个不同的构造方法12.1 加法法则与乘法法则加法法则与乘法法则例例12.1 设设A为为n元集元集,问问nA上的自反关系有多少个上的自反关系有多少个nA上的反自反关系有多少个上的反自反关系有多少个nA上的对称关系有多少个上的对称关系有多少个nA上的反对称关系有多少个上的反对称关系有多少个nA上的函数有多少个上的函数有多少个nA上的双射函数有多少个上的双射函数有多少个11*1111RMn元集元集A上的二元关系上的二元关系R的关系矩阵的关系矩阵R是是A上的自反关系当且仅当上的自反关系当且仅当在在MR中中 对主角线上的元素全都为对主角线上的元素全都为1,非主对角线上的元素可以是非主对角线上的元素可

7、以是0或或1。非主对角线的位置有非主对角线的位置有n2-n个个,根据乘法法根据乘法法则自反关系的个数是则自反关系的个数是 2 n2-n00*0000RMR是是A上的反自反关系当且仅当上的反自反关系当且仅当在在MR中中 对主角线上的元素全都为对主角线上的元素全都为0,非主对角线上的元素可以是非主对角线上的元素可以是0或或1。非主对角线的位置有非主对角线的位置有n2-n个个,根据乘法法根据乘法法则自反关系的个数是则自反关系的个数是 2 n2-n*0*10*1*RMR是是A上的对称关系当且仅当上的对称关系当且仅当MR是对称矩阵。是对称矩阵。主对角线上的元素可以是主对角线上的元素可以是0或或1,主对角

8、线的位置有主对角线的位置有n个个,在每对在每对非主对角线的非主对角线的对称位置上对称位置上,两个元素取值同时是两个元素取值同时是0或同时是或同时是1,这样的对称位置共有这样的对称位置共有(n2-n)/2对。对。根据乘法法则对称关系的个数是根据乘法法则对称关系的个数是 2 (n2+n)/2*$*$*RMR是是A上的反对称关系当且仅当在上的反对称关系当且仅当在MR非主对角线的位置非主对角线的位置上上,关于主对角线对称的两个位置取值不能全为关于主对角线对称的两个位置取值不能全为1。主对角线上的元素可以是主对角线上的元素可以是0或或1,主对角线的位置有主对角线的位置有n个个,在每对在每对非主对角线的非

9、主对角线的对称位置上对称位置上,两个元素取值有三种两个元素取值有三种不同的情况不同的情况,这样的对称位置共有这样的对称位置共有(n2-n)/2对。对。根据乘法法则对称关系的个数是根据乘法法则对称关系的个数是 2n3 (n2-n)/2这两个元素的取值有三这两个元素的取值有三种不同的情况种不同的情况:(0,0), (0,1), (1,0)上、下三角区域上、下三角区域分别有分别有1+2+(n-1)个元素个元素例例12.2 Ipv4协议网址计数协议网址计数: 32 位地址位地址(w.x.y.z):网络标识网络标识+主机标识主机标识 A类类:最大网络；最大网络；B类类:中等网络；中等网络；C:最小网络；

10、最小网络；D类类:多路广播；多路广播；E类类:备用备用 限制条件：限制条件：1111111 在在A 类中的网络标识部分无效类中的网络标识部分无效 主机标识部分不允许全主机标识部分不允许全0或全或全1 A 类类: netid 271, hostid 2242 , 地址数地址数: 127 * 16777214 B 类类: netid 214, hostid 2162 , 地址数地址数: 16384 * 65534 C 类类: netid 221, hostid 282 , 地址数地址数: 2097152 * 254 Ipv4协议网址总数协议网址总数= 2130706178+1073709056+5

11、32676608 = 373709184212.1 加法法则与乘法法则加法法则与乘法法则12.1 加法法则与乘法法则加法法则与乘法法则加法法则与乘法法则的其它加法法则与乘法法则的其它例子例子n从城市从城市A到城市到城市B有两条陆路有两条陆路, 两条水路两条水路, 一条航线一条航线, 则由推广的加法原理知则由推广的加法原理知, 从从A到到B有有2 + 2 + 1 = 5种走法。种走法。n书架上有三本不同的英语书书架上有三本不同的英语书, 两本不同的日语书两本不同的日语书, 两本不同的俄语两本不同的俄语书书, 一个学生要选英语、日语、俄语书各一本一个学生要选英语、日语、俄语书各一本, 由推广的乘法

12、原理知共有由推广的乘法原理知共有3 2 2 = 12种选法。种选法。 n求比求比10000小的正整数中含有数字小的正整数中含有数字1的数的个数。的数的个数。 12.2 排列与组合排列与组合设设n元集合元集合S,从从S 中选取中选取r 个元素个元素,根据是否有序根据是否有序,是否允许是否允许重复可以将该问题分为四个子类型重复可以将该问题分为四个子类型例例: S=1,2,3,4,5,从从S中选取中选取3个元素个元素n无重复排列无重复排列: 1 2 3 , 2 1 3 , 5 2 4 看作不同的选取结果看作不同的选取结果n可重复排列可重复排列: 1 1 2 , 1 2 1 , 2 1 3 看作不同的

13、选取结果看作不同的选取结果n无重复组合无重复组合: 1 2 3 , 2 4 5 是不同的选取结果是不同的选取结果 但但 1 2 3 , 2 1 3看作相同的选取结果看作相同的选取结果n可重复组合可重复组合: 1 1 3 , 2 4 5 是不同的选取结果是不同的选取结果 但但 1 1 3 , 1 3 1看作相同的选取结果看作相同的选取结果不重复不重复重复重复有序有序集合排列集合排列P(n,r)多重集排列多重集排列无序无序集合组合集合组合C(n,r)多重集组合多重集组合12.2 排列与组合排列与组合定义定义12.1 设设n元集合元集合Sn从从S 中有序选取的中有序选取的r 个元素称作个元素称作S的

14、一个的一个r排列排列,S的不同的不同r排列总数排列总数记作记作P(n,r), r=n时的排列称为时的排列称为S的全排列的全排列n从从S 中无序选取的中无序选取的r 个元素称作个元素称作S的一个的一个r组合组合,S的不同的不同r组合总数组合总数 记作记作C(n,r),有时也记作有时也记作定理定理12.1 设设n,r为自然数为自然数,规定规定0!=1,则则rnrnrnnnrnnrnP,0,) 1).(1()!(!),(rnrnrnrnrrnPrnC,0,)!( !),(),(rn12.2 排列与组合排列与组合例例 设设S=1,2,3,4n从从S的所有不同的所有不同3排列排列(从从S中有序选取中有序

15、选取3个元素得到的排列个元素得到的排列) 1 2 3 , 1 3 2 , 2 1 3 , 2 3 1 , 3 1 2 , 3 2 1 1 2 4 , 1 4 2 , 2 1 4 , 2 4 1 , 4 1 2 , 4 2 1 1 3 4 , 1 4 3 , 3 1 4 , 3 4 1 , 4 1 3 , 4 3 1 2 3 4 , 2 4 3 , 3 2 4 , 3 4 2 , 4 2 3 , 4 3 2 P(4,3)=24n从从S的所有不同的所有不同3组合组合(从从S中无序选取中无序选取3个元素得到的组合个元素得到的组合) 1 2 3 , 1 2 4 , 1 3 4 , 2 3 4 C(4,

16、3)=412.2 排列与组合排列与组合推论推论1 元素依次排成一个圆圈的排列称为环排列元素依次排成一个圆圈的排列称为环排列.S的的r环环排列数等于排列数等于 P(n,r)/rn证证: 设线排列的设线排列的r个元素依次为个元素依次为 a1,a2,ar , 将将a1接在接在ar的后面的后面就组成一个环排列就组成一个环排列.只要相邻关系不变只要相邻关系不变,这这r个元素中的任何一个作为个元素中的任何一个作为线排列的首元素线排列的首元素,首尾相连所构成的环排列都是相同首尾相连所构成的环排列都是相同.因此环排列数因此环排列数是线排列数的是线排列数的1/r .例例 一家人请客入席一家人请客入席, 共共8个

17、人个人, 围圆桌而坐围圆桌而坐, 若座位不编号有多少种坐法若座位不编号有多少种坐法? 座位编号呢座位编号呢? 解解 座位不编号为环状排列问题座位不编号为环状排列问题, 有有7! = 5040种坐法种坐法. 座位编号实际上为非环状排列问题座位编号实际上为非环状排列问题 , 故有故有8! = 40320种坐法种坐法 . aedcbcabde12.2 排列与组合排列与组合推论推论2 设设S=a,b,c,d,e,n=5,r=3, C(5,3)=10n考虑含有考虑含有a的组合的生成方法的组合的生成方法: 从余下的从余下的4个元素中取个元素中取2个再加上个再加上a, 含有含有a的组合共有的组合共有C(4,

18、2)=6种种,同理含有同理含有b,c,d,e的组合都各有的组合都各有6种种,这样共得到这样共得到 5*C(4,2)种组合种组合. 但每种组合都被重复计算了但每种组合都被重复计算了3次次. 例如例如(a,b,c),分别在计算含有分别在计算含有a,b,c的组合中各被计算了一次的组合中各被计算了一次 所以所以 C(5,3)=5*C(4,2)/3=5*6/3=10n选取一个选取一个3组合时组合时,没有被选取的元素同时也组成了一个没有被选取的元素同时也组成了一个2组合组合 例如例如 选取选取 (a,b,c),同时也得到一个同时也得到一个2组合组合(d,e),即即C(5,3)=C(5,2)n所有的所有的3

19、组合分成一类含有组合分成一类含有a,一类不含有一类不含有a . 含有含有a的组合如上述方的组合如上述方法法 共有共有C(4,2)种种,不含有不含有a的组合是从余下的的组合是从余下的4个元素中选取出个元素中选取出,共共有有C(4,3)种种,根据加法法则根据加法法则 C(5,3)=C(4,2)+C(4,3)1,1(),1(),(),(),()1,1(),(rnCrnCrnCrnnCrnCrnCrnrnC12.2 排列与组合排列与组合多重集多重集: S= n: S= n1 1aa1 1 , , n n2 2aa2 2 , , , , n nk kaak k n其中其中 a a1 1 , a, a2

20、2 , , a, , ak k 是是 k k 个不同的元素个不同的元素nN Ni i 表示表示 a ai i 在在S S中出现的次数中出现的次数, ,称作称作a ai i的重复度的重复度nn ni i=时表示有足够多的时表示有足够多的a ai i以备选取以备选取, ,即即a ai i的选取次数不受限制的选取次数不受限制定义定义12.2 12.2 设设S=S= n n1 1aa1 1 , , n n2 2aa2 2 , , , , n nk kaak k 为多重集为多重集, , n=n n=n1 1+n+n2 2+n+nk k 表示表示S S中元素的总数中元素的总数 (1)(1)从从S S中有序

21、选取的中有序选取的r r个元素称为多重集个元素称为多重集S S的一个的一个 r r排列排列. . 当当 r=n r=n 时的排列称为时的排列称为 S S 的全排列的全排列 (2)(2)从从S S中无序选取的中无序选取的r r个元素称为多重集个元素称为多重集S S的一个的一个r r组合组合例例 由由a,b,c,da,b,c,d四个字母组成的长度为四个字母组成的长度为1010的字符串是多重集的的字符串是多重集的1010排列排列 英文单词英文单词 mathematics mathematics 中出现的所有字母中出现的所有字母 a a c e h i m m s t t a a c e h i m

22、m s t t 是多重集的一个是多重集的一个1111组合组合12.2 排列与组合排列与组合定理定理12.2 12.2 设设S= nS= n1 1aa1 1 , , n n2 2aa2 2 , , , , n nk kaak k 为多重集为多重集 (1)S(1)S的全排列数是的全排列数是 (2)(2)若若r r n ni i , i=1,2,k, i=1,2,k,那么那么S S的的r r排列数是排列数是 k k r rS S的全排列数也记作的全排列数也记作例例 由由1 1个个a,2a,2个个b,3b,3个个c,4c,4个个d d组成的长度为组成的长度为1010的字符串共有的字符串共有 10! /

23、(1!2!3!4!) 10! /(1!2!3!4!) 种种!21knnnnknnnn2112.2 排列与组合排列与组合定理定理12.2 当当 r ni , i=1,2,k 时时,多重集多重集S的的r组合是组合是 C(k+r-1,r) 证明证明 设设 S= n11 , n22 , , nkk 现有现有k个盒子如图所示，编号分别为个盒子如图所示，编号分别为1,2,k 将将 r 个完全相同的球投入到盒子中个完全相同的球投入到盒子中 第第 i 只盒子中装有的球数只盒子中装有的球数 ti 表示表示 S中的元素中的元素 i 被取出被取出 ti 次次, 由于由于 t1+t2+ t k =r 则每次投球的结果

24、都可以得到一个从则每次投球的结果都可以得到一个从S中取中取r个元素的可重复组合。个元素的可重复组合。 将将r个球和个球和 k-1个盒子的隔板位置选好，就可以得到各个盒子的球数个盒子的隔板位置选好，就可以得到各个盒子的球数 而这样的位置选择恰好有而这样的位置选择恰好有 C(k+r-1,r) 种种 123ik12.2 排列与组合排列与组合例例 设设 S=1,2,3,4,从从S中取中取3个元素的可重复组合个元素的可重复组合1234表示组合表示组合 (234)1234表示组合表示组合 (122)1234表示组合表示组合 (222)1234表示组合表示组合 (144)球与隔板共占有球与隔板共占有(4-1

25、)+3个位置个位置, 球和隔板的位置选择代表可重复组合球和隔板的位置选择代表可重复组合即从即从4+3-1个位置中选择个位置中选择3个位置放球，其余位置放隔板就可以得到一个个位置放球，其余位置放隔板就可以得到一个可重复组合可重复组合,所以总共有所以总共有 C(4+3-1,3)=C(6,3)=6!/(3!(6-3)!)=20 种可重复组合种可重复组合12.2 排列与组合排列与组合例例12.3 排列排列26 个字母个字母,使得使得a与与b之间恰有之间恰有7 个字母个字母,求方法数求方法数. 解解 固定固定a和和b, 中间插入中间插入7 个字母个字母,有有 2 P(24,7) 种方法种方法, 将它看作

26、大字母与其余将它看作大字母与其余17 个全排列有个全排列有 18！种，共！种，共 N = 2 P(24,7) 18! 或者或者 从第从第1个位置至第个位置至第18个位置中选取一个位置个位置中选取一个位置,设为第设为第k个位个位 从从a,b中选取一个放在第中选取一个放在第k个位置上个位置上,另一个放在第另一个放在第k+8个位置上个位置上 将其余的将其余的24个字母排在剩余的个字母排在剩余的24个位置上个位置上 这样得到的这样得到的26个字母全排列数为个字母全排列数为 C(18,1)C(2,1)24!=2P(24,7)18!第第1个位置个位置第第26个位置个位置第第18个位置个位置第第k个位置个位

27、置第第k+8个位置个位置12.2 排列与组合排列与组合例例12.4 把把 2n 个人分成个人分成n 组组,每组每组2 人人,有多少分法？有多少分法？ 解解: 相当于把相当于把 2n个不同的球放到个不同的球放到 n 个相同的盒子个相同的盒子,每个盒子每个盒子2 个个, 放法为放法为 (将将2n个球排成一列个球排成一列,按顺序依次各取按顺序依次各取2个球放入每个盒子中个球放入每个盒子中,再消除次序再消除次序)例例12.5 下而给出一段简单的程序下而给出一段简单的程序,问它的输出问它的输出x是什么是什么? Algorithm 输出结果为输出结果为 C(n+k-1,k)1. x02. for i11

28、to n3. for i21 to i1 K+1. for ik to ik-1K+2. xx+1K+3. return x!2)!2(!) !2()!2(nnnnNnn例例: x=0; for(i=1;i=5;i+) for(j=1;j=i;j+) for(k=1;kn-k+1时无解时无解 当当 kn-k+1时时,设设有有 n-k+1 个盒子如图所示个盒子如图所示 将将 k 个完全相同的球投入到盒子中个完全相同的球投入到盒子中,每个盒子最多投入一个球每个盒子最多投入一个球 则不同投球的结果可以得到从则不同投球的结果可以得到从S中取中取k个不相邻数的不同方法。个不相邻数的不同方法。 具体做法是

29、从左至右将具体做法是从左至右将k个球和个球和(n-k)个盒子中间隔板依次编号为个盒子中间隔板依次编号为 1,2,3,n 则则k个球所对应的编号就是选择个球所对应的编号就是选择k个不相邻数的一种方法个不相邻数的一种方法 而这样的投球结果恰好有而这样的投球结果恰好有 C(n-k+1,k) 种种 123n45n-1n-2n-k+1个盒子个盒子12.2 排列与组合排列与组合例例 设设 S=1,2,3,4,5,6,7,8,9,从从S中取中取3个不相邻的数个不相邻的数表示选择的表示选择的3个数是个数是 1,3,7表示选择的表示选择的3个数是个数是 2,5,7表示选择的表示选择的3个数是个数是 3,5,9表

30、示选择的表示选择的3个数是个数是 2,5,8表示选择的表示选择的3个数是个数是 2,4,6从从S中选择中选择3个不相邻的数的方法总数为个不相邻的数的方法总数为 C(9-3+1,3)=3512.3 二项式定理与组合恒等式二项式定理与组合恒等式定理定理12.4 (二项式定理二项式定理),设设n是正整数是正整数,对一切对一切x和和y推论推论 设设n是正整数是正整数,则则nkknknyxknyx0)(nkknxknx0)1 (例例 (x+y)5=(x+y)(x+y)(x+y)(x+y)(x+y)=+C(5,3)x3y2+ 构成构成x3y2的项必须是从的项必须是从5个个(x+y)中选中选3个提供个提供x

31、,其他其他5-3个提供个提供y 因此因此,x3y2的系数是的系数是C(5,3)12.3 二项式定理与组合恒等式二项式定理与组合恒等式主要恒等式主要恒等式knNknknnkn,. 1knZknknknkn,11. 2knZknknknkn,111. 3Nnknnnk2. 40Nnknnkk0) 1(. 50Nknknklnl,11. 60Nkrnkrnkrknknkrrn,. 7),min(,. 80nmrNrnmrnmkrnkmrkNnmmnmknkmnk,. 9012.3 二项式定理与组合恒等式二项式定理与组合恒等式例例12.7 证明以下组合恒等式证明以下组合恒等式 证证 (1) 由二项式定

32、理有由二项式定理有 两边求导数得两边求导数得 令令x=1即可得原等式即可得原等式 (2) Znnknknnk,2) 1 (10nkknxknx0)1 (nkknkxknxn011)1 (Znnnknknnk,2) 1()2(202nknknknkknknknknknknkknk00020211 1) 1(1111 nknknknkknnknknknnknkn110001111111) 1(2122) 1(22) 1(nnnnnnnn12.3 二项式定理与组合恒等式二项式定理与组合恒等式非降路径问题非降路径问题: 设设m,n是正整数是正整数,从从(0,0)点到点到(m,n)点的非降路径是点的非降

33、路径是 一条折线一条折线,这条折线由这条折线由m+n次移动构成次移动构成,每次允许向上每次允许向上 或者向右移动一步或者向右移动一步. 问不同的非降路径有多少条问不同的非降路径有多少条? 解解 不同的路径取决于不同的路径取决于m+n步的选择步的选择 其中包含其中包含m步向右步向右,n步向上。步向上。 这种路径的条数等于从这种路径的条数等于从m+n个个 位置中选位置中选m个位置的方法数。个位置的方法数。 即即 C(m+n,m) 或或 C(m+n,n)例例 某城市某城市7条南北走向的街道条南北走向的街道, 6条东西走向的街道。问从西南角到东北角的最短路有几条条东西走向的街道。问从西南角到东北角的最

34、短路有几条? 解解 记东西走向的路段为记东西走向的路段为x,南北走向的路段为南北走向的路段为y, 则每条最短路由则每条最短路由6个个x和和5个个y组成组成. x,y的不同排列构成不同的最短路的不同排列构成不同的最短路 所以共有所以共有 11!/(5!6!)=C(11,5)条最短路条最短路(0,0)(m,n)12.3 二项式定理与组合恒等式二项式定理与组合恒等式给定非负整数给定非负整数a,b,m,n,其中其中am,bn. 从从(a,b)点到点到(m,n)点的非降路径数等于点的非降路径数等于 从从(0,0)点到点到(m-a,n-b)点的非降路径数点的非降路径数, 即即 C(m-a+n-b,m-a)

35、设设a,b,c,d,m,n是非负整数是非负整数,其中其中acm,bdn. 从从(a,b)点经过点经过(c,d)点到点到(m,n)点的非降路径数点的非降路径数 = 从从(a,b)点到点到(c,d)点的非降路径数点的非降路径数 从从(c,d)点到点到(m,n)点的非降路径数点的非降路径数(a,b)(m,n)(0,0)(c,d)12.3 二项式定理与组合恒等式二项式定理与组合恒等式例例12.8 求集合求集合1,2,n上的单调递增函数的个数上的单调递增函数的个数 解解 将自变量看作横坐标将自变量看作横坐标,对应的函数值看作纵坐标对应的函数值看作纵坐标,得到得到n个点个点, 再增加两个点再增加两个点(1

36、,1)和和(n+1,n),共有共有n+2个点个点(如果如果f(1)1) (1,1) , (1,f(1) , (2,f(2) , (n,f(n) , (n+1,n) 如果如果 f(1)1,那么从那么从 (1,1) 直接向上连接到直接向上连接到 (1,f(1) 每个点都按先向右每个点都按先向右,后向上的规则连接到下一个点后向上的规则连接到下一个点, 这样得到一条从这样得到一条从 (1,1) 到到 (n+1,n) 的非降路径的非降路径. 这种非降路径和集合这种非降路径和集合 1,2,n上单调递增函数是一一对应的上单调递增函数是一一对应的 根据公式根据公式,集合集合1,2,n上单调递增函数个数是上单调

37、递增函数个数是 C(2n-1,n)例例 设设A=1,2,3,4 , 如右图所示如右图所示 黑线表示的非降路径对应黑线表示的非降路径对应A上的递增函数上的递增函数 f(1)=1,f(2)=1,f(3)=2,f(4)=2 红线表示的非降路径对应红线表示的非降路径对应A上的递增函数上的递增函数 f(1)=2,f(2)=3,f(3)=3,f(4)=4(1,1)(5,4)(0,0)12.3 二项式定理与组合恒等式二项式定理与组合恒等式例例12.9 栈栈(后进先出栈后进先出栈)的输出计数问题的输出计数问题 解解 将进栈、出栈分别记作将进栈、出栈分别记作x,y,一个输出对应了一个输出对应了n个个x,n个个y的排列的排列, 且排列的任何前缀中的且排列的任何前缀中的x个数不少于个数不少于y的个数的个数.将排列中的将排列中的x看作向右看作向右 走一步走一步,y看作向上走一步看作向上走一步,这样一个排列就对应了一条从这样一个排列就对应了一条从(0,0)点到点到 (n,n)点的非降路径点的非降路径,且不穿过对角线。且不穿过对角线。 如右图所示如右图所示,任何一条从任何一条从(0,0)到到(n,n)穿过对角线的路径一定要穿过