《組合數(shù)學(xué)》PPT課件.ppt

《《組合數(shù)學(xué)》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《組合數(shù)學(xué)》PPT課件.ppt（360頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、組合數(shù)學(xué)課件 課程簡(jiǎn)介 相關(guān)課程 使用教材 數(shù)學(xué)分析 高等代數(shù) 離散數(shù)學(xué) 書名：組合數(shù)學(xué)（第三版） 作者：孫淑玲 出版社：中國(guó)科學(xué)技術(shù)大學(xué)出版社 本課程針對(duì)計(jì)算機(jī)科學(xué)中的一個(gè)重要學(xué)科 組合數(shù)學(xué) ， 組合數(shù)學(xué)是數(shù)學(xué)的一個(gè)分支 ， 它研究事物在結(jié)定模式下的配 置 ， 研究這種配置的存在性 ， 所有可能配置的計(jì)數(shù)和分類以 及配置的各種性質(zhì) 。 組合數(shù)學(xué)在計(jì)算機(jī)科學(xué)中有著極其廣泛 的應(yīng)用 。 組合學(xué)問(wèn)題求解方法層出不窮、干變?nèi)f化，應(yīng)以理解為 基礎(chǔ)，善于總結(jié)各種技巧，掌握科學(xué)的組織和推理方法。 目錄（ 1） 引言 第 1章 排列與組合 1.1 加法法則和乘法法則 1.2 排列 1.3 組合 1.4 二項(xiàng)

2、式定理 1.5 組合恒等式及其含義 1.6 模型轉(zhuǎn)換 本章小結(jié) 習(xí)題 第 2章 鴿籠原理 2.1 鴿籠原理 2.2 鴿籠原理的推廣 2.3 Ramsey定理 本章小結(jié) 習(xí)題 第 3章 容斥原理 3.1 容斥原理 3.2 重集 r-組合 3.3 錯(cuò)排問(wèn)題 3.4 有限制排列 3.5* 一般有限制排列 3.6* 廣義容斥原理 本章小結(jié) 習(xí)題 第 4章 母函數(shù) 4.1 母函數(shù)的基本概念 4.2 母函數(shù)的基本運(yùn)算 4.3 在排列組合中的應(yīng)用 4.4 整數(shù)的拆分 4.5 Ferrers圖 目 錄 目錄（ 2） 4.6* 在組合恒等式中的應(yīng)用 本章小結(jié) 習(xí)題 第 5章 遞推關(guān)系 5.1 遞推關(guān)系的建立 5

3、.2 常系數(shù)線性齊次遞推關(guān)系 5.3 常系數(shù)線性非齊次遞推關(guān)系 5.4 迭代法與歸納法 5.5 母函數(shù)在遞推關(guān)系中的應(yīng)用 5.6* 典型的遞推關(guān)系 本章小結(jié) 習(xí)題 第 6章 Plya定理 6.1 群的概念 6.2 置換群 6.3 循環(huán)、奇循環(huán)與偶循環(huán) 6.4 Burnside引理 6.5 Plya定理 6.6 Plya定理的應(yīng)用 6.7 母函數(shù)形式的 Plya定理 6.8* 圖的計(jì)數(shù) 6.9* Plya定理的若干推廣 本章小結(jié) 習(xí)題 * 課程總結(jié) 注：加 *的章節(jié)一般性了解 引 言 發(fā)展歷史 涵蓋內(nèi)容 學(xué)習(xí)目的 學(xué)習(xí)方法 存在性問(wèn)題 計(jì)數(shù)和枚舉 優(yōu)化 問(wèn)題 構(gòu)造性問(wèn)題 科學(xué)的組織 科學(xué)的推理

4、古老 年輕 練習(xí) 思考總結(jié) 筆記 組合數(shù)學(xué)研究的中心問(wèn)題是按照一定的規(guī) 則來(lái)安排有限多個(gè)對(duì)象 如果人們想把有限多個(gè)對(duì)象按照它們所應(yīng)滿足的條 件來(lái)進(jìn)行安排，當(dāng)符合要求的安排并非顯然存在或顯 然不存在時(shí)，首要的問(wèn)題就是要證明或者否定它的存 在。這就是 存在性 問(wèn)題。如果所要求的安排存在，則 可能有多種不同的安排，這又經(jīng)常給人們提出這樣的 問(wèn)題：有多少種可能的安排方案？如何對(duì)安排的方案 進(jìn)行分類？這就是 計(jì)數(shù)問(wèn)題 。如果一個(gè)組合問(wèn)題有解， 則往往需要給出求其某一特定解的算法，這就是所謂 的 構(gòu)造性 問(wèn)題。如果算法很多，就需要在一定的條件 下找出一個(gè)或者幾個(gè)最優(yōu)或近乎最優(yōu)的安排方案，這 就是 優(yōu)化 問(wèn)

5、題。 第 1章 排列與組合 本章重點(diǎn)介紹以下的基本計(jì)數(shù)方法： 加法法則和乘法法則 排列 組合 二項(xiàng)式定理的應(yīng)用 組合恒等式 相互獨(dú)立 的事件 A、 B 分別有 k 和 l 種方法產(chǎn)生 ， 則產(chǎn)生 A 或 B 的方 法數(shù)為 k+l 種 。 1.1 加法法則 1.1 加法法則和乘法法則 1.1.1 加法法則 加法法則 集合論定義 若 |A|=k， |B|=l ，且 A B= ， 則 |A B| = k+l 。 設(shè) S是有限集合，若 ，且 時(shí)， ，則有 。 ij ijSS 1 , m ii i S S S S 11 m m ii ii S S S 1.1 加法法則例 1 1.1 加法法則和乘法法則

6、1.1.1 加法法則 例 題 例 1、 有一所學(xué)校給一名物理競(jìng)賽優(yōu)勝 者發(fā)獎(jiǎng) ， 獎(jiǎng)品有三類 ， 第一類是三種 不同版本的法漢詞典；第二類是四種 不同類型的物理參考書；第三類是二 種不同的獎(jiǎng)杯 。 這位優(yōu)勝者只能挑選 一樣獎(jiǎng)品 。 那么 ， 這位優(yōu)勝者挑選獎(jiǎng) 品的方法有多少種 ？ 解： 設(shè) S是所有這些獎(jiǎng)品的集合 ， Si是第 i類獎(jiǎng)品的集合 (i=1,2,3)， 顯然 ， SiSj= (i j) ， 根據(jù)加法 法則 有 ii S S S S S 3 1 2 3 1 | | | | | | | | 3 4 2 9 1.1 加法法則例 2、 3 1.1 加法法則和乘法法則 1.1.1 加法法則

