具體數(shù)學 第5章 二項式系數(shù)(5.4-5.8節(jié))

1、第第5章章 二項式系數(shù)二項式系數(shù)（Binomial Coefficients）鞠成東鞠成東E-mail：M. P. 書名：具體數(shù)學：計算機科學基礎(chǔ)（第書名：具體數(shù)學：計算機科學基礎(chǔ)（第2版）版）原書名：原書名：Concrete Mathematics: A Foundation for Computer Science (2nd Edition)作者：作者：(美美)Ronald L. Graham, Donald E. Knuth, Oren Patashnik譯者：張明堯，張凡譯者：張明堯，張凡出版社：人民郵電出版社出版社：人民郵電出版社 ISBN：978-7-11

2、5-30810-8 第第1章章 遞歸問題遞歸問題 第第2章章 和式（選講）和式（選講） 第第3章章 整值函數(shù)整值函數(shù) 第第4章章 數(shù)論數(shù)論 第第5章章 二項式系數(shù)二項式系數(shù) 第第6章章 特殊的數(shù)特殊的數(shù) 第第7章章 生成函數(shù)（自學）生成函數(shù)（自學） 第第8章章 離散概率離散概率 第第9章章 漸進式漸進式 It introduces the mathematics that supports the analysis of algorithms, modeling probems in real world. See,Chap. 1 Recurrence 遞歸的計數(shù)遞歸的計數(shù)Chap. 2 Su

3、m 各種求和，用于算法復雜度計算等各種求和，用于算法復雜度計算等Chap. 6 Special Numbers 調(diào)和數(shù)列及有關(guān)求和問題調(diào)和數(shù)列及有關(guān)求和問題 Concrete mathematics is a blending of continuous and discrete mathematics. See,Chap. 3 Integer Functions 實數(shù)的整數(shù)部分運算實數(shù)的整數(shù)部分運算Chap. 9 Asymptotics 離散到連續(xù)的漸進離散到連續(xù)的漸進 The goal is for the student to have mathematical skills to so

4、lve complex problems, and to discover subtle patterns in data. Chap. 7 Generating Functions 用于概率計算的母函數(shù)用于概率計算的母函數(shù)Chap. 8 Discrete Probability 離散問題概率離散問題概率(最有趣最有趣) 5.4 生成函數(shù)（生成函數(shù)（Generating Functions） 5.5 *超幾何函數(shù)（超幾何函數(shù)（Hypergeometric Functions） 5.6 *超幾何變換（超幾何變換（Hypergeometric Transformations） 5.7 *部分超幾何

5、和式（部分超幾何和式（Partial Hypergeometric Sums） 5.8 *機械求和法（機械求和法（Mechanical Summation）85.4 生成函數(shù)生成函數(shù)生成函數(shù)生成函數(shù)方法是離散數(shù)學的重要方法，是連方法是離散數(shù)學的重要方法，是連接離散數(shù)學與連續(xù)數(shù)學的橋梁接離散數(shù)學與連續(xù)數(shù)學的橋梁?？梢哉f，是離散。可以說，是離散數(shù)學數(shù)學中最中最令人驚訝的、有益的、巧妙的令人驚訝的、有益的、巧妙的發(fā)明。發(fā)明。法國法國數(shù)學家數(shù)學家Laplace 于于1812年出版的年出版的概率概率分析理論分析理論最早提出。最早提出。作用作用：廣泛應用于：廣泛應用于組合計數(shù)組合計數(shù)、概率論概率論、證明證

6、明恒等式恒等式、求解遞推求解遞推關(guān)系關(guān)系、求求遞歸數(shù)列的通項遞歸數(shù)列的通項公式公式（如：經(jīng)典的（如：經(jīng)典的Fibonacci數(shù)、數(shù)、Catalan數(shù)數(shù)等）等）以及以及編程與算法設計和編程與算法設計和分析分析（往往對程序效率與速度（往往對程序效率與速度有很大改進有很大改進）等方面。）等方面。91011121314更多應用：更多應用： 利用生成函數(shù)利用生成函數(shù)證明組合證明組合恒等式恒等式 利用生成函數(shù)利用生成函數(shù)求解遞求解遞推推關(guān)系關(guān)系 常系數(shù)線性常系數(shù)線性齊次齊次遞推關(guān)系遞推關(guān)系 常系數(shù)線性常系數(shù)線性非齊次非齊次遞推關(guān)系遞推關(guān)系 利用生成函數(shù)利用生成函數(shù)進行組合計數(shù)進行組合計數(shù) 組合數(shù)的生成函數(shù)

