1、組合數(shù)學(xué)(Combinatorics),哈爾濱工業(yè)大學(xué)(威海)計算機科學(xué)與技術(shù)學(xué)院 孟凡超 Email: Tele主要內(nèi)容,概述 鴿巢原理 排列與組合 生成排列和組合 二項式系數(shù) 容斥原理及應(yīng)用 遞推關(guān)系和生成函數(shù) 特殊計數(shù)序列 Polya計數(shù)法,二項式系數(shù),Pascal公式 二項式系數(shù),二項式系數(shù)性質(zhì),對于所有滿足0k n的整數(shù)k都成立。,二項式系數(shù),定理(Pascal公式)：對于滿足1kn-1的所有整數(shù)k和n，有,二項式系數(shù),B中的k-組合是通過把x添加到集合S-x的k-1組合中而得到的，因此，B的大小是,|B|=,因此，,二項式系數(shù),例：令n=5，k=3，S=x

2、,a,b,c,d。 S在A中的三組合是：a,b,c,a,b,d,a,c,d,b,c,d。 a,b,c,d的2組合是：a,b,a,c,a,d,b,c,b,d,c,d。 增加x后變?yōu)閤,a,b,x,a,c,x,a,d,x,b,c,x,b,d,x,c,d。該集合也是S在B中3組合。因此，,二項式系數(shù),Pascal三角形(楊輝三角形)：,根據(jù)Pascal公式,和,得到。,二項式系數(shù),1,3,6,10,在k=2列上的數(shù)等于n(n-1)/2是三角數(shù)。,二項式系數(shù),基于路徑的Pascal三角形解釋,p(n,k)：為從左上頂點(0,0)到頂點(n,k)的路徑條數(shù)，其中，在每一條途徑中，從一項移動到該項下一行在

3、其之下方的項，或其直接右下方。規(guī)定p(n,0)=1，p(n,n)=1。,二項式系數(shù),從(0,0)到(n,k)的每一條路徑或者是： 一條從(0,0)到(n-1,k)的路徑，再接著一次垂直移動(a)，或者 一條從(0,0)到(n-1,k-1)的路徑，再接著一次移動(b)。 因此，根據(jù)加法原理，有p(n,k)=p(n-1,k)+p(n-1,k-1)。 可以與計算二項式系數(shù) 完全相同的方法來計算p(n,k)，且 以相同的初始值開始。因此，對于所有的整數(shù)n和滿足0kn的k，有,(b),(a),(n,k),(n-1,k),(n,k),(n-1,k-1),(n-1,k),二項式系數(shù),例：從(0,0)點沿水平

4、和垂直道路可以到點(m,n)有多少種方法？,二項式系數(shù),將上面的Pascal公式中的n換成m+n，將k換成m，可以得到如下公式：,由前面的例子可知， 是從(0,0)到(m,n)點的路徑數(shù)，這些路徑可以分為兩類：一類是從(0,0)到(m-1,n)點到達(m,n)，另一類是由(0,0)到(m,n-1)到達(m,n)點。,二項式系數(shù),二項式系數(shù),二項式定理：令n是一個正整數(shù)。于是，對所有的x和y，有,用求和記號寫出，即,二項式系數(shù),證明(方法1)：將(x+y)n寫成每一個因子都等于x+y的n個因子的乘積(x+y)n=(x+y)(x+y)(x+y)。 用分配律將該乘積完全展開，由于對于每個因子都可以選

5、擇x或者y，故結(jié)果存在2n項并且每一項都可以寫成xn-kyk 的形式，其中， k=0,1,2,n。,通過在n個因子中的k個選擇y且在剩下的n-k個因子中選擇x而得到項xn-kyk。這樣，在展開的乘積項xn-kyk出現(xiàn)的次數(shù)等于n個因子的集合的k-組合的個數(shù) 。,因此,二項式系數(shù),(方法2)：通過對n用歸納法證明。如果n=1，則公式變成,顯然，n=1時成立?，F(xiàn)在假設(shè)該公式對正整數(shù)n成立，下面我們證明該公式對n+1也成立。,用k-1代替k,二項式系數(shù),因此，,根據(jù)Pascal公式，上式變?yōu)?由于,于是重寫上式得到：,這就是用n+1代替n后的二項式定理，由歸納法該定理成立。,二項式系數(shù),二項式定理的

6、幾種等價形式：,二項式系數(shù),定理：令n為一正整數(shù)，則對所有的x，有,(x+y)2=x2+2xy+y2 (x+y)3=x3+3x2y+3xy2+y3 (x+y)4=x4+4x3y+6x2y2+4xy3+y4,在這些展開式中出現(xiàn)的系數(shù)就是Pascal三角形的行上的數(shù)。,二項式系數(shù),二項式所滿足的一些恒等式 恒等式1： (n和k為正整數(shù))。,恒等式2：,恒等式3：,恒等式4：,二項式系數(shù),恒等式5：,恒等式6：,恒等式7：,二項式系數(shù),對二項式進行微分，可以等到許多有趣的恒等式,兩邊對x微分，得到,令x=1，可以得到恒等式7。,令x=1，得到恒等式2,二項式系數(shù),恒等式8：Pascal三角形一行上各