7、例 題 例 2、 大于 0小于 10的奇偶數(shù) 有多少個(gè) ？ 例 3、 小于 20可被 2或 3整除的自然 數(shù)有多少個(gè) ？ 解： 設(shè) S是符合條件數(shù)的集合 ， S1、 S2分別是符合條件的 奇數(shù) 、 偶數(shù)集合 ， 顯然 ， S1S2= ， 根據(jù)加法 法則 有 S S S12| | | | | | 5 4 9 若 |A|=k， |B|=l ， AB=(a,b)|a A， b B，則 |AB| = kl 。 1.1 乘法法則 1.1 加法法則和乘法法則 1.1.2 乘法法則 乘法法則 相互獨(dú)立 的事件 A、 B 分別有 k 和 l 種方法產(chǎn)生 ， 則選取 A以后 再選取 B 的方法數(shù)為 kl 種 。

8、 集合論定義 設(shè) 是有限集合，且 ，則有 。 11 mm ii ii S S S 1 m i i SS ( 1 , 2, ., )iS i m 12 ( , , ., ) | , 1 , 2, ., m i ia a a a S i m 1.1 乘法法則 例 4 1.1 加法法則和乘法法則 1.1.2 乘法法則 例 題 例 4、 從 A 地到 B地有二條不同的道 路 ， 從 B地到 C地有四條不同的道路 ， 而從 C地到 D地有三條不同的道路 。 求從 A地經(jīng) B、 C兩地到達(dá) D地的道路 數(shù) 。 解： 設(shè) S是所求的道路數(shù)集合 ， S1、 S2、 S3分別是從 A到 B、 從 B到 C、 從

9、 C到 D的道路集合 ， 根據(jù)乘法 法則 有 S S S S1 2 3| | | | | | | | 2 4 3 24 1.1 乘法法則 例 5 1.1 加法法則和乘法法則 1.1.2 乘法法則 例 題 例 5、 由數(shù)字 1,2,3,4,5可以構(gòu)成多少個(gè) 所有數(shù)字互不相同的四位偶數(shù) ？ 解： 所求的是四位偶數(shù) ， 故個(gè)位只能選 2或 4， 有兩種選 擇方法；又由于要求四位數(shù)字互不相同 ， 故個(gè)位選中后 ， 十位只有四種選擇方法；同理 ， 百位 、 千位分別有三種 、 兩種選擇方法 ， 根據(jù)乘法 法則 ， 四位數(shù)互不相同的偶數(shù) 個(gè)數(shù)為 2432=48 1.1 乘法法則 例 6 1.1 加法法則和

10、乘法法則 1.1.2 乘法法則 例 題 例 6、 求出從 8個(gè)計(jì)算機(jī)系的學(xué)生 、 9 個(gè)數(shù)學(xué)系的學(xué)生和 10個(gè)經(jīng)濟(jì)系的學(xué)生 中選出兩個(gè)不同專業(yè)的學(xué)生的方法數(shù) 。 解： 由乘法 法則 有 選一個(gè)計(jì)算機(jī)系和一個(gè)數(shù)學(xué)系的方法數(shù)為 89=72 選一個(gè)數(shù)學(xué)系和一個(gè)經(jīng)濟(jì)系的方法數(shù)為 910=90 選一個(gè)經(jīng)濟(jì)系和一個(gè)計(jì)算機(jī)系的方法數(shù)為 108=80 由加法 法則 ， 符合要求的方法數(shù)為 72+90+80=242 1.1 重集的概念 1.1 加法法則和乘法法則 1.1.3 計(jì)數(shù)問(wèn)題的分類 有序安排或有序選擇 允許重復(fù) /不允許重復(fù) 無(wú)序安排或無(wú)序選擇 允許重復(fù) /不允許重復(fù) 標(biāo)準(zhǔn)集的特性：確定、無(wú)序、 相異等

11、。 重集： B=k1*b1, k2*b2, kn*bn，其中： bi為 n個(gè)互不相 同的元素，稱 ki為 bi的 重?cái)?shù) ， i=1,2, n， n=1,2, ， ki=1,2, 。 重集的概念 1.2 線排列 1.2 排列 定義 1.1 1.2.1 線排列 集合論定義 定理 1.1 從 n個(gè)不同元素中，取 r個(gè) (0rn)按一 定順序排列起來(lái)，其排列數(shù) P(n,r)。 設(shè) A=an ，從 A中選擇 r個(gè) (0rn)元素排 列起來(lái)， A的 r有序子集， A的 r排列。 如 n, r Z且 nr0, P(n,r)=n!/(n-r)!。 如 n=r，稱全排列 P(n,n)= n!； 如 n r, P

12、(n,r)=0；如 r=0, P(n,r)=1。 證明： 構(gòu)造集合 A的 r排列時(shí) ， 可以從 A的 n各元素中任 選一個(gè)作為排列的第一項(xiàng) ， 有 n種選法；第一項(xiàng)選定后 從剩下的 n-1個(gè)元素中選排列的第二項(xiàng)有 n-1種選法； 由此類推 ， 第 r項(xiàng)有 n-r+1種選法 。 根據(jù)乘法 法則 有 !( , ) ( 1 ) .( 1 ) ( ) ! nP n r n n n r nr 1.2 線排列推論 1 1.2 排列 1.2.1 線排列 兩個(gè)推論 推論 1.1.1： 如 n, r N且 nr2，則 P(n,r)=nP(n-1,r-1) 。 證明： 在集合 A的 n個(gè)元素中 ， 任一個(gè)元素都可

13、以排在 它的 r排列首位 ， 故首位有 n種取法；首位取定后 ， 其 他位置的元素正好是從 A的另 n-1個(gè)元素中取 r-1個(gè)的排 列 ， 因此有 P(n-1,r-1)種取法 。 由乘法法則有 P(n,r)=nP(n-1,r-1) 證畢 。 1.2 線排列推論 2 1.2 排列 1.2.1 線排列 兩個(gè)推論 推論 1.1.1： 如 n, r N且 nr2，則 P(n,r)=nP(n-1,r-1) 。 推論 1.1.2： 如 n, r N且 nr2，則 P(n,r)= rP(n-1,r-1)+P(n-1,r) 。 證明： 當(dāng) r2時(shí) ， 把集合 A的 r排列分為兩大類：一類包含 A中的某個(gè)固定元

14、素 ， 不妨設(shè)為 a1， 另一類不包含 a1 。 第 一類排列相當(dāng)于先從 A-a1中取 r-1個(gè)元素進(jìn)行排列 ， 有 P(n-1,r-1)種取法 ， 再將 a1放入每一個(gè)上述排列中 ， 對(duì)任一 排列 ， a1都有 r種放法 。 由乘法法則 ， 第一類排列共有 rP(n-1,r-1)個(gè) 。 第二類排列實(shí)質(zhì)上是 A-a1的 r排列 ， 共 有 P(n-1,r)個(gè) 。 再由加法法則有 P(n,r)= rP(n-1,r-1)+P(n-1,r) 證畢 。 1.2 線排列例 1 1.2 排列 1.2.1 線排列 例 題 例 1、 由數(shù)字 1,2,3,4,5可以構(gòu)成多少個(gè)所有數(shù)字互不相同的四位數(shù) ？ 解：

