組合數(shù)學(xué) 二項(xiàng)式定理

本文格式為Word版，下載可任意編輯——組合數(shù)學(xué)二項(xiàng)式定理第五章二項(xiàng)式定理

5.1二項(xiàng)式定理定理5.1

令n是一個(gè)正整數(shù),那么對(duì)于變量x,y(可以是任意實(shí)數(shù))有:

n?n?n????(x+y)n=xn+??xn-1y+??xn-2y2+…+??yn-1+yn.

?n-1??1??2?即(x+y)n=?k?n?n?n-kk

??xy?k?證明：展開(kāi)(x+y)n=(x+y)(x+y)…(x+y),n項(xiàng)乘積，應(yīng)用乘法對(duì)加法分派率，

展開(kāi)一般項(xiàng)：xn-kyk,(若n-k次選擇x必然k次選擇y)，

?n?合并同類(lèi)項(xiàng)，k次選擇y的方法數(shù)??，k=1,2,…,n。

?k?

證明：（方法二，歸納法，自己看）

二項(xiàng)式定理的幾個(gè)其它形式:

(1)(x+y)n=?k?n?n?n-kk

??xy?n-k?(2)(x+y)n=?k?n?n?kn-k??xy?n-k??n?kn-k??xy?k??n?k??x?k?(3)(x+y)n=?k?n(4)(1+x)n=?k?n

5.2Pascal公式

楊輝三角（看書(shū)），總結(jié)，公式化，就是Pascal公式定理5.2

對(duì)于滿(mǎn)足1?k?n-1的所有整數(shù)k和n,有

?n??n-1??n-1??+????=??k??k??k-1?證明：（組合分析法）

令S是n元素集合，x是S的任一元素，那么S的k組合的集合X可以分兩部分：A：不包含x的k組合；B：包含x的k組合；

?n??n-1??n-1?|X|=|A|+|B|；|X|=??，|A|＝??，|B|＝??。

?k??k-1??k?

證明組合恒等式的3種常用方法：（1）代數(shù)法（2）數(shù)學(xué)歸納法（3）組合分析法

5.3一些有用的恒等式

(1)

?n??n-1?k??=n???k??k-1?證明：（直接驗(yàn)證）

?n???＝?k?n?n?1?????

k!(n?k)!k(k?1)!(n?k)!k?k?1?n!n(n?1)!(2)

?n??n??n?n??+??+…+??=2?0??1??n?證明：二項(xiàng)式定理，令x=y=1。

(3)

n?n??n??n??n?????-??+??+…+(-1)k??+…+(-1)n??=0?0??1??2??k??n?證明：上式，令x=1，y=－1。

n??n??n????－??+…+（－1）n??=0?0??1??n?

?n??n??n???+??+…+??+…=2n-1?0??2??k??n??n??n???+??+…+??+…=2n-1?1??3??k?

(4)

?n??n??n?n-1

1??+2??+…+n??=n2?1??2??n?證明：由恒等式（1）

?n??n-1?1×??=n??

?1??0??n??n-1?2×??=n??

?2??1?、、、

相加：1

?n????1?+2

?n????2?+…+n

?n????n?＝

?n-1??n-1??n-1?n(??+??+…+??)=n2n-1

?0??1??n-1?

(5)

n(n+1)2n-2=?k?nn??k2???k?(n?1)

n??n?n???證明：(1+x)n=??+??x+…+??xn.

?0??1??n?n??n?n???兩邊微分：n(1+x)n-1=??+2??x+…+n??xn-1.

?1??2??n?n??n?n???兩邊乘x：nx(1+x)n-1=??x+2??x2+…+n??xn.

?1??2??n?兩邊微分：

??f(x)?g(x)?g(x)?f(x)公式：（f(x)g(x)）

(nx(1?x))??n(1?x)n?122n?1?n(n?1)(1?x)n?1n?2?

?n??n??n????2x???...?n??x?1??2??n?

