現(xiàn)代工程數(shù)學(xué)第5章二項式系數(shù)

1、第 5 章 二項式系數(shù),5.1 Pascal 公式 5.2 二項式定理 5.3 一些恒等式 5.4 二項式系數(shù)的單峰性 5.5 多項式定理 5.6 牛頓二項式定理 5.7 再論偏序集 作業(yè),5.1 Pascal公式,定理5.1.1（ Pascal公式）若1 k n 1，則 證法1,證法2 設(shè) S = a1, a2, an。S 的 k-組合由兩部分組成。 不包含 an 的 k-組合，即a1, a2, an1的 k-組合，有 個。 包含 an 的 k-組合，由a1, a2, an1的 k1-組合增加 an 得到，有 個。 所以，,Pascal（楊輝）三角形,5.2 二項式定理,定理5.2.1 設(shè)

2、n 是正整數(shù)，則 證法1 取 k 個 y，n k 個 x 相乘得出 xnk y k。,5.3 一些恒等式,奇組合與偶組合各半,O=k | 0 k n , k是奇數(shù)， E=k | 0 k n , k是偶數(shù),證法2 設(shè) S = a1, a2, an?？紤] S 的偶組合， a1 有兩種選擇， a1 選定后， a2 有兩種選擇， a1, a2, an1 都選定后， an 只有一種選擇，若已選了偶數(shù)個元素，則不選 an ，否則選 an 。所以， S 的偶組合共有 2n1 個。 S 的奇組合數(shù)目為 2n 2n1 = 2n1,證法3 設(shè) S = a1, a2, an。在 S 的奇組合集合與 S 的偶組合集合

3、之間建立一一對應(yīng) f 。任取 S 的奇組合 A，令,組合數(shù)定義域的擴充,多項式等式的證明法,若次數(shù) n 的多項式 f (x)和 g(x) 在多于 n 個點的值相等，則它們是相同的多項式。 因為次數(shù) n 的多項式 f (x) g(x) 有多于 n 個根，所以是零多項式 0。,若 k 為非負(fù)整數(shù)，當(dāng) r 為非負(fù)整數(shù)時等式成立，所以 r 為任意實數(shù)時等式成立。 若 k 為負(fù)整數(shù)，等式兩邊均為 0。,若 k n，等式兩邊均為 0。所以，當(dāng) k 和 n 為任意非負(fù)整數(shù)時，等式成立。,證明組合恒等式的方法,用組合數(shù)公式直接驗證。 用數(shù)學(xué)歸納法。 分析恒等式的組合意義。 利用二項式定理，對公式進行微分或者積

4、分運算。 利用二項式定理，比較多項式的系數(shù)。,5.4 二項式系數(shù)的單峰性,若 s0 s1 st st+1 sn ，則稱 s0, s1,sn 是單峰的。 例如，1, 1；1, 2, 1；1, 3, 3, 1 ；1, 4, 6, 4, 1 都是單峰的。 1, 2, 1, 2, 1 不是單峰的。,證明 設(shè) 1 k n,設(shè) C 是由集合 S 的組合組成的集合。若對于 C 中任何兩個不同組合 X 和 Y， X Y 且 Y X ，則稱 C 為 S 的雜置。例如， C =a, b, b, c, d,a, d, a, c 是 S =a, b, c, d 的雜置。 設(shè) S 是 n 元集。對于每個 k n ， S

5、 的所有 k 組合組成的集合是 S 的雜置。在這樣的雜置中，當(dāng)時所包含的組合最多，有個。這是包含的組合最多的 S 的雜置。,設(shè) A 是由 S = 1, 2, , n 的組合組成的集合。若對于 A 中任何兩個組合 X 和 Y，X Y 或 Y X ，則稱 A 為鏈。設(shè) A 是鏈且 C 是雜置。若 A 和 C 有兩個不同公共元素 a 和 b，則 a, bA 且 a, bC，因而 ( a b 或 b a )且 a b 且 b a ，矛盾。因此， A 和 C 至多有一個公共元素 。設(shè) C 是雜置。若有一個鏈劃分包含 m 個鏈，則因為 C 中的兩個組合不能在同一個鏈中，所以 C 中組合的個數(shù)至多是 m。,