15、由于所有的四位數(shù)字互不相同 ， 故每一個(gè)四位數(shù)就 是集合 1,2,3,4,5的一個(gè) 4排列 ， 因而所求的四位數(shù)個(gè) 數(shù)為 5!( 5, 4 ) 12 0 ( 5 4 ) !P 1.2 線排列例 2 1. 排列 1.2.1 線排列 例 題 例 2 、 將 具 有 9 個(gè) 字 母 的 單 詞 FRAGMENTS進(jìn)行排列 ， 要求字母 A總是緊跟在字母 R的右邊 ， 問(wèn)有 多少種這樣的排法 ？ 如果再要求字 母 M和 N必須相鄰呢 ？ 解： 由于 A總是 R的右邊 ， 故這樣的排列 相當(dāng)于 是 8個(gè)元 素的集合 F,RA,G,M,E,N,T,S的一個(gè)全排列 ， 個(gè)數(shù)為 如果再要求 M和 N必須相鄰

16、， 可先把 M和 N看成一個(gè)整 體 =M,N， 進(jìn)行 7個(gè)元素的集合 F,RA,G,E,T,S,的全 排列 ， 在每一個(gè)排列中再進(jìn)行 M,N的全排列 ， 由乘法 法則 ， 排列個(gè)數(shù)為 ( 8, 8 ) 8 ! 40 32 0P ( 7 , 7 ) ( 2, 2 ) 7 ! 2 ! 10 08 0PP 1.2 線排列例 3 1.2 排列 1.2.1 線排列 例 題 例 3、 有多少個(gè) 5位數(shù) ， 每位數(shù)字都 不相同 ， 不能取 0， 且數(shù)字 7和 9不能 相鄰 ？ 解： 由于所有的 5位數(shù)字互不相同 ， 且不能取 0， 故每一 個(gè) 5位數(shù)就是集合 1,2, ,9的一個(gè) 5-排列 ， 其排列數(shù)為

17、P(9,5)， 其中 7和 9相鄰的排列數(shù)為 c(7,3)4!242P(7,3)， 滿足題目要求的 5位數(shù)個(gè)數(shù)為 ( 9, 5 ) 4 2 ( 7 , 3 ) 15 12 0 16 80 13 44 0PP 1.2 圓排列 1.2 排列 定義 1.2 1.2.2 圓排列 定理 1.2 設(shè) A=an ， 從 A中取 r個(gè) (0rn)元素按 某種順序 （ 如逆時(shí)針 ） 排成一個(gè)圓圈 ， 稱為圓排列 （ 循環(huán)排列 ） 。 設(shè) A=an， A的 r圓排列個(gè)數(shù)為 P(n,r)/r。 證明： 由于把一個(gè)圓排列旋轉(zhuǎn)所得到另一個(gè)圓排列視為 相同的圓排列 ， 因此線排列 a1a2 ar， a2a3 ara1，

18、ara1a2 ar-1在圓排列中是一個(gè) ， 即一個(gè)圓排列可產(chǎn)生 r 個(gè)不同的線排列；同理 ， r個(gè)不同的線排列對(duì)應(yīng)一個(gè)圓 排列 。 而總共有 P(n,r)個(gè)線排列 ， 故圓排列的個(gè)數(shù)為 P(n,r)/r= n!/(r(n-r)!) 證畢 。 1.2 圓排列 例 4 1.2 排列 例 題 1.2.2 圓排列 例 4、 有 8人圍圓桌就餐 ， 問(wèn)有多少種就座方式 ？ 如果有兩人不愿坐在一起 ， 又有多少種就座方式 ？ 解： 由上述定理知 8人圍圓桌就餐 ， 有 8!/8=7!=5040種就 座方式 。 又有兩人不愿坐在一起 ， 不妨設(shè)此二人為 A、 B， 當(dāng) A、 B坐在一起時(shí) ， 相當(dāng)于 7人圍

19、圓桌就餐 ， 有 7!/7=6!種就 座方式 。 而 A、 B坐在一起時(shí) ， 又有兩種情況 ， 或者 A 在 B的左面 ， 或者 A在 B的右面 ， 因此 A、 B坐在一起時(shí) ， 共有 26!種就座方式 ， 因此如果有兩人不愿坐在一起 ， 就座方式為 7!-26!= 56!=3600 1.2 圓排列 例 5 1.2 排列 例 題 1.2.2 圓排列 例 5、 4男 4女圍圓桌交替就座有多 少種就座方式 ？ 解： 顯然 ， 這是一個(gè)圓排列問(wèn)題 。 首先讓 4個(gè)男的圍圓 桌就座 ， 有 4!/4=3!種就座方式 。 因?yàn)橐竽信畤鷪A桌 交替就座 ， 在男的坐定后 ， 兩兩之間均需留有一個(gè)空位 ，

20、女的就座相當(dāng)于一個(gè) 4元素集合的全排列 ， 就座方式數(shù) 為 4!。 由乘法法則知 ， 就座方式數(shù)為 3!4!=144 1.2 重排列 1.2 排列 定義 1.3 1.2.3 重排列 集合論定義 定理 1.3 從 n個(gè)不同元素中，可重復(fù)選取 r個(gè)按 一定順序排列起來(lái)，稱為重排列。 從重集 B=k1*b1, k2*b2, , k n*bn中選 取 r個(gè)按一定順序排列起來(lái)。 重集 B=*b1, *b2, , *bn 的 r排 列的個(gè)數(shù)為 nr。 證明： 構(gòu)造 B的 r排列如下：選擇第一項(xiàng)時(shí)可從 n個(gè)元素 中任選一個(gè) ， 有 n種選法 ， 選擇第二項(xiàng)時(shí)由于可以重復(fù) 選取 ， 仍有 n種選法 ， ， 同

21、理 ， 選擇第 r項(xiàng)時(shí)仍有 n種 選法 ， 根據(jù)乘法法則 ， 可得出 r排列的個(gè)數(shù)為 nr。 證畢 。 1.2 重排列 例 6 1.2 排列 例 題 1.2.3 重排列 例 6、 由數(shù)字 1,2,3,4,5,6這六個(gè)數(shù)字能組成多少個(gè)五位數(shù) ？ 又可組成多少 大于 34500的五位數(shù) ？ 解： 一個(gè)五位數(shù)的各位數(shù)字可重復(fù)出現(xiàn) ， 是一個(gè)典型的 重排列問(wèn)題 ， 相當(dāng)于重集 B=*1,*2, ,*6的 5排 列 ， 所求的五位數(shù)個(gè)數(shù)為 65=7776。 大于 34500的五位數(shù)可由下面三種情況組成： 萬(wàn)位選 4,5,6中的一個(gè) ， 其余 4位相當(dāng)于重集 B的 4排列 ， 由乘法法則知 ， 共有 36

