二项式系数54.pptVIP

產生組合 對一個有限的集合，該如何產生出所有的組合方式？ 由於組合可視為一個子集合，我們能用{a1, a2, …, an}之子集合與長度為n之位元字串間的對應關係來說明。 回顧此對應關係，當對應之位元字串的第k個位置等於1時，表示元素ak在此組合中；而位元字串的第k個位置等於0時，表示元素ak不在此組合中。同時，我們也知道一個長度為n的位元字串對應於一個介於0到2n ? 1的整數之二進位表示法。 為產生所有n位二進位數字，由n個0的表示法00…00開始，持續找出下一個二進位表示法，直至得到n個1的表示法111…11為止。產生下一個二進位表示法的過程如下：在每個步驟中，從最右邊找出第一個不是1的位置，將這個位置的位元換成1，然後將其右邊的所有位元全部換成0，就能得到下一個較大的二進位表示法。 * 例：在{a1, a2, …, a6}中，對應於子集合{a2, a5, a6}的位元字串為010011。 例：找出10 0010 0111的下一個位元字串。 解：從右邊數來第一個不為1的位元在第4位。將其換為1，將其右邊的所有位元全部換成0，就能得到下一個較大的二進位表示法10 0010 1000。 * 產生r-組合的方法 給定一個產生集合{1, 2, 3, …, n}之r-組合的演算法。每一個r-組合都對應一個長度為r之遞增數列。 a1a2…ar依字典順序之下一個較大數列可依下面程序而得： 首先找出最後一個ai的位置，其中 ai ? n ? r + i。然後，以ai + 1替換ai，當j = i + 1, i + 2, …, r時，以ai + j ? i + 1替換aj。如此一來便能得到下一個較大之r-組合。 * 例：在集合{1, 2, 3, 4, 5, 6}中，找出{1, 2, 5, 6}的下一個4-組合。 解：已知n = 6，r = 4，a1 = 1，a2 = 2，a3 = 5和 a4 = 6。滿足ai ? n ? r + i(= 6 ? 4 + i = 2 + i)的最後一個ai，是a2 = 2。以3替換a2 (= 2)，而 a3 = ai + j ? i + 1 = 2 + 3 ? 2 + 1 = 4， a4 = 2 + 4 ? 2 +1 = 5。 得到下一個較大的4-組合為{1, 3, 4, 5}。 利用這種方式，由{1, 2, 3, 4}開始，我們便可以找出所有的4-組合。 * 2009/11 二項式係數(§5.4) 在n個元素的集合中選出r-組合的方法數為 。 這個數也稱作二項式係數(binomial coefficient)，因為這些數將出現在二項展開式，如(a + b)n的係數中。 * 二項式定理(The Binomial Theorem) 令x和y為變數，而n為非負整數，則 證明：將使用組合證明方式。當j = 0, 1, 2, …, n，xn?jyj項的係數可以由相乘的n項(x + y)中，選取(n?j)項的x和j項的y來相乘而得，所以其係數應可 視為在n元素集合中(n?j)-組合的個數，即 ，得證。 * 例:求出(x + y)4的展開式。 解:根據二項式定理 * 例:求出(x + y)25展開式中x12y13的係數。 解:根據二項式定理，係數為 * 例:求出(2x ? 3y)25展開式中x12y13的係數。 解:由於(2x ? 3y)25相當於(2x + (?3y))25，根據二項式定理 所以，x12y13的係數是當j = 13時， * 系理:令n為非負整數。則 證明:利用二項式定理當x = 1，y = 1時， ，得證。 * 系理:令n為正整數。則 證明:利用二項式定理當x = 1，y = ?1時， 注意:此系理可推導出 * 系理:令n為非負整數。則 證明:利用二項式定理當x = 1，y = 2時， * 帕斯卡等式與三角形 帕斯卡等式(Pascal’s Identity) 令n ? k為正整數，則  證明:假設T為包含n +1個元素的集合，而a ?T，S = T?{a}。 我們注意到T有 個包含k個元素的不同子集合。 這類的子集合能分成兩類：一種是包含元素a與k?1個S中的元素；另一種是不包含a，而包含k個S中的元素。 由於包含k? 1個S中的元素之子集合個數為 ， 而包含k個S中的元素之子集合個數為 。 所以，我們有 * 帕斯卡三角形(Pascal’s triangle) 此三角形之第n列包含 二項式係數 C(n, k)。 帕斯卡等式 * 二項式係數的等式 凡德蒙德等式(Vandermonde’s Identity) 令m、n和r為非負整數，而且r不