6、定理5.4.3（Sperner 定理）設(shè) S 是 n 元集。則 S 的雜置最多包含個組合。 證明 設(shè) S = 1, 2, , n。歸納證明： S 的所有 2n 個組合的集合 P(S) 可以被劃分為個鏈。,n = 1： 1 n = 2： 1 1, 2 2 n = 3： 1 1, 2 1, 2, 3 3 1, 3 2 2, 3 這些鏈劃分有以下兩個性質(zhì)： 鏈中每個組合比它前面的組合多一個元素。 鏈中第一個組合與最后一個組合的元素個數(shù)之和是 n 。 稱這樣的鏈劃分為對稱的鏈劃分。,設(shè) n 2，對于P(1, 2, , n 1)的對稱的鏈劃分的每個鏈 A1 A2 Ak 得到鏈 A1 A2 Ak Ak n

7、 因為 | A1 | + | Ak | = n 1，所以 | A1 | + | Ak n| = n 若 k 1，則還得到鏈 A1 n A2 n Ak1 n 因為 | A1 | + | Ak | = n 1， | A1 | + | Ak1 | = n 2， 所以 | A1 n | + | Ak1 n | = n 。,設(shè) A1 A2 Ak 是 P(1, 2, , n) 的對稱的鏈劃分中的鏈，則 | A1 | + | Ak | = n 且 | A1 | | Ak |。若 k = 1，則 | A1 | 若 k 1，則 | A1 | 且 | Ak | ， A1 , A2 , , Ak 中存在唯一 組合。

8、,因為在 P(1, 2, , n) 的對稱的鏈劃分的每個鏈中 存在唯一 -組合，共有 個 -組合，所 以在對稱的鏈劃分中有 個鏈。每個雜置中 的組合個數(shù)至多是 。,5.5 多項式定理,5.6 牛頓二項式定理,在牛頓二項式定理中，令 x = z，y =1，得,牛頓二項式定理的應(yīng)用,5.7 再論偏序集,設(shè) (X, ) 是有限偏序集。若 A X 且對于 A 中任意兩個不同元素 a 和 b， a b 和 b a 都不成立，則稱 A 為反鏈。若 C X 且對于 C 中任意兩個元素 a 和 b， a b 或 b a，則稱 C 為鏈。 我們常將鏈表示為 x1 x2 xt 顯然，反鏈的子集仍是反鏈，鏈的子集仍

9、是鏈。,例 設(shè) X = 1, 2, 10，考慮偏序集 (X, | )，其中 |是整除關(guān)系。4, 6, 7, 9, 10是反鏈，1 | 2 | 4 | 8 是鏈。,設(shè) (X, ) 是有限偏序集。 若 A 是反鏈且 C 是鏈，則 | A C | 1。 若 a b 且 a , b A C ，則 a , bA 且 a , bC 。 若 a , bC，則 a b 或 b a 。 若 a , bA，則 a b 和 b a 都不成立。 若有元素個數(shù)為 r 的鏈 C，則由于 C 中沒有兩個元 素屬于同一反鏈，所以 X 不能劃分為少于 r 個反 鏈。 若有元素個數(shù)為 s 的反鏈 A，則由于 A 中沒有兩個 元素