7、問題組合數(shù)的生成函數(shù)問題 排列數(shù)的指數(shù)型生成函數(shù)問題排列數(shù)的指數(shù)型生成函數(shù)問題 整數(shù)拆分問題整數(shù)拆分問題 組合型分配問題組合型分配問題 排列型分配問題排列型分配問題 有限制位置的排列和棋盤多項式問題有限制位置的排列和棋盤多項式問題 利用生成函數(shù)利用生成函數(shù)解決概率統(tǒng)計問題解決概率統(tǒng)計問題 151617【示例示例2】：求：求n位十進制數(shù)中出現(xiàn)偶數(shù)個位十進制數(shù)中出現(xiàn)偶數(shù)個5的數(shù)的數(shù)的個數(shù)。的個數(shù)。18192021【練習題練習題】：類似的例子還有許多，例如：著名：類似的例子還有許多，例如：著名的的Hanoi塔問題、塔問題、Fibonacci數(shù)列等都是典型的利用生數(shù)列等都是典型的利用生成函數(shù)求解遞推關(guān)

8、系的例子。成函數(shù)求解遞推關(guān)系的例子。2223【示例示例4】：若有：若有1克、克、2克、克、3克、克、4克的砝碼各克的砝碼各一枚，問：能稱出哪幾種重量？有幾種可能方案？一枚，問：能稱出哪幾種重量？有幾種可能方案？24【示例示例4】：若有：若有1克、克、2克、克、3克、克、4克的砝碼各克的砝碼各一枚，問：能稱出哪幾種重量？有幾種可能方案？一枚，問：能稱出哪幾種重量？有幾種可能方案？【練習題練習題】：若有：若有1克、克、2克的砝碼各克的砝碼各兩兩枚，枚，3克、克、4克的砝碼各克的砝碼各一一枚，問：能稱出哪幾種重量？有幾種枚，問：能稱出哪幾種重量？有幾種可能方案？可能方案？2526【示例示例6】：有紅

9、球兩只，白球和黃球各一只，：有紅球兩只，白球和黃球各一只，求有多少種不同的組合方案（顏色和球數(shù)不同）。求有多少種不同的組合方案（顏色和球數(shù)不同）。27【示例示例6】：有紅球兩只，白球和黃球各一只，：有紅球兩只，白球和黃球各一只，求有多少種不同求有多少種不同的組合方案的組合方案（顏色和球數(shù)不同）（顏色和球數(shù)不同） 。28【示例示例6】：有紅球兩只，白球和黃球各一只，：有紅球兩只，白球和黃球各一只，求有多少種不同的組合求有多少種不同的組合方案方案（顏色和球數(shù)不同）（顏色和球數(shù)不同） 。29【示例示例6】：在做抽樣調(diào)查時，采訪的男士有教：在做抽樣調(diào)查時，采訪的男士有教師、醫(yī)生、律師等不同的師、醫(yī)生、