22、4個(gè)五位數(shù)； 萬(wàn)位是 3， 千位 5,6中的一個(gè) ， 其余 3位相當(dāng)于重集 B的 3排列 ， 由乘法法則知 ， 共有 263個(gè)五位數(shù)； 萬(wàn)位是 3， 千位 4中的一個(gè) ， 百位選 5,6中的一個(gè) ， 其余 2位相當(dāng)于重集 B的 2排列 ， 由乘法法則知 ， 共有 262 個(gè)五位數(shù)； 由加法法則知 ， 大于 34500的五位數(shù)個(gè)數(shù)為 364 + 263 + 262=4392 1.2 重 排列計(jì)數(shù) 1.2 排列 1.2.3 重排列 定理 1.4 重集 B=n1*b1,n2*b2,n k*bk的全排列 個(gè)數(shù)為 112 ! , ! ! . ! k i ik n nn n n n 其 中 證明： 將 B

23、中的 ni個(gè) bi看作不同的 ni個(gè)元素 ， 賦予上標(biāo) 1,2, , ni， 即 ， 如此 ， 重集 B就變 成具有 n1+n2+ +nk=n個(gè)不同的元素集合 顯然 ， 集合 A的全排列個(gè)數(shù)為 n!。 又由于 ni個(gè) bi賦予上標(biāo)的方法有 ni!種 ， 于是對(duì)重集 B的任一 個(gè)全排列 ， 都可以產(chǎn)生集合 A的 n1!n2! nk!個(gè)排列 （ 由 乘法法則 ） ， 故重集 B的全排列個(gè)數(shù)為 證畢 。 注：利用組合數(shù)的計(jì)數(shù)方法同樣可以得出證明 。 12, , . , ( 1 , 2, . , )ini i ib b b i k 121 2 1 2 1 21 1 1 2 2 2 , , . , ,

24、, , . , , . , , , . , knnn k k kA b b b b b b b b b 112 ! ! ! . ! k i ik n nn n n n 其 中 1.2 重 排列 例 7 1.2 排列 1.2.3 重排列 例 題 例 6、 有四面紅旗 ， 三面藍(lán)旗 ， 二面 黃旗 ， 五面綠旗可以組成多少種由 14面旗子組成的一排彩旗 ？ 解： 這是一個(gè)重排列問(wèn)題，是求重集 4*紅旗 ,3*藍(lán)旗 ,2*黃 旗 ,5*綠旗 的全排列個(gè)數(shù)，根據(jù)定理，一排彩旗的種數(shù)為 14 ! 2522520 4 ! 3 ! 2 ! 5 ! 1.2 重 排列 例 8 1.2 排列 1.2.3 重排列

25、例 題 例 8、 用字母 A、 B、 C組成五個(gè)字母 的符號(hào) ， 要求在每個(gè)符號(hào)里 ， A至多 出現(xiàn) 2次 ， B至多出現(xiàn) 1次 ， C至多出 現(xiàn) 3次 ， 求此類符號(hào)的個(gè)數(shù) 。 解： 這也是一個(gè)重排列問(wèn)題。根據(jù)分析，符合題意的符號(hào) 個(gè)數(shù)相當(dāng)于求重集 M=2*A,1*B,3*C的 5排列個(gè)數(shù)，可分 為三種情況：需要分別求 M-A、 M-B和 M-C的全排列 個(gè)數(shù)。根據(jù)加法法則，此類符號(hào)個(gè)數(shù)為 5 ! 5 ! 5 ! 60 1 ! 1 ! 3 ! 2 ! 0 ! 3 ! 2 ! 1 ! 2 ! 1.2 項(xiàng)鏈排列 1.2 排列 定義 1.4 1.2.4 項(xiàng)鏈排列 對(duì)圓排列，通過(guò)轉(zhuǎn)動(dòng)、平移、翻轉(zhuǎn)、可

26、重合的，即 可看作項(xiàng)鏈排列。 如 n個(gè)不同元素的 r項(xiàng)鏈排列個(gè)數(shù)為 P(n,r)/(2r)， 具體參照 Plya定理 。 1.3 無(wú)重組合 1.3 組合 定義 1.5 1.3.1 （無(wú)重）組合 集合論定義 定理 1.5 設(shè) A=an，從 A中選擇 r個(gè) (0rn)元素組合 起來(lái)， A的 r無(wú)序子集， A的 r組合。 如 rn，有 C(n,r)=P(n,r)/r!=n!/(r!(n-r)!)。 如 nr=0， C(n,r)=1； 如 n r， C(n,r)=0。 從 n個(gè)不同元素中，取 r個(gè) (0rn)不考 慮順序組合起來(lái)，其組合數(shù) C(n,r) 或 。 nr 證明： 從 n個(gè)不同元素中取 r個(gè)

27、元素的組合數(shù)為 C(n,r)， 而 r個(gè)元素可組成 r!個(gè) r排列 ， 即一個(gè) r組合對(duì)應(yīng) r!個(gè) r 排列 。 于是 C(n,r)個(gè) r組合對(duì)應(yīng) r!C(n,r)個(gè) r排列 ， 這是 從 n個(gè)不同元素中取 r個(gè)元素的 r排列數(shù) P(n,r)， 因此有 ( , ) !( , ) ! ! ( ) ! P n r nnC n r r r r n r 1.3 無(wú)重 組合推論 1 1.3 組合 1.3.1 （無(wú)重）組合 三個(gè)推論 推論 1.5.1： C(n,r)=C(n,n-r) 證明： 實(shí)際上 ， 從 n個(gè)不同元素中選出 r個(gè)元素的同時(shí) ， 就有 n-r個(gè)元素沒(méi)有被選出 ， 因此選出 r個(gè)元素的方式

28、數(shù) 等于選出 n-r個(gè)元素的方式數(shù) ， 即 C(n,r)=C(n,n-r)。 得證 。 另外 ， 也可通過(guò)計(jì)算得出證明如下 !( , ) ( , ) ( ) ! ( ( ) ) ! ! ! nnC n n r C n r n r n n r n r r 1.3 無(wú)重 組合推論 2 1.3 組合 1.3.1 （無(wú)重）組合 三個(gè)推論 推論 1.5.1： C(n,r)=C(n,n-r) 推論 1.5.2 (Pascal公式 )： C(n,r) =C(n-1,r)+C(n-1,r-1) 證明： 利用組合分析法 。 在集合 A的 n個(gè)不同元素中固 定一個(gè)元素 ， 不妨設(shè)為 a1 ， 從 n個(gè)元素中選出

29、r個(gè)元素的 組合由下面兩種情況組成： r個(gè)元素中包含 a1。 相當(dāng)于從除去 a1的 n-1個(gè)元素中選 出 r-1個(gè)元素的組合 ， 再加上 a1而得到 ， 組合數(shù)為 C(n- 1,r-1)； r個(gè)元素中不包含 a1。 相當(dāng)于從除去 a1的 n-1個(gè)元素中 選出 r個(gè)元素的組合而得到 ， 組合數(shù)為 C(n-1,r)。 由加法法則即得 C(n,r)=C(n-1,r)+C(n-1,r-1) 另外 ， 也可通過(guò)計(jì)算得出證明如下 ! ( 1 ) ! ( ) ( 1 ) ! ( 1 ) ! ( , ) ! ( ) ! ! ! ( 1 ) ! ( 1 ) ! ( 1 ) ! ( 1 ) ! ! ( 1 ) !

