二項式定理學習筆記(詳解)
二項式定理好難啊...學了好久\(QWQ\)
這篇部落格寫的有點雜,主要講證明,僅供娛樂?
二項式定理的常見形式
首先我們看看這個常見的令人頭疼的式子:
\[(x+1)^n=\sum_{i=0}^{n} C(n,i) ~ x^i\]
這個式子為什麼是對的呢?
我們考慮將左邊的式子寫成完全形式:
\[(x+1)(x+1)···(x+1)\]
那麼我們發現其實可以每次從這\(n\) 個\((x+1)\) 中選出一個\(x\) 或者一個\(1\) ,然後將 n 個選出來的數字相乘累加進\(ANS\)
那麼我們考慮從\(n\) 個\[(x+1)\] 中選出\(i\) 個\(x\) 的情況有多少種呢
這其實就是組合數 中的\(C(n,i)\) ,於是乎我們發現原來的式子是正確的
然後講講二項式定理的一個應用:
我們考慮從\(n\) 個物品中選出選出\(t\) 個物品,那麼有多少種選擇的方案呢?
既然是二項式定理的應用,那麼怎麼才能將二項式定理套進去呢?
先別多想,我們考慮用\((x^0+x^1)\) 表示某樣物品選或者不選(這裡\(0\) 次項就是不選,而\(1\) 次項則是選),這兩者相互獨立
那麼我們可以根據所有物品兩兩獨立 將它們的選擇方案乘起來,就是\((x^0+x^1)^n\)
考慮為什麼可以這麼乘?不用想那麼多感性理解即可,不理解的話看到下面也能懂的
那麼我們考慮一下之前的問題:選出\(t\) 個物品
那麼這裡我們將\(n\) 個\((x^0+x^1)\) 相乘之後\(x^t\) 的係數其實就是方案數了,因為在這裡\(x^t\) 只可能來自\(t\) 個不同的\((x^0+x^1)\) 中的\(x^1\) , 也就是說它的含義就是我們在\(n\) 個\((x^0+x^1)\) 中選擇\(t\) 個\(x^1\) 然後每次選出一種方案就令\(x^t\) 前的係數加一
然後我們把\(x^0\) 等價成\(1\) ,也就是二項式定理的常見形式了
小插曲
我們定義組合數\(C(n,m)\) 為\(\frac{n(n-1)(n-2)···(n-m+1)}{m!}\) ,這樣定義對於下面的證明更有幫助
然後我們再考慮將原式的 求和函式的 終止條件換一下:
\[(x+1)^n=\sum_{i=0}^{\infty} C(n,i) x^i \]
這時候我們可以知道這個式子和之前是等價的,因為\(i\) 大於\(n\) 的時候\(C(n,i)\) 是等於\(0\) 的
至於為什麼要這樣表示看到下面你就知道了
指數為負的二項式定理
然後我們考慮一下\((x+1)\) 的指數推廣到負數 的情況
這個時候其實也有:
\[(x+1)^{-n}=\sum_{i=0}^{\infty} C(-n,i) ~ x^i=\sum_{i=0}^{\infty} (-1)^i~C(n+i-1,i)~x^i\]
這時候你可能會非常的驚訝... 組合數還能有負的?!
遺憾的告訴你(什麼鬼),組合數可以有負的,因為這裡的組合數使按之前小插曲裡面的定義來的
那麼我們考慮怎樣轉移到最右邊的式子:
\[C(-n,m)=\frac{(-n)(-n-1)(-n-2)···(-n-m+1)}{m!}\]
然後我們吧上面的式子裡面所有項取反,也就是將他們的符號提取出來,就成了:
\[C(-n,m)=(-1)^{(-n)-(-n-m+1)+1}\frac{n(n+1)(n+2)···(n+m-1)}{m!}\]
\[ = (-1)^{m}\frac{n(n+1)(n+2)···(n+m-1)}{m!}\]
\[ = (-1)^{m} C(n+m-1,m)\]
就是這樣(或許你已經看到過上面的式子了)
把上面的式子再寫一遍就是:\((x+1)^{-n}=\sum_{i=0}^{\infty}(-1)^i C_{n+i-1}^i~x^i\)
當加號變為減號
(在這裡我們略去 n 為負數的情況)
首先的話,我們考慮將上面式子中的\(x\) 取負,那麼原式就變成了:
\[(-x+1)^n=\sum_{i=0}^{\infty} (-1)^i~ C(n,i)~x^i\]
這樣寫不好看,換種寫法
\[(1-x)^n=\sum_{i=0}^{\infty} (-1)^i~ C(n,i)~x^i\]
這個式子...(相信大家可能看到過的吧)
這裡的話後面的式子其實就是把\(x\) 的負號提了出來,沒什麼特別的
但是你有沒有感覺這個式子有點眼熟?
沒錯啊,這和指數為負的二項式定理 中長得有點像的,組合數前面都帶著個正負號
於是我們考慮一下吧這裡的 n 也取負呢?
那麼原式就變成了:
\[(1-x)^{-n} =\sum_{i=0}^{\infty} C(n+i-1,i)~x^i\]
也就是說兩個正負號抵消掉了...\(QWQ\)
這個式子其實是非常有用的,它會在你學生成函式的時候派上大用場
(至於生成函式嘛,登博主學完之後還有時間的話可能就會寫篇部落格介紹一下)
二項式定理的一般形式
其實上面講了這麼多都是二項式定理的特殊形式(但其實都是比較常見+實用的)
於是下面說說它的一般形式:
\[(x+y)^n=\sum_{i=0}^{n} C(n,i) a^i·b^{n-i}\]
這個東西可以理解為有 n 堆物品,每堆裡面有 x 和 y ,每堆只能選一個,要求選擇的所有方案之和
具體證明就毋須多言了,上面已經證了一大堆了
關於廣義二項式定理
其實廣義二項式定理就是上面的那個式子,我們只要將指數 n 的定義域改成實數就好了
也就是說,廣義二項式定理對於實數也成立,也就是:
\[(x+y)^α=\sum_{i=0}^{α} C(α,i) a^i·b^{α-i}\]
而關於\(C(α,i)\) 的值通過小插曲中組合數的定義代就好了
論二項式定理與組合數的關♂
系
我們看到上面的二項式定理中都出現了組合數,那麼他們兩者之間有什麼內在聯絡呢?或者說我們可以通過二項式定理得出組合數的一些性質麼?
答案當然是肯定的啦!
第一種情況
我們考慮吧二項式定理的公式中的\(x\) \(y\) 都變成\(1\) ,那麼我們會發現下面這個式子:
\[(1+1)^n=\sum_{i=0}^{n} C_{n}^{i}\]
這能說明什麼呢?很明顯啊!
我們考慮前面其實就是 2 的 n 次冪,後面就是 n 個物品裡面選出 1~n 個的方案數之和,那麼由二項式定理可以得知他們兩者是相等的
從另一個角度出發, n 個物品裡面任意選擇的方案數等於\(\sum_{i=0}^nC_{n}^i\) ,同時也等於\(2^n\)
前面的式子不需要多解釋,考慮後面的式子就是每個物品有選或者不選兩個選擇,那麼總方案數等於所有物品選擇的方案數 的乘積,這樣一來兩者的相等關係也就非常明顯了
那麼我們再考慮一下楊輝三角,楊輝三角的第 i 行 第 j 列對應著\(C_i^j\)
上面的相等關係也就說明了楊輝三角的第 i 行所有數之和等於\(2^i\)
第二種情況
我們再考慮把 x 變成 1, y 變成 0,這兩者會產生什麼樣的反應呢?我們看下面的式子:
\[(1-1)^n=\sum_{i=0}^{n} (-1)^i~C_{n}^{i}\]
(注意,不要認為等式左邊恆等於 0 ! 我們預設\(x^0\) 為 1 ,對於任意實數! 同時這裡也可以倒過來證明 0 的 0 次冪為 1,算是吧?)
那麼我們發現除去\(n = 0\) 的情況, \(C_n^i\) 的偶數項之和 減去 \(C_n^i\) 的奇數項之和 等於 0 !
換句話說, \(C_n^i\) 的偶數項之和 等於 \(C_n^i\) 的奇數項之和 !
這裡不知道如何解釋了,只能說對於 n 為奇數的情況考慮組合數的對稱性(即\(C_n^i=C_n^{n-i}\) )
然後對於 n 為偶數的情況考慮 掐頭去尾,每個偶數項都對應上一行的兩個相鄰元素之和,不相交併且取遍了上一行的所有元素,而奇數項同理,於是兩者相等
那麼這裡上一張圖你肯定就懂了(自己感受一下)
考慮一下楊輝三角,也就是說楊輝三角每一行的偶數列對應的項之和 等於奇數列對應的項之和 (由上圖也可以看出來)
但是別忘了考慮特殊情況,我們剛剛說過\(n=0\) 除外
但其實考慮 n=0 的情況也簡單,就是當\(n=0\) 時組合數只有一項且為 1 ,然後我們把原來的式子倒過來表達:
\[\sum_{i=0}^{n} (-1)^i~C_{n}^{i}=[n==0]=\epsilon(n)\]
其實\(\epsilon\) 就是單位元函式
總結
二項式定理很有趣,但是看著上面的內容貌似沒什麼用,但等你學到深處就會發現經常會看到它的身影,到那時別忘了再翻開這篇部落格,或許你會有新的收穫~
Bye~Bye~