令x=1，得n(n+1)2n-2=?k?nn??k2???k?

類(lèi)似可求:?k?nn??kp??，p為任意正整數(shù)。?k?

(6)?k?n?n?2?2n????=??k??n??A?B，|S|=2n,|A|=n,|B|=n,

證明：（組合分析法）令S為2n個(gè)元素的集合，SS的任一n組合，含有A中的k個(gè)元素，B中的n-k個(gè)元素，k=1,2,…,n,

?2n?????n?

?n??n????????k??n-k?nk?1?n?????k?nk?12

(7)

?n??r??n??n-k?????=????

?r??k??k??r-k?證明：左邊相當(dāng)于從n元素集合中先取r個(gè)元素，再?gòu)娜〕龅倪@個(gè)r元素集合中取k個(gè)元素的組合計(jì)數(shù)；

另一種計(jì)數(shù)法：

直接從n元素集合中取k個(gè)元素，與第一種方法的區(qū)別是少計(jì)算了一些重復(fù)的k元素組合，如：n=7,r=5,k=3狀況

{a,b,c,d,e,f}?{a,b,c,d,e}{a,b,c,d,f}{a,b,c,e,f}、、、?{a,b,c},{a,b,c}、、、

?n-k?直接取出的k元素集合，少計(jì)數(shù)了??倍。得證。

?r-k?定義1:

?n?令r可取任意實(shí)數(shù),k可取任意整數(shù),定義??的擴(kuò)展為:

?k??r(r-1)...(r-k?1)若k?1?k!?r????=?1若k?0?k??0若k??1??

?r?易證擴(kuò)展定義??仍使Pascal公式成立:

?k??r??r-1??r-1??+????=??k??k??k-1?

?r??r?1??r?k??r?k?1?(8)??+??=???+…+??0??1?k??k??

?r?k?1??r?k??r?k?證明：??＝??＋??

?k??k??k-1??r?k??r?k-1??r?k-1???＝??＋???k-1??k-1??k-2?、、、

?r?2??r?1??r?1??r?1??r??＋??＝??＋????＝??1??1??0??1??0?

??0??+??1??+…+??n-1??+??n??=??n?1(9)??

?k??k??k??k??k?1?證明：

??n?1??1?＝??n?????n???k??k?1??k???n??n-1??n-1k?1???????????k?1??k?、、、

??2?????1?????1???k?1??k?1??k???1?????0?1????0??＝??0???k?1??k???k??k?

4.3非降路徑問(wèn)題（一）非降路徑問(wèn)題

設(shè)平面上兩點(diǎn)（0，0）和（m，n），由（0，0）開(kāi)始，一次只能

向上走一步，或向右走一步，最終到（m，n）的一條路徑。稱(chēng)非降路徑。

水平方向向右移動(dòng)一步，這樣的操作稱(chēng)x；垂直方向向上移動(dòng)一步，這樣的操作稱(chēng)y。顯然，無(wú)論如何移動(dòng)，到達(dá)（m，n）點(diǎn)確定含m個(gè)x和n個(gè)y，那么（0，0）到（m，n）點(diǎn)的非降路徑問(wèn)題就定義為m個(gè)x和n個(gè)y的一個(gè)排列。

問(wèn)題：（0，0）到（m，n）點(diǎn)的非降路徑數(shù)有多少個(gè)？

證明組合恒等式：

?m?n??m?n-1??m?n-1????（1）???=???＋???

?n??n??n-1??m?n?(m?n)!?m?n??m?n?????=???=??=???n!m!?mn??m??n?證明：

（0，0）到（m,n）的非降路徑，等價(jià)于（0，0）到（m-1,n）的非降路徑，（0，0）到（m,n-1）的非降路徑，之和。

?m??n??m??n??m??n??m?n?（2）??????????+???????+...+????????=???

?0??r??1??r-1??r??0??r?m,n,r,正整數(shù)，r?m,n

證明：