10、律師等不同的q個行業(yè)，女士也有不同的個行業(yè)，女士也有不同的p個行業(yè)，假設我們在每一行業(yè)中至多選取個行業(yè)，假設我們在每一行業(yè)中至多選取2位男士和位男士和至多選取至多選取1位女士，問有多少種不同的方法取位女士，問有多少種不同的方法取k個人的個人的樣本？樣本？30【示例示例7】：在做抽樣調(diào)查時，采訪的：在做抽樣調(diào)查時，采訪的男士男士來自來自q個不同的行業(yè)個不同的行業(yè)，女士有女士有p個不同的行業(yè)個不同的行業(yè)，假設我們在，假設我們在每一行業(yè)中至多選取每一行業(yè)中至多選取2位男士和至多選取位男士和至多選取1位女士，問位女士，問有多少種不同的方法取有多少種不同的方法取k個人的樣本？個人的樣本？ (A+B)-(

11、2A+B)x=x.)21)(1()2()()21)(1()1()21(211)(xxxBABAxxxBxAxBxAxH 設設 . 1BA20BA.)12()12()1()221(11211)(22222 xxxxxxxxxH 11)12()(nnnnnnxxhxH, 2 , 1, 12 nhnn).(10655885. 3101536. 31015292. 110718年年 T3839 解解54322235531 )1)(1)(1( ,xxxxxxxxxxG(x)hhnnn 的的生生成成函函數(shù)數(shù)為為組組合合數(shù)數(shù)為為設設S 的的1組合數(shù)組合數(shù)=3：a, b, cS 的的2組合數(shù)組合數(shù)=5：2a,

12、 2c, ab, ac, bcS 的的3組合數(shù)組合數(shù)=5：2ab, 2ac, b2c, a2c, abcS 的的4組合數(shù)組合數(shù)=3：2a2c, 2abc, ab2cS 的的5組合數(shù)組合數(shù)=1：2ab2c【示例示例9】：S =2a, b,2c , 求求S 的所有的所有n 組合數(shù)。組合數(shù)。 解解)1)(.(1.)1.)(1()(452xxxxxxg 其其生生成成函函數(shù)數(shù)為為的的非非負負整整數(shù)數(shù)解解的的個個數(shù)數(shù)。是是方方程程種種裝裝法法。設設共共有有nrrrrhhnn 4321 )1(111111552xxxxx 【示例示例1010】用用n n個水果組成一只個果籃。果個水果組成一只個果籃。果籃中可以

13、裝籃中可以裝4 4種水果：蘋果為偶數(shù)，香蕉為種水果：蘋果為偶數(shù)，香蕉為5 5 的倍數(shù)，至多有的倍數(shù)，至多有4 4個桔子，至多有一個西個桔子，至多有一個西瓜。可以有多少種裝法？瓜。可以有多少種裝法？2)1(1x 001)1(nnnnnnxnxC1 nhn所所以以 解解.)(.(1 .).)(1()(24342 xxxxxxxxxg生生成成函函數(shù)數(shù)為為種種裝裝法法。設設共共有有nhxxxxxxx 111111522 【示例示例1111】用用n n個水果組成一只個果籃。果個水果組成一只個果籃。果籃中可以裝籃中可以裝4 4種水果：蘋果為偶數(shù)，香蕉為種水果：蘋果為偶數(shù)，香蕉為奇數(shù)，至多有奇數(shù)，至多有4

14、4個桔子，至少有一個西瓜。個桔子，至少有一個西瓜?？梢杂卸嗌俜N裝法？可以有多少種裝法？22252)1()1()1(xxxx .,8,5,2, 15432 hhhh所所以以.2819148528765432xxxxxxx 解解8642888668448228082870281 )(8xxxxxCxCxCxCCxAan 數(shù)數(shù)。男男士士中中選選出出偶偶數(shù)數(shù)的的組組合合表表示示從從設設 【示例示例1212】某某單位有單位有8 8男男5 5女，從中選出一女，從中選出一個小組。要求男士為偶數(shù)，女士至少個小組。要求男士為偶數(shù)，女士至少2 2人，人，有多少種組合方式？有多少種組合方式？5432551010 5

15、1)1()(25xxxxxxxBbn 人人的的組組合合數(shù)數(shù)。女女士士中中至至少少選選出出表表示示從從設設 解解 請注意：每個人是有區(qū)別的！請注意：每個人是有區(qū)別的！1312111098765432538150 350630728840 2812851010 )()()(nxxxxxxxxxxxxxBxAxCcn 組組合合數(shù)數(shù)。生生成成函函數(shù)數(shù)為為表表示示滿滿足足要要求求的的男男女女設設2854222854450825284 CCCCx組組合合數(shù)數(shù)恰恰為為女女，女女，男男組組合合為為：。的的系系數(shù)數(shù)人人小小組組的的數(shù)數(shù)目目為為332815382812851010 為為滿滿足足要要求求的的所所有有

16、組組合合數(shù)數(shù) 【示例示例1313】 解解kxxxxg.)()(53 的的生生成成函函數(shù)數(shù)。數(shù)數(shù)的的非非負負奇奇數(shù)數(shù)整整數(shù)數(shù)解解的的個個求求方方程程nkhnrrr . 21kkkxxxx)1(122 021021rkrrrkrrrrkkxCxCx)(2/ )( ,22/ )(2/ )2(knChknrkrnknknn 得得令令K是偶是偶數(shù)，數(shù)，N也是也是偶數(shù)偶數(shù)K是奇是奇數(shù)，數(shù)，N也是也是奇數(shù)奇數(shù)【 示例示例1414】 解解.)1(.)1( .)1(.)1()(105428463 xxxxxxxxxg的的生生成成函函數(shù)數(shù)。求求的的非非負負整整數(shù)數(shù)解解的的個個數(shù)數(shù)，是是方方程程nnhnrrrrh

17、432152431,111111115243 xxxxx 解解)1)(1( .)(1.)1.)(1()(50755025105xxxxxxxxg 其其生生成成函函數(shù)數(shù)為為的的非非負負整整數(shù)數(shù)解解的的個個數(shù)數(shù)。是是方方程程種種方方法法。設設共共有有10, 30 5025105 5454321 rrnrrrrrhhnn)1(111111115025100105xxxxxx 【示例示例1616】我們我們有有1 1，5 5，1010，2525，5050等硬等硬幣。幣。5050分硬幣只有分硬幣只有1 1個，個，2525分硬幣有只有分硬幣有只有3 3個，其它硬幣有很多。用這些硬幣恰好組個，其它硬幣有很多。用這些硬幣恰好組成成n n分錢，共有多少種方法？分錢，共有多少種方法？ 【示例示例1717】 解解mmmxxxxxxg)1(.)()(32 的