10、屬于同一鏈，所以 X 不能劃分為少于 s 個鏈。,定理5.7.1 設(shè) (X, ) 是有限偏序集，r 是元素最多鏈的元素個數(shù)。則可將 X 劃分為 r 個反鏈，但不能劃分為少于 r 個反鏈。 證明 只需證明可將 X 劃分為 r 個反鏈。 令 X1 = X，A1 是 X1 的極小元的集合。 令 X2 = X1 A1，A2 是 X2 的極小元的集合。 令 Xp = Xp1 Ap1，Ap 是 Xp 的極小元的集合。 Xp +1 = Xp Ap = ，其中 X1, X2 , , Xp 不是空集。 A1, A2 , , Ap 是將 X 分成反鏈的劃分。,任取 ap Ap，因為 ap 不是 Xp1 的極小元，

11、所以必有 Xp1 的極小元 ap1使得 ap1 ap ，由 Ap1 是 Xp1 的極小元的集合知道， ap1 Ap1 。 存在 a1A1, a2A2 , , apAp 構(gòu)成鏈 a1 a2 ap 因為 r 是元素最多鏈的元素個數(shù)，所以 p r。 由于 X 被劃分成了p 個反鏈 A1, A2 , , Ap ，所以， r p 。因此， p = r 。,例如，偏序集 (X, | ) 的哈斯圖如下。r = 4。 A1 = 1， A2 = 2, 3, 5, 7， A3 = 4, 6, 9, 10， A4 = 8。 包含 4 個元素的鏈 1 | 2 | 4 | 8,定理5.7.2（Dilworth 定理）

12、設(shè) (X, ) 是有限偏序 集，m 是元素最多反鏈的元素個數(shù)。則可將 X 劃 分為 m 個鏈，但不能劃分為少于 m 個鏈。 證明 只需證明可將 X 劃分為 m 個鏈。 對 X 的元素個數(shù)歸納證明。 若 | X | = 1，則 m = 1，結(jié)論顯然成立。 設(shè) | X | 1 ?？紤]兩種情況： 存在 m 個元素的反鏈 A，它不是 X 的所有極大元的集合，也不是 X 的所有極小元的集合，即存在不屬于 A 的極大元，也存在不屬于 A 的極小元。,令 A+ = x : xX 且存在 aA 使得 a x A = x : xX 且存在 aA 使得 x a 顯然，A A+，A A 。下述性質(zhì)成立： | A+

13、| | X |。設(shè)極小元 xA。若 xA+，則存在 aA 使得 a x，由 x 是極小元得出 a = x 。因而 xA ，與 xA 矛盾。因此， xA+ 。 | A | | X |。設(shè)極大元 xA。若 xA，則存在 aA 使得 x a，由 x 是極大元得出 a = x 。因而 xA ，與 xA 矛盾。因此， xA。,A+ A = A。因為 A A+，A A ，所以 A A+ A 。若有 x A+ A 卻 xA，則有a, bA 使得 a x b ，這與 A 是反鏈矛盾。 A+ A = X。若有 X 中元素 x A+ A ，則 xA+ 且 xA ，沒有 aA 使得 a x， 也沒有 aA 使得 x

14、 a， A x 是反鏈，這與 A 是元素最多的反鏈矛盾。 因為 | A+ | | X |，| A | | X | ，由歸納假設(shè)知： A+ 可劃分成 m 個鏈 E1, , Em， A 可劃分成 m 個 鏈 F1, , Fm 。A 中元素是 A 的極大元和 A+ 的極 小元，因而是 F1, , Fm 的最后元素， E1, , Em 的 第一個元素。,把這些鏈成對“粘”在一起得到 m 個鏈，即為 X 的劃分。 例如，偏序集 (X, ) 的哈斯圖如下。元素最多的反鏈 A = 7, 5, 4, 6, 9，A+ = 7, 5, 4, 6, 9, 10, 8， A = 7, 5, 4, 6, 9, 1, 2, 3， A+ 可劃分成鏈： 7, 5 10, 4 8, 6, 9 A 可劃分成鏈： 1 7, 5, 2 4, 3 6, 9 “粘”在一起得到鏈： 1 7, 5 10, 2 4 8, 3 6, 9,若只有 X 的極大元集合和 X 的極小元集合才是有