现代工程数学第5章二项式系数

1、第 5 章 二项式系数,5.1 Pascal 公式 5.2 二项式定理 5.3 一些恒等式 5.4 二项式系数的单峰性 5.5 多项式定理 5.6 牛顿二项式定理 5.7 再论偏序集 作业,5.1 Pascal公式,定理5.1.1（ Pascal公式）若1 k n 1，则 证法1,证法2 设 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 设

2、n 是正整数，则 证法1 取 k 个 y，n k 个 x 相乘得出 xnk y k。,5.3 一些恒等式,奇组合与偶组合各半,O=k | 0 k n , k是奇数， E=k | 0 k n , k是偶数,证法2 设 S = a1, a2, an。考虑 S 的偶组合， a1 有两种选择， a1 选定后， a2 有两种选择， a1, a2, an1 都选定后， an 只有一种选择，若已选了偶数个元素，则不选 an ，否则选 an 。所以， S 的偶组合共有 2n1 个。 S 的奇组合数目为 2n 2n1 = 2n1,证法3 设 S = a1, a2, an。在 S 的奇组合集合与 S 的偶组合集合

3、之间建立一一对应 f 。任取 S 的奇组合 A，令,组合数定义域的扩充,多项式等式的证明法,若次数 n 的多项式 f (x)和 g(x) 在多于 n 个点的值相等，则它们是相同的多项式。 因为次数 n 的多项式 f (x) g(x) 有多于 n 个根，所以是零多项式 0。,若 k 为非负整数，当 r 为非负整数时等式成立，所以 r 为任意实数时等式成立。 若 k 为负整数，等式两边均为 0。,若 k n，等式两边均为 0。所以，当 k 和 n 为任意非负整数时，等式成立。,证明组合恒等式的方法,用组合数公式直接验证。 用数学归纳法。 分析恒等式的组合意义。 利用二项式定理，对公式进行微分或者积

4、分运算。 利用二项式定理，比较多项式的系数。,5.4 二项式系数的单峰性,若 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 不是单峰的。,证明 设 1 k n,设 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 的杂置。 设 S 是 n 元集。对于每个 k n ， S

5、 的所有 k 组合组成的集合是 S 的杂置。在这样的杂置中，当时所包含的组合最多，有个。这是包含的组合最多的 S 的杂置。,设 A 是由 S = 1, 2, , n 的组合组成的集合。若对于 A 中任何两个组合 X 和 Y，X Y 或 Y X ，则称 A 为链。设 A 是链且 C 是杂置。若 A 和 C 有两个不同公共元素 a 和 b，则 a, bA 且 a, bC，因而 ( a b 或 b a )且 a b 且 b a ，矛盾。因此， A 和 C 至多有一个公共元素 。设 C 是杂置。若有一个链划分包含 m 个链，则因为 C 中的两个组合不能在同一个链中，所以 C 中组合的个数至多是 m。,

6、定理5.4.3（Sperner 定理）设 S 是 n 元集。则 S 的杂置最多包含个组合。 证明 设 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 这些链划分有以下两个性质： 链中每个组合比它前面的组合多一个元素。 链中第一个组合与最后一个组合的元素个数之和是 n 。 称这样的链划分为对称的链划分。,设 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 。,设 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) 的对称的链划分的每个链中 存在唯一 -组合，共有 个 -组合，所 以在对称的链划分中有 个链。每个杂置中 的组合个数至多是 。,5.5 多项式定理,5.6 牛顿二项式定理,在牛顿二项式定理中，令 x = z，y =1，得,牛顿二项式定理的应用,5.7 再论偏序集,设 (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、是链。,例 设 X = 1, 2, 10，考虑偏序集 (X, | )，其中 |是整除关系。4, 6, 7, 9, 10是反链，1 | 2 | 4 | 8 是链。,设 (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 都不成立。 若有元素个数为 r 的链 C，则由于 C 中没有两个元 素属于同一反链，所以 X 不能划分为少于 r 个反 链。 若有元素个数为 s 的反链 A，则由于 A 中没有两个 元素

10、属于同一链，所以 X 不能划分为少于 s 个链。,定理5.7.1 设 (X, ) 是有限偏序集，r 是元素最多链的元素个数。则可将 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 构成链 a1 a2 ap 因为 r 是元素最多链的元素个数，所以 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、设 (X, ) 是有限偏序 集，m 是元素最多反链的元素个数。则可将 X 划 分为 m 个链，但不能划分为少于 m 个链。 证明 只需证明可将 X 划分为 m 个链。 对 X 的元素个数归纳证明。 若 | X | = 1，则 m = 1，结论显然成立。 设 | X | 1 。考虑两种情况： 存在 m 个元素的反链 A，它不是 X 的所有极大元的集合，也不是 X 的所有极小元的集合，即存在不属于 A 的极大元，也存在不属于 A 的极小元。,令 A+ = x : xX 且存在 aA 使得 a x A = x : xX 且存在 aA 使得 x a 显然，A A+，A A 。下述性质成立： | A+

13、| | X |。设极小元 xA。若 xA+，则存在 aA 使得 a x，由 x 是极小元得出 a = x 。因而 xA ，与 xA 矛盾。因此， xA+ 。 | A | | X |。设极大元 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 | ，由归纳假设知： 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 的极小元集合才是有