30、 ( 1 ) ! ( 1 ( 1 ) ) ! ( 1 , ) ( 1 , 1 ) n n n n r n r n C n r r n r r n r r r n r n r nn r n r r n r C n r C n r 1.3 無(wú)重 組合推論 3 1.3 組合 1.3.1 （無(wú)重）組合 三個(gè)推論 推論 1.5.1： C(n,r)=C(n,n-r) 推論 1.5.2 (Pascal公式 )： C(n,r)=C(n- 1,r)+C(n-1,r-1) 推論 1.5.3： C(n,r)=C(n-1,r-1)+C(n-2,r- 1)+ + C(r-1,r-1) 證明： 反復(fù)利用 Pascal公式

31、 ， 即可證明 。 或利用組合分析法，在集合 A=an的 n個(gè)不同元素選出 r個(gè)元素的 組合可分為以下多種情況： 如 r個(gè)元素中包含 a1，相當(dāng)于從除去 a1的 n-1個(gè)元素中選出 r-1個(gè)元素的組合，再加上 a1而得到，組合 數(shù)為 C(n-1,r-1)；如 r個(gè)元素中不包含 a1但包含 a2，相當(dāng)于從除去 a1,a2的 n-2個(gè)元素中選出 r-1個(gè)元素的組合，再加上 a2而得到，組 合數(shù)為 C(n-2,r-1), 同理如 r個(gè)元素中不包含 a1,a2, an-r，但包含 an-r+1，相當(dāng)于從剩下的 r-1個(gè)元素中選出 r-1個(gè)元素的組合，再加 上 an-r+1而得到，組合數(shù)為 C(r-1,

32、r-1) 。由加法法則得 C(n,r)=C(n-1,r-1)+C(n-2,r-1)+ + C(r-1,r-1) 1.3 無(wú)重 組合 例 1 1.3 組合 1.3.1 （無(wú)重）組合 例 題 例 1、 有 5本日文書 ， 7本英文書 ， 10 本中文書 ， 從中取兩本不同文字的書 ， 問(wèn)有多少種方案 ？ 若取兩本相同文字 的書 ， 問(wèn)有多少種方案 ？ 任取兩本書 ， 有多少種方案 ？ 解： 從三種文字的書中取兩種共有 C(3,2)=3種取法 。 根據(jù)乘法法 則有：日英各一本的方法數(shù)為 57=35， 中英各一本的方法數(shù)為 107=70， 中日各一本的方法數(shù)為 105=50， 由加法法則得 35+70

33、+50=155 取兩本相同文字的，有兩本中文、兩本英文或兩本日文三種方 式，由加法法則得 C(5,2)+C(7,2)+C(10,2)=76 任取兩本書，相當(dāng)于從 5+7+10=22本書中取兩本的組合，即 C(22,2)=231 1.3 無(wú)重 組合 例 2 1.3 組合 1.3.1 （無(wú)重）組合 例 題 例 2、 從 1300之間任取 3個(gè)不同的數(shù) ， 使得這 3個(gè)數(shù)的和正好被 3除盡 ， 問(wèn)共 有幾種方案 ？ 解： 所有的整數(shù)可分為以下 3個(gè)分類：模 3余 0、 模 3余 1和模 3余 2， 故 1300 的 300 個(gè) 數(shù)可 以分為 3 個(gè)集 合： A=1,4, ,298 ， B=2,5,

34、,299， C=3,6, ,300。 任取 3個(gè)數(shù)其和正好被 3整除的 情況如下： 三個(gè)數(shù)同屬于集合 A， 有 C(100,3)種方案； 三個(gè)數(shù)同屬于集合 B， 有 C(100,3)種方案； 三個(gè)數(shù)同屬于集合 C， 有 C(100,3)種方案； 三個(gè)數(shù)分別屬于集合 A,B,C， 由乘法法則有 1003種方案 。 由加法法則得 ， 所求的方案數(shù)為 3C(100,3)+1003=1485100 1.3 無(wú)重 組合 例 3 1.3 組合 1.3.1 （無(wú)重）組合 例 題 例 3、 某車站有 1到 6個(gè)入口處 ， 每個(gè) 入口處每次只能進(jìn)一個(gè)人 ， 問(wèn)一小組 9個(gè)人進(jìn)站的方案數(shù)有多少 ？ 解 I： 按照

35、從入口 1到入口 6的順序可得到 9個(gè)人一個(gè)排列 ， 再把 兩個(gè)入口間設(shè)上一個(gè)標(biāo)志 ， 加上這 5個(gè)標(biāo)志相當(dāng)于每一個(gè)排列有 14個(gè)元素 ， 其中 5個(gè)標(biāo)志沒(méi)有區(qū)別 ， 但其位置將區(qū)分各入口的進(jìn) 站人數(shù) ， 相當(dāng)于 14個(gè)元素集合的 5組合 ， 故進(jìn)站方案數(shù)為 9!C(14,5)=726485760 解 II： 同上分析 ， 問(wèn)題轉(zhuǎn)化為重集 1*p1,1*p2, ,1*p9,5*標(biāo)志 的 全排列 （ pi代表 9個(gè)人 ， i=1, ,9） ， 故進(jìn)站方案數(shù)為 14!/5!=726485760 解 III： 考慮 9個(gè)人選擇方案 ， 第 1個(gè)人有 6種選擇 ， 第 2個(gè)人除了 選擇入口 ， 還要考

36、慮在第 1個(gè)人的前面或后面 ， 故有 7種選擇 同理 ， 第 9個(gè)人有 14種選擇 ， 根據(jù)乘法法則 ， 故進(jìn)站方案數(shù)為 67 14=726485760 1.3 無(wú)重 組合 例 4 1.3 組合 1.3.1 （無(wú)重）組合 例 題 例 4、 求 5位數(shù)中至少出現(xiàn)一個(gè) 6， 而被 3整除的數(shù)的個(gè)數(shù) 。 解： 10進(jìn)制數(shù)被 3整除的充要條件是各位數(shù)的和能被 3整除 。 據(jù) 此可進(jìn)行如下討論： 從左往右計(jì) ， 如最后一個(gè) 6出現(xiàn)在個(gè)位 ， 則十百千位各有 10種 選擇 ， 萬(wàn)位有 3種可能 ， 根據(jù)乘法法則 ， 總個(gè)數(shù)為 3103 ； 如最后一個(gè) 6出現(xiàn)在十位 ， 則個(gè)位有 9種選擇 ， 百千位各有