7、數(shù)的平方和的恒等式為,證明：令S為2n個元素的集合。上式右邊為S的n-組合的個數(shù)。把S劃分成兩個子集A和B，每個子集都有n個元素。,二項式系數(shù),用S的這個劃分來劃分S的n組合。 S的每個n組合含有A的k個元素，而其余的n-k個元素則來自B，k可以是0到n之間的任意整數(shù)。 我們把S的n組合劃分成n+1個部分： C0,C1,C2,Cn 其中，Ck由那些包含A的k個元素和B的n-k個元素的n組合組成。根據(jù)加法原理，有,二項式系數(shù),Ck的一個n組合通過從A中選擇k個元素，然后從B中再選擇 (n-k)個元素得到，第一步有 種選擇，第二步有 種選擇，由乘法原理，有,所以,二項式系數(shù),令r為實數(shù)且k為整數(shù)。

8、然后定義二項式系數(shù)如下：,Pascal公式和恒等式1對于所有的r和k都是有效的。,二項式系數(shù),恒等式9：,二項式系數(shù),恒等式10：,二項式系數(shù),二項式定理：,二項式系數(shù)：,多項式系數(shù)：,表示重數(shù)分別為：n1,n2,nt的t種不同類型物體的多重集排列個數(shù)。,二項式系數(shù),二項式系數(shù)Pascal公式：,多項式系數(shù)Pascal公式：,二項式系數(shù)寫成多形式系數(shù)的形式：,二項式系數(shù),令t=3，并令n1,n2,n3為正整數(shù)，且n1+n2+n3=n，于是：,二項式系數(shù),多項式定理：令n為一個正整數(shù)。對于所有的x1,x2,xt，,其中求和對n1+n2+nt=n的所有的非負整數(shù)解n1,n2,nt進行。,二項式系數(shù)

9、,通過選擇n個因子中的n1個為x1，剩下的n-n1個因子中的n2個為x2，剩下的n-n1-nt-1個因子中的nt個為xt，得到,出現(xiàn)的次數(shù)為：,由乘法原理，項,二項式系數(shù),的展開式中有多少不同的項？,多項式展開中的不同的項的數(shù)目等于方程 n1+n2+nt=n 的非負整數(shù)解的數(shù)目。這些解的個數(shù)等于,在,二項式系數(shù),例：在(3x-2y)18的展開式中，x5y13的系數(shù)是什么？,例：在(2x1-x2+2x3-2x4)9的展開式中，x13x23x3x42的系數(shù)是什么？,二項式系數(shù),二項式定理：,二項式系數(shù),恒等式11：,其中，|z|1。,二項式系數(shù),因此，對|z|1,用-z代替z，得到,如果n=1,恒

10、等式12：,恒等式13：,二項式系數(shù),求多項式系數(shù)的另一種方法,二項式系數(shù),例：用牛頓二項式定理近似計算,令=1/2,二項式系數(shù),二項式系數(shù),二項式系數(shù)的單峰值 單峰：如果存在一個整數(shù)t，0t n，使得 s0s1st stst+1 sn 那么序列s0,s1,sn就是單峰的，其中，st為序列中的最大數(shù)。整數(shù)t不必是唯一的，因為最大數(shù)可以在序列中出現(xiàn)多于一次。 例如，序列：1,3,3,2是單峰的。,二項式系數(shù),定理：令n為正整數(shù)，二項式序列,是單峰序列。,如果n是偶數(shù)，則,如果n是奇數(shù)，則,二項式系數(shù),弱取整數(shù)：對于任意實數(shù)x，令 表示小于或等于x的最 大整數(shù)。整數(shù) 稱為x的弱取整。,強取整數(shù)：對

11、于任意實數(shù)x，令 表示大于或等于x的最 小整數(shù)。整數(shù) 稱為x強取整。,推論：對于正整數(shù)n，二項式系數(shù),的最大者為,二項式系數(shù),雜置：令S是n個元素的集合，S的一個雜置是S的組合的集合C，C具有性質(zhì)：C中沒有組合含于另一個組合。 例如，S=a,b,c,d，則C=a,b,b,c,d,a,d,a,c是S的一個雜置。 得到S的一個雜置的一種方法是選擇一個整數(shù)kn，然后取Ck為S的所有的k-組合。由于Ck中的每一個組合都有k個元素，因此在Ck中沒有組合能夠包含另外的組合，從而Ck是一個雜置。用這種方法構(gòu)造的雜置至多含有：,二項式系數(shù),個集合。,例如，S的2組合給出的大小為6的雜置為 C2=a,b,a,c

12、,a,d,b,c,b,d,c,d,二項式系數(shù),定理：令S是n個元素的集合，S的雜置最多包含 個集合。,S的所有2n個組合的集合可以被劃分 成部分，使得任意雜置最多含有每一個部分的一個組合。,二項式系數(shù),鏈：對于一個部分中的任意兩個組合，一個含在另一個中，具有這種性質(zhì)的組合的集合叫做鏈。 例如，對于n=1,2,3分割成鏈的劃分： n=1：1 n=2： 11,2 ; 2 n=3: 11,21,2,3; 31,3; 22,3,二項式系數(shù),通過對1,2,3所示的鏈劃分得出對1,2,3,4的組合的鏈的劃分。 劃分方法如下： 取多于一個組合的每一個鏈做成n=4的兩個鏈： 其一是通過把4添加到原鏈的最后一個組合中得到一個新的組合，再把這個新的組合添加到鏈的末尾得到； 另一個是通過把4添加到原鏈除最后一個組合外的所有組合中得到。,二項式系數(shù),11,21,2,3,11,21,2,31,2,3,4,41,41,2,4,11,21,2,3,11,21,2,31,2,3,4,41,41,2,4,二項式系數(shù),31,3,31,3