现代工程数学第5章.ppt

第 5 章 二项式系数5.1 Pascal 公式5.2 二项式定理5.3 一些恒等式5.4 二项式系数的单峰性5.5 多项式定理5.6 牛顿二项式定理5.7 再论偏序集作业5.1 Pascal公式（Pascal公式）若1 k n 1，则证法证法1证法证法2 设 S=a1,a2,an。S 的 k-组合由两部分组成。1.不包含 an 的 k-组合，即a1,a2,an1的 k-组合，有 个。2.包含 an 的 k-组合，由a1,a2,an1的 k1-组合增加 an 得到，有 个。所以，Pascal（杨辉）三角形 kn01234011112121313314146415.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 的偶组合集合之间建立一一对应 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 为任意非负整数时，等式成立。证明组合恒等式的方法1.用组合数公式直接验证。2.用数学归纳法。3.分析恒等式的组合意义。4.利用二项式定理，对公式进行微分或者积分运算。5.利用二项式定理，比较多项式的系数。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 的所有 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。（Sperner 定理）设 S 是 n 元集。则 S 的杂置最多包含 个组合。证明证明 设 S=1,2,n。归纳证明：S 的所有 2n 个组合的集合 P(S)可以被划分为个链。n=1：1n=2：1 1,22n=3：1 1,2 1,2,33 1,3 2 2,3这些链划分有以下两个性质：1.链中每个组合比它前面的组合多一个元素。2.链中第一个组合与最后一个组合的元素个数之和是 n。称这样的链划分为对称的链划分。设 n 2，对于P(1,2,n 1)的对称的链划分的每个链A1 A2 Ak得到链A1 A2 Ak Ak n因为|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 中存在唯一 组合。因为在 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显然，反链的子集仍是反链，链的子集仍是链。例例 设 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。1.若 a,bC，则 a b 或 b a。2.若 a,bA，则 a b 和 b a 都不成立。若有元素个数为 r 的链 C，则由于 C 中没有两个元素属于同一反链，所以 X 不能划分为少于 r 个反链。若有元素个数为 s 的反链 A，则由于 A 中没有两个元素属于同一链，所以 X 不能划分为少于 s 个链。设(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 的极小元，所以必有 Xp1 的极小元 ap1使得 ap1 ap，由 Ap1 是 Xp1 的极小元的集合知道，ap1 Ap1。存在 a1A1,a2A2,apAp 构成链a1 a2 1。考虑两种情况：1.存在 m 个元素的反链 A，它不是 X 的所有极大元的集合，也不是 X 的所有极小元的集合，即存在不属于 A 的极大元，也存在不属于 A 的极小元。令A+=x:xX 且存在 aA 使得 a xA=x:xX 且存在 aA 使得 x a显然，A A+，A A。下述性质成立：|A+|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 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,92.若只有 X 的极大元集合和 X 的极小元集合才是有 m 个元素的反链。任取 X 的一个极小元 x，总可找到 X 的一个极大元 y 使得 x y，当然，这里 x=y 是可能的。因为 X 的有 m 个元素的反链一定是极大元集合或极小元集合，所以必包含 x 和 y 之一，X x,y的元素最多的反链有 m 1 个元素。由归纳假设知，可将 X x,y 划分成 m 1 个链 E1,Em1。可将X 划分成 m 个链：x y,E1,Em1。作业 8，18，20，25，41，46，49