37、10 種選擇 ， 萬(wàn)位有 3種可能 ， 根據(jù)乘法法則 ， 總個(gè)數(shù)為 31029 ； 如最后一個(gè) 6出現(xiàn)在百位 ， 則個(gè)十位各有 9種選擇 ， 千位有 10 種選擇 ， 萬(wàn)位有 3種可能 ， 根據(jù)乘法法則 ， 總個(gè)數(shù)為 31092； 如最后一個(gè) 6出現(xiàn)在千位 ， 則個(gè)十百位各有 9種選擇 ， 萬(wàn)位有 3 種可能 ， 根據(jù)乘法法則 ， 總個(gè)數(shù)為 393； 如最后一個(gè) 6出現(xiàn)在萬(wàn)位 ， 則個(gè)十百位各有 9種選擇 ， 千位有 3 種可能 ， 根據(jù)乘法法則 ， 總個(gè)數(shù)為 393 ； 根據(jù)加法法則 ， 符合條件的整數(shù)個(gè)數(shù)為 3103 + 31029 + 31092 + 393 + 393 =12504 1

38、.3 無(wú)重 組合 例 5 1.3 組合 1.3.1 （無(wú)重）組合 例 題 例 5、 求 1000!的末尾有幾個(gè)零 。 解： 此問(wèn)題在于求將 1000!分解為素?cái)?shù)的乘積時(shí) ， 2和 5的 冪是多少 。 末尾零的個(gè)數(shù)應(yīng)該等于 2和 5的冪中較小的那個(gè) 數(shù) 。 11000中 5的倍數(shù)的數(shù)共 200個(gè) ， 其中有 40個(gè) 52的倍數(shù) ， 這 40個(gè)數(shù)中有 8個(gè) 53的倍數(shù) ， 而這 8個(gè)數(shù)中又有 1個(gè) 54的倍數(shù) ， 故 1000!分解為素?cái)?shù)的乘積時(shí) ， 5的冪應(yīng)該是 200+40+8+1=249 顯然 ， 2的冪必然大于 249， 因此 1000!的末尾有 249個(gè)零 。 1.3 無(wú)重 組合 例 6

39、 1.3 組合 1.3.1 （無(wú)重）組合 例 題 例 6、 求能除盡 1400的正整數(shù)數(shù)目 （ 1 除外 ） ， 其中包含多少個(gè)奇數(shù) ？ 解： 1400=23527， 故除盡 1400的正整數(shù)分解為素?cái)?shù)的乘積 的形式應(yīng)該為 2l5m7n， 其中 0 l3,0m2,0n1， 但應(yīng)排除 l=m=n=0的情況 。 故滿足條件的數(shù)目為 (3+1)(2+1)(1+1)-1=23 其中包含的奇數(shù)為 (1)(2+1)(1+1)-1=5 1.3 重復(fù)組合 1.3 組合 定義 1.6 1.3.2 重復(fù)組合 集合論定義 定理 1.6 從 n個(gè)不同元素中，可重復(fù)選取 r個(gè)不 考慮順序組合起來(lái)，其組合數(shù) F(n,r)

40、。 從重集 B=k1*b1, k2*b2, , k n*bn中取 r 個(gè)元素不考慮順序的組合。 重集 B=*b1, *b2, , *bn 的 r組 合數(shù) F(n,r) = C(n+r-1, r) 證明： 設(shè) n個(gè)元素 b1,b2, ,bn和自然數(shù) 1,2, ,n一一對(duì)應(yīng) 。 于 是任何組合皆可看作是一個(gè) r個(gè)數(shù)的組合 c1,c2, ,cr。 由于 是組合 ， 不妨認(rèn)為各 ci是按照大小順序排列的 ， 相同的 ci連 續(xù)排在一起 ， 不妨設(shè) c1 c2 cr 。 又令 di=ci+i-1(i=1,2, ,r)， 即 d1=c1,d2=c2+1, ,dr=cr+r-1。 因 1 ci n， 故 1

41、 di n+r-1， 得到一個(gè)集合 1,2, ,n+r-1 的 r組合 d1,d2, ,dr (d1 d2 dr) 。 顯然有一種 c1,c2, ,cr的取法 ， 就有一種 d1,d2, ,dr的取 法 ， 反之亦然 ， 這兩種取法是 一一對(duì)應(yīng)的 ， 從而這兩種取 法是 等價(jià)的 。 如此 ， 從 n個(gè)不同元素中可重復(fù)選取 r個(gè)的組 合數(shù) ， 和從 n+r-1個(gè)不同元素中不重復(fù)選取 r個(gè)的組合數(shù)是 相同的 ， 故 F(n,r) = C(n+r-1, r) 1.3 重復(fù) 組合 例 7 1.3 組合 定理 1.7 1.3.2 重復(fù)組合 例 題 r個(gè)無(wú)區(qū)別的球放入 n個(gè)有標(biāo)志的盒子 里，每盒的球數(shù)可多

42、于 1個(gè)，則共有 F(n,r)種方案。 例 7、 試問(wèn) (x+y+z)4的展開(kāi)式有多少 項(xiàng) ？ 證明： 這是一個(gè)允許重復(fù)組合的典型問(wèn)題 ， 實(shí)質(zhì)上定 理 1.6的另一種說(shuō)法 。 由于每盒的球數(shù)不受限制 ， 相當(dāng) 于重集 *a1,*a2, ,*an的 r組合 。 解： (x+y+z)4展開(kāi)式每一項(xiàng)都是 4次方的 ， 相當(dāng)于從 3個(gè) 不同元素中可以重復(fù)的選擇 4個(gè) ， 或者相當(dāng)于將 4個(gè)無(wú) 區(qū)別的球放到 3個(gè)有標(biāo)志的盒子里 。 故展開(kāi)項(xiàng)個(gè)數(shù)為 F(3,4)=C(3+4-1,4)=15 1.3 重復(fù) 組合 例 8、 9 1.3 組合 例 題 1.3.2 重復(fù)組合 例 8、 某餐廳有 7種不同的菜 ，

43、 為了招 待朋友 ， 一個(gè)顧客需要買 14個(gè)菜 ， 問(wèn) 有多少種買法 ？ 例 9、 求 n個(gè)無(wú)區(qū)別的 球放入 r個(gè)有標(biāo)志的盒 子里 (nr)而無(wú)一空盒 的方案數(shù) 。 解： 這 個(gè) 問(wèn) 題 相 當(dāng) 于 重 集 *1,*2, ,*7的 14組合 。 根 據(jù)定理 1.6知買菜的方法數(shù)為 F(7,14)=C(7+14-1,14)=4845 解： 由于每個(gè)盒子不能為空 ， 故每個(gè)盒子里可先放一個(gè)球 ， 這樣還剩 n-r個(gè)球 ， 再將這 n-r個(gè)球防到 r個(gè)盒子里 ， 由于這時(shí) 每盒的球數(shù)不受限制 ， 相當(dāng)于重集 *a1,*a2, ,*ar的 n- r組合 。 根據(jù)定理 1.6知 ， 其組合數(shù)為 F(r,

44、n-r)=C(r+n-r-1,n-r)=C(n-1,r-1) 1.3 重復(fù) 組合 例 10 1.3 組合 例 題 1.3.2 重復(fù)組合 例 10、 在由數(shù) 0,1, ,9組成的 r位整數(shù)所組成的集合中 ， 如果將 一個(gè)整數(shù)重新排列得到另一個(gè)整數(shù) ， 則稱這兩個(gè)整數(shù)是 等價(jià) 的 。 那么 ， 有多少不等價(jià)的整數(shù)？ 如果 0和 9最多只能出現(xiàn)一次，又有多少不等價(jià)的整數(shù)？ 解： 分析題意知 ， 一個(gè) r位整數(shù)只和所取的數(shù)字有關(guān) ， 與其順 序無(wú)關(guān) ， 因而是個(gè)組合問(wèn)題 。 又每一整數(shù)的每一位可從 0,1, ,9 中任取 ， 故不等價(jià)的 r位整數(shù)相當(dāng)于重集 *0,*1, ,*9的 r 組合 。 根據(jù)定