?m?n???（0，0）到（m+n-r,r）的非降路徑數(shù)，（0，0）到（m+n-r,r）??表示?r?的任一非降路徑必經(jīng)過(guò)線段（m,0）,（m-r,r）上的某一點(diǎn)，即（m-k,k）,k=0,1,2,…,r。

?m??n?（0，0）到（m,0）；（m,0）到（m+n-r,r）非降路徑數(shù)：????????；

?0??r?注：（m,0）到（m+n-r,r）等價(jià)與（0，0）到（n-r,r）

?m??n???（0，0）到（m－1,1）（m－1,1）；到（m+n-r,r）非降路徑數(shù)：??????；?1??r-1?、、、例

在世乒賽某場(chǎng)比賽的一局中，中國(guó)選手以11：7獲勝，在比賽

過(guò)程中未出現(xiàn)5：5及6：6的比分，求有多少種可能表示比賽過(guò)程的比分記錄？

解：

?10?7?（0，0）到（10,7）非降路徑數(shù)：????；

?7??5?5??5?2?（0，0）到（5,5），（5，5）到（10,7）非降路徑數(shù)：????????；

?5??2??6?6??4?1???（0，0）到（6,6），（6，6）到（10,7）非降路徑數(shù)：??????；?6??1?（0，0）到（5,5），（5，5）到（6，6）,（6，6）到（10,7）非降路

?5?徑數(shù)：???55??1?1??4?1???????????；??1??1?

?10?7??總的：???7???5????5?5?－???55??5?2???????2????6?6??4?1???－??????61????＋

5??1?1??4?1???????????。??1??1?

例求從（0，0）和（n，n）點(diǎn)的除端點(diǎn)外不接觸直線y=x的非降路徑數(shù)。

設(shè)非降路徑最終離開(kāi)對(duì)角線的點(diǎn)是A，先分析對(duì)角線下方，等價(jià)于（1，0）到（n，n-1）的非降路徑。

?2n-2?（1，0）到（n，n-1）的非降路徑數(shù)：????

?n-1?再減去（1，0）到（n，n-1）的接觸或穿過(guò)對(duì)角線的非降路徑數(shù)：

?2n-2?（0，1）到（n，n-1）的非降路徑數(shù)：????

?n-2??2n-2??2n-2???總的：2×（???－???）

?n-1??n-2?

思考題：求從（0，0）和（n，n）點(diǎn)的除端點(diǎn)外不穿過(guò)直線y=x的非降路徑數(shù)。（等價(jià)于（0，0）和（n＋1，n＋1）不接觸直線y=x

?2n的非降路徑數(shù)，2×（???n??2n???）??）?－???n-1?

5.4二項(xiàng)式系數(shù)的單峰性定義1:

設(shè)序列s0,s1,s2,…,sn,若存在一個(gè)整數(shù)t,0?t?n,使得:

s0?s1?s2?…?st,st?st+1?st+2?…?sn那么,稱(chēng)序列是單峰的.

定理5.4.1

令n為正整數(shù),二項(xiàng)式系數(shù)序列是單峰序列,確切地說(shuō),

若n是偶數(shù):

?n??n??n??n?????…>??.

???0??1??n??2?若n是奇數(shù):

??n??n?n??n??n???????…>??.

?????0??1??n??2??2?證明：（初等方法）

?n?????kn?k?1???令Q＝，顯然，

k?n??????k?1?Q>1，序列遞增，2k?n?1；Q＝1，極值點(diǎn)，2k?n?1；Q…>??

??01???????n??2?n是奇數(shù)時(shí)：k?減，即：

n?12是遞增，k?n?1n?1n?1,極值點(diǎn)，k?遞222??n??n?n??n??n???????…>??.

?????0??1??n??2??2?定義2:

設(shè)x為任意實(shí)數(shù),令

?x?表示大于或等于x的最小整數(shù),稱(chēng)強(qiáng)取整(上取整);?x?表示小于或等于x的最大整數(shù)