45、理 1.6知 ， 其組合數(shù)為 F(10,r)=C(10+r-1, r)=C(9+r,r) 0和 9最多只出現(xiàn)一次 ， 可分為三種情況：均不出現(xiàn)時(shí)相當(dāng)于 重集 B=*1,*2, ,*8的 r組合 ， 組合數(shù)為 F(8,r)=C(r+7,r)； 只出現(xiàn)其一 ， 若 0出現(xiàn) ， 相當(dāng)于 B的 r-1組合 ， 然后加入 0， 組合 數(shù)為 F(8,r-1)=C(r+6,r-1)， 同理 9出現(xiàn)的組合數(shù)為 C(r+6,r-1) ；均 出現(xiàn)一次 ， 相當(dāng)于 B的 r-2組合 ， 然后加入 0,9， 組合數(shù)為 F(8,r- 2)=C(r+5,r-2)， 由加法法則知 ， 符合題意的整數(shù)個(gè)數(shù)為 C(r+7,r)

46、+2C(r+6,r-1)+C(r+5,r-2) 1.3 重復(fù) 組合 例 11 1.3 組合 例 題 1.3.2 重復(fù)組合 例 11、 求方程 x1+x2+ +xn=r的非負(fù)整數(shù)解的個(gè) 數(shù) ， 其中 n,r為正整數(shù) 。 解： 設(shè) 重集 B=*b1,*b2, ,*bn， B的任一個(gè) r組 合都具有形式 x1*b1,x2*b2, ,xn*bn， 其中 xi(i=1,2, ,n) 是非負(fù)整數(shù)且滿足方程 x1+x2+ +xn=r 。 反之 ， 每一個(gè)滿足方程 x1+x2+ +xn=r的非負(fù)整數(shù)解 x1,x2, ,xn都對(duì)應(yīng)重集 B的一個(gè) r組合 。 因此 ， 方程 x1+x2+ +xn=r的非負(fù)整數(shù)解的

47、個(gè)數(shù)就等于重集 B的 r 組合數(shù) F(n,r)。 1.3 不相鄰組合 1.3 組合（ 3） 1.3 組合 定義 1.7 1.3.3 不相鄰組合 定理 1.8 從序列 A=1,2, n個(gè)中選取 r個(gè)，其 中不存在 i,i+1兩個(gè)相鄰的數(shù)同時(shí)出現(xiàn) 于一個(gè)組合的組合。 從序列 A=1,2, n個(gè)中選取 r個(gè)作不相 鄰的組合，其組合數(shù)為 C(n-r+1, r) 證明： 設(shè) d1,d2, ,dr是所求的一個(gè)不相鄰組合 ， 不妨設(shè) d1 d2 dr。 令 ci=di-i+1(i=1,2, ,r)， 即 c1=d1,c2=d2-1, ,cr=dr-r+1。 因 1 di n， 故 1 ci n-r+1， 得

48、到一個(gè)集合 1,2, ,n-r+1的 r組合 。 顯然有一種 d1,d2, ,dr的取法 ， 就有一種 c1,c2, ,cr的取法 。 反之亦然 ， 集合 1,2, ,n-r+1的一個(gè) r組合 c1,c2, ,cr， 不妨設(shè) c1 c2 cr。 令 di=ci+i-1(i=1,2, ,r)， 即 d1=c1,d2=c2 1, ,dr=cr +r-1。 因 1 ci n-r+1， 故 1 di n， 得到一個(gè)集合 1,2, ,n的不 相鄰組合 d1,d2, ,dr 。 顯然有一種 c1,c2, ,cr的取法 ， 就有一種 d1,d2, ,dr的取法 。 故這兩種取法是 一一對(duì)應(yīng)的 ， 從而這兩種

49、取法是 等價(jià)的 。 從 n個(gè) 不同元素中可選取 r個(gè)的不相鄰組合數(shù) ， 和從 n-r+1個(gè)不同元素中 選取 r個(gè)的組合數(shù)是相同的 ， 即 C(n-r+1, r)。 1.4 二項(xiàng)式定理 1.4 二項(xiàng)式定理 定理 1.9 0 , , , ( ) nn k n k k nn N x y R x y x yk如 有 證明： 因?yàn)?(x+y)n=(x+y)(x+y) (x+y)， 等式右端有 n個(gè)因子 ， 項(xiàng) xkyn-k是從這 n個(gè)因子中選取 k個(gè)因子 ， k=0,1, ,n。 在這 k個(gè) (x+y) 里都取 x， 而從剩下的 n-k個(gè)因子 (x+y)中選取 y作乘積得到 ， 因此 xkyn-k的系數(shù)

50、為上述選法的個(gè)數(shù) C(n,r)。 故有 證畢 。 注：可用數(shù)學(xué)歸納法證明 ， 證明略； C(n, k)又稱 二項(xiàng)式系數(shù) 。 0 () nn k n k k nx y x yk 1.4 二項(xiàng)式定理推論 1 1.4 二項(xiàng)式定理 四個(gè)推論 推論 1.9.1： 推論 1.9.2： 推論 1.9.3： 0 00 , , , ( ) n n k n k k nn n k k n k k kk nn N x y R x y x y nk nnx y x y k n k 如 有 00 , , ( 1 ) nnn k k kk nnn N x R x x xk n k 如 有 0 ,2n n k nnN k 如

51、 有 證明： 在推論 1.9.2中令 x=1， 即可得證 。 利用組合分析 ， 等式左端相當(dāng)于從 A=an中任意選擇 k(0kn)個(gè) 元素的所有可能數(shù)目 ， 即對(duì) n個(gè)元素 ， 每一個(gè)都有被選擇和不被 選擇的可能 ， 總的可能數(shù)為 2n。 另外 ， 該等式還表明 A的所有子集個(gè)數(shù)為 2n。 1.4 二項(xiàng)式定理推論 2 1.4 二項(xiàng)式定理 四個(gè)推論 推論 1.9.1： 推論 1.9.2： 推論 1.9.3： 推論 1.9.4： 0 00 , , , ( ) n n k n k k nn n k k n k k kk nn N x y R x y x y nk nnx y x y k n k 如

52、有 00 , , ( 1 ) nnn k k kk nnn N x R x x xk n k 如 有 0 ,2n n k nnN k 如 有 0 , ( 1 ) 0n k k nnN k 如 有 證明： 在推論 1.9.2中令 x=-1， 即可得證 。 另外 ， 該等式還表明 A=an的偶數(shù)子集個(gè)數(shù)和奇數(shù)子集個(gè)數(shù)相等 。 1.4 廣義二項(xiàng)式定理 1.4 二項(xiàng)式定理 定理 1.10 定義 1.8 ( , ) , , ( 1 ) .( 1 ) / ! 0 10 00 C k R k Z k k k kk k 廣義 二項(xiàng)式系數(shù) 為： kk k R x y x y x yk 0 , | | 1 , (

53、 ) 如 有 牛頓二項(xiàng)式定理： 1.4 廣義 二項(xiàng)式定理 推論 1 1.4 二項(xiàng)式定理 六個(gè)推論 推論 1.10.1： 推論 1.10.2： k k z z zk 0 | | 1 , ( 1 ) 有 n k k k nkz z zk 0 1| | 1 , ( 1 ) ( 1 ) 有 證明： 00 0 0 ( 1 ) .( 1 ) ( 1 ) ! ( 1 ) ( 1 ) .( 1 ) ! 1 ( 1 ) n k k kk k k k kk k n n n kn z z z k k n n n k z k nk z k 1.4 廣義 二項(xiàng)式定理 推論 2 1.4 二項(xiàng)式定理 六個(gè)推論 推論 1.1

54、0.1： 推論 1.10.2： 推論 1.10.3： 推論 1.10.4： 推論 1.10.5： k k z z zk 0 | | 1 , ( 1 ) 有 n k k k nkz z zk 0 1| | 1 , ( 1 ) ( 1 ) 有 kk k z z z1 0 | | 1 , ( 1 ) ( 1 ) 有 k k z z z1 0 | | 1 , ( 1 ) 有 k kk k kz z zk k 1 21 1 ( 1 ) 22| | 1 , 1 1 12 有 證明： 當(dāng) =1/2時(shí) ， C(,0)=1， 而對(duì)于 k 0， 有 將上式代入推論 1.10.1即可得證 。 1 1 1 2 1 2

55、 1 21 1 2 ( 1 2 1 ) .( 1 2 1 ) ! ( 1 ) 1 3 . ( 2 3 ) 2! ( 1 ) 1 2 3 4 . ( 2 3 ) ( 2 2 ) 2 2 4 . ( 2 2 ) ! ( 1 ) ( 2 2 ) ! 2 ( ( 1 ) ! ) ( 1 ) 22 1 2 k k k k k k k k k k k k k kk kk k kk k k k 1.4 廣義 二項(xiàng)式定理 推論 3 1.4 二項(xiàng)式定理 六個(gè)推論 推論 1.10.1： 推論 1.10.2： 推論 1.10.3： 推論 1.10.4： 推論 1.10.5： 推論 1.10.6： k k z z z

56、k 0 | | 1 , ( 1 ) 有 n k k k nkz z zk 0 1| | 1 , ( 1 ) ( 1 ) 有 kk k z z z1 0 | | 1 , ( 1 ) ( 1 ) 有 k k z z z1 0 | | 1 , ( 1 ) 有 k kk k kz z zk k 1 21 1 ( 1 ) 22| | 1 , 1 1 12 有 n k k k rz z r r nkrz r z k0 | | 1 , | | 1 | | , 0 1( 1 ) 即 是 非 常 數(shù) ， 有 1.5 組合恒等式及其含義 1 1.5 組合恒等式及其含義 恒等式 1： 如 n,k N， 有 C(n,

57、k)=(n/k)C(n-1,k-1) 證明： 從 n個(gè)元素中取 k個(gè)的組合可先從 n個(gè)元素中取 1個(gè) ， 再?gòu)?剩下的 n-1個(gè)元素中選擇 k-1個(gè) ， 組合數(shù)為 C(n-1,k-1)。 選出的 k個(gè) 元素都有可能被第一次選中 ， 因是組合 ， 故重復(fù)度為 k。 得證 。 或通過(guò)計(jì)算證明： nnn kn kk k kn n n n kn k kk n n n n k n n kk k k k 1 , 0 1 1, ( 1 ) .( 1 ) ( 1 ) .1 ( 1 ) ( 2 ) .( 1 ) 1 1( 1 ) ( 2 ) .1 若 若 有 1.5 組合恒等式及其含義 2 1.5 組合恒等式及

58、其含義 恒等式 2： 1 1 , ( , ) 2n n k n N k C n k n 如 有 證明： 考慮盒子 1中有 n個(gè)有區(qū)別的球 ， 從中取一個(gè)球放入盒子 2 中 ， 再取任意多個(gè)球放入盒子 3中 。 等式左端表示先從盒子 1中 取 k(k=1,2, ,n)個(gè)球 ， 再?gòu)闹腥∫粋€(gè)放入盒子 2中 ， 剩下的 k-1個(gè) 球放入盒子 3中 。 等式右端表示先從盒子 1中取一個(gè)放入盒子 2中 ， 剩下的 n-1個(gè)球是否放入盒子 3中均有兩種可能 。 顯然兩種取法 結(jié)果是一樣的 。 得證 。 或通過(guò) 計(jì)算 證明： 1 1 1 1 10 1 11 11 11 1 2 n n n k k k nn

59、kk n nn n n k k n k k kk nn nn kk n 1.5 組合恒等式及其含義 3 1.5 組合恒等式及其含義 恒等式 3： 0 , ( 1 ) ( , ) 0n k k n N k C n k 如 有 證明： 將等式兩邊對(duì) x微分得 在上式中 ， 令 x=-1得 即 得證 。 注：如令 x=1， 即可證明 恒等式 2。 0 11 1 1 1 1 0 ( 1 ) ( 1 ) ( 1 ) 0 ( 1 ) 0 n nk k n nk k n k k n k k n xx k n n x k x k n k k n k k 1.5 組合恒等式及其含義 4、 5 1.5 組合恒等式

60、及其含義 恒等式 5： 恒等式 4： 12 0 , ( 1 ) ( , ) 0n k k n N k C n k 如 有 22 0 , ( , ) ( 1 ) 2n n k n N k C n k n n 如 有 證明： 將等式兩邊對(duì) x微分得 將等式兩邊同乘以 x后再對(duì) x微分得 在上式中 ， 令 x=1得 得證 。 注：如令 x=-1， 即可證明 恒等式 5。 0 11 1 1 2 2 1 1 22 1 ( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 ) 2 n nk k n nk k n n n k k n n k n xx k n n x k x k n n x n x x k x k n k n n k 1.5 組合恒等式及其含義 6 1.5 組合恒等式及其含義 恒等式 6： 1 0 1 2 1, ( , ) 11 nn k n N C n kkn 如 有 證明： 將等式兩邊對(duì) x從 0到 1積分得 即 得證 。 0 11 00 0 11 11 0 00 1 0 ( 1 ) ( 1 ) ( 1 ) 11 2 1 1 11 n nk k n nk k nkn k n n k n xx k n x dx x dx k xx n k nk n k nk 恒等式 7： Vandermonde恒等式，如 n,m N且 rmi