现代工程数学第5章[课堂课资]

1、第 5 章 二项式系数 5.1 Pascal 公式 5.2 二项式定理 5.3 一些恒等式 5.4 二项式系数的单峰性 5.5 多项式定理 5.6 牛顿二项式定理 5.7 再论偏序集 作业 1章节内容 5.1 Pascal公式 定理定理5.1.1（ Pascal公式）若1 k n 1，则 证法证法1 1 11 k n k n k n k n knk n kkn knk n knk kn knk knn knk n knk n k n k n !)(! ! )( !)(! !) 1( !)(! !) 1( !)(! )(!) 1( !)(!) 1( !) 1( !) 1(! !) 1( 1 11

2、 2章节内容 证法证法2 设 S = a1, a2, an。S 的 k-组合由两部分组成。 1.不包含 an 的 k-组合，即a1, a2, an1的 k-组合， 有 个。 2.包含 an 的 k-组合，由a1, a2, an1的 k1-组合 增加 an 得到，有 个。 所以， k n1 1 1 k n 1 11 k n k n k n 3章节内容 Pascal（杨辉）三角形 kn n k n k n k n k n n nn 1 11 11 0 k n 01234 01 111 2121 31331 414641 4章节内容 5.2 二项式定理 n k kknn yx k n yx 0 )(

3、 个n n yxyxyx)()()( 定理定理5.2.1 设 n 是正整数，则 证法证法1 取 k 个 y，n k 个 x 相乘得出 xnk y k。 5章节内容 1 0 11 1 11 1 1 1 1 11 1 0 11 1 11 0 1 0 1 0 1 10011 11 1 0 )()()( 1 1 0 1 )( n k kknn n k kknn n n k kkn n k kknn n j njjn n k kknn n k kkn n k kkn n k kknnn yx k n yyx k n x yyx k n yx k n x y n n yx j n yx k n x n y

4、x k n yx k n yx k n yxyxyxyx yxyxyxn归纳。对证法2 6章节内容 n k kn n k kknn n k k n k kn x k n xxyx yx k n yx x kn n x k n x n 0 0 00 )1 (, 1 )( )1 ( 得到中取 在 为非负整数，设 证明 定理5.2.2 7章节内容 5.3 一些恒等式 1 11 k n k n k n kn n k n 0) 1(1 21 )1 ( 0 0 0 n k k n n k n k kn k n x k n x x k n x ，得令 ，得令 8章节内容 奇组合与偶组合各半 O=k | 0

5、k n , k是奇数， E=k | 0 k n , k是偶数 EkOk Ek k Ok k EOk k n k kn k n k n k n k n k n xx k n x ) 1() 1() 1(0 1)(1 0 ，令，证法1 1 2 n EkOk k n k n 9章节内容 证法证法2 设 S = a1, a2, an。考虑 S 的偶组合， a1 有两种选择， a1 选定后， a2 有两种选择， a1, a2, an1 都选定后， an 只有一种选择，若已选 了偶数个元素，则不选 an ，否则选 an 。所以， S 的偶组合共有 2n1 个。 S 的奇组合数目为 2n 2n1 = 2n1

6、 10章节内容 证法证法3 设 S = a1, a2, an。在 S 的奇组合集合 与 S 的偶组合集合之间建立一一对应 f 。任取 S 的奇组合 A，令 AaaA AaaA Af 11 11 )( 若 若 11章节内容 。则 若 若 ，令的偶组合任取 ， ， ， ， 明的不同奇组合，可以证是和设 CAf CaaC CaaC A CS BfaBaAAfBaAa BfaBaAAfBaAa BfaBaAAfBaAa BfaBaAAfBaAa BfAfSBA )( )()(. 4 )()(. 3 )()(. 2 )()(. 1 )()( 11 11 1111 1111 1111 1111 12章节内

7、容 nk k n n k n k 1 1 1 其中 1 1 ! )( ! ) 1( ! ) 1( ! )( ! ! k n n knk nn knk nk k n k 证明 13章节内容 1 1 011 1 1 0 1 1 2 1 1 1 2 1 1证法 12 n n k n k n k n n k n n k n k n n k n n k n k k n nn k n k其中 14章节内容 12 1 1 nn k n k n n k 其中 n k n n k kn n k kn k n knx x k n kxnx x k n x 1 1 1 11 0 21 )1 ( )1 (证法 得令

8、求导数两边对 2 15章节内容 12) 1( 2 1 2 nnn k n k n n k 其中 n k kn n k kn n k kn x k n kxnxx x k n kxnx x k n x 1 1 1 11 0 )1 ( )1 ( )1 (证明 两边乘 求导数两边对 k n k n x k n kxnx x 1 1 )1 ( 求导数两边再对 16章节内容 221 1 2 1 1221 1 12 1 2) 1(2) 1(2 1 )1 () 1()1 ( nnn n k n k knn n k k n k k nnnnn k n k x x k n kxxnnxn x k n kx k

9、n k 得令 21 11 1 )1 () 1()1 ( )1()1 ()( )1 ( nn nn n xxnnxn xnxxnx xnx 17章节内容 )2)(1( 32 )2)(1( )2(12 1 2 0 22 )2)(1( 1 2 2 )2)(1( 1 1 1 )2)(1( 1 )2)(1( 1 )2)(1( 1 22 2 0 0 00 0 nn n nn n nn k n nn k n nn k n knk n kk k n kk nn n k n k n k n k n k 解法1 求 18章节内容 n k k n n k k x n k k x n k k n x n x n n

10、k kn n k x k n kn x x k n k x k n k dxx k n n x n x dxx x k n x k n kk 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 1 1)1 ( 1 1 1 1 1 1)1 ( 1 )1 ( )1 ( )1 (解法 )2)(1( 1 2 求 19章节内容 )2)(1( 32 )2)(1( )2(12 1 2 12 1 1 )2)(1( 1 )2)(1( 1 )2)(1( 1 1 1 1 2 12 1 1 1 2 )1 ( 1 1 1)1 ( 1 1 1 1)1 ( 22 2 0 0 1 0 0 2 1 0 0

11、1 2 1 0 2 1 0 1 0 1 1 0 1 nn n nn n nnk n kk k n kk x k n kk dxx k n k nnn x n dxdxx n dx n x nn n n k n k n k k n k k nn n n 20章节内容 n n k n n k 2 0 2 n n k n n n kn n k n x x k n x k n xx n k n k n n k k n k k nn 2 2 2 )1 ()1(证法 0 2 0 2 0 2 0 22 即 的系数相等两边的 1 21章节内容 n k n k nn k n kn n k n n n nS kn

12、 kn n Bk k n A knBkAnS BASbbBaaA 0 2 0 11 2 - -)(- -)(- ,证法 组合数的 组合，个有组合，个有 组合合并而成。的组合与的组合由的 ，设2 n n k n n k 2 0 2 22章节内容 组合数定义域的扩充 组合数函数的定义域。的定义相同，它扩大了 定义与组合数都是非负整数时，这个和当 多项式。次是时，当 是任意整数。是任意实数，其中 为负整数 为非负整数 kr rk k r k kr k k k krrr k r 0 0 ! ) 1() 1( 23章节内容 多项式等式的证明法 若次数 n 的多项式 f (x)和 g(x) 在多于 n 个

13、点 的值相等，则它们是相同的多项式。 因为次数 n 的多项式 f (x) g(x) 有多于 n 个根， 所以是零多项式 0。 。为为负整数，上式两边均若 。，右式两边均为，左式两边均为若 。为任意实数时上式成立所以 的整数时，上式成立，为为正整数，当设 0 00 1 1 1 11 k k r krk k r r k r k k r k r k r 1 24章节内容 1 00 0 0 0 0 1 1 1 11 1 2 1 0 1 0 1 0 1 0, 0 1 k i k i k i i k i i in k kn i in k kn k kn k kn i in k kn i innn k k

14、kn i in k knn k kn ，则设 。时，当 进行归纳。对证法 25章节内容 个。组合有的不含含 个，组合有的不含含 个，组合有的不含 组合。的元集考虑证法 0 , , 1 1 , ,1 0, 0 1 121121 2121 11 121 0 n kaaaaaaaa k kn kaaaa k kn kaa kaaaSkn kn i in k knn k kn kkkk kn k i 2 26章节内容 为任意整数为任意实数 kr i ir k kr k i , 1 0 若 k 为非负整数，当 r 为非负整数时等式成立，所 以 r 为任意实数时等式成立。 若 k 为负整数，等式两边均为

15、0。 27章节内容 1 00 0 0 0 0 1 1 1 1 1 2 1 1 00 1 0 1 1 0 0 0 1 1 n i n i n i i n i k i k n k i k n k n k n k i k n k i kkkk n n nk k i k n kk n ，则设 时，当 进行归纳。对证法1 28章节内容 个。组合有的只含 个，组合有的不含含 个，组合有的含 组合。的元集考虑证法 k kaaaaa k n kaaaa k n kaa kaaan nk k i k n kk n nnn n n i 0 1, , 1 1, 1 1,1 0 0 1 1 1121 1221 11

16、121 0 2 29章节内容 nk k i k n kk n n i 0 0 1 1 0 若 k n，等式两边均为 0。所以，当 k 和 n 为任意 非负整数时，等式成立。 30章节内容 证明组合恒等式的方法 1.用组合数公式直接验证。 2.用数学归纳法。 3.分析恒等式的组合意义。 4.利用二项式定理，对公式进行微分或者积分运 算。 5.利用二项式定理，比较多项式的系数。 31章节内容 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

17、, 2, 1, 2, 1 不是单峰的。 32章节内容 n nnnn n n nnn n n nnn nn n 2 1 2 1 2 0 0 , 1 , 0 1 . 4 . 是奇数若 是偶数若 是单峰序列。定理5 33章节内容 证明证明 设 1 k n k kn knk n knk n k n k n 1 ! ) 1( ! ) 1( ! ! )( ! ! 1 1 1221 , 22 2 1 121 ,2 2 k kk k kn kn n k k kk k kn kn n k n 时，当 时，当 为偶数若 34章节内容 1 21 ,21 2 1 1 21 ,21 2 1 1 21 ,21 2 1 k

18、 kk k kn kn n k k kk k kn kn n k k kk k kn kn n k n 时，当 时，当 时，当 为奇数若 35章节内容 。 为正奇数时，当 ；为非负偶数时，当 ，例如， 的最小整数天花板函数 的最大整数，其中地板函数 。中最大者为 22 22 22 1 11125 . 115 . 1 , 1 , 0 2 . 4 . 5 nn nn nn n n xx xx nn n nnn 推论 36章节内容 设 C 是由集合 S 的组合组成的集合。若对于 C 中 任何两个不同组合 X 和 Y， X Y 且 Y X ，则称 C 为 S 的杂置。例如， C =a, b, b, c

19、, d,a, d, a, c 是 S =a, b, c, d 的杂置。 设 S 是 n 元集。对于每个 k n ， S 的所有 k 组合 组成的集合是 S 的杂置。在这样的杂置中，当 时所包含的组合最多，有个。这 是包含的组合最多的 S 的杂置。 / / 2 n k 2 n n 37章节内容 设 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

20、a ，矛盾。因 此， A 和 C 至多有一个公共元素 。设 C 是杂置。 若有一个链划分包含 m 个链，则因为 C 中的两个 组合不能在同一个链中，所以 C 中组合的个数至 多是 m。 / / 38章节内容 定理定理5.4.3（Sperner 定理）设 S 是 n 元集。则 S 的 杂置最多包含个组合。 证明证明 设 S = 1, 2, , n。归纳证明： S 的所有 2n 个组合的集合 P(S) 可以被划分为个链。 2 n n 2 n n 39章节内容 n = 1： 1 n = 2： 1 1, 2 2 n = 3： 1 1, 2 1, 2, 3 3 1, 3 2 2, 3 这些链划分有以下两

21、个性质： 1.链中每个组合比它前面的组合多一个元素。 2.链中第一个组合与最后一个组合的元素个数之 和是 n 。 称这样的链划分为对称的链划分。 40章节内容 设 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 。 4

22、1章节内容 设 A1 A2 Ak 是 P(1, 2, , n) 的对称的链划分中的链，则 | A1 | + | Ak | = n 且 | A1 | | Ak |。若 k = 1，则 | A1 | 若 k 1，则 | A1 | 且 | Ak | ， A1 , A2 , , Ak 中存在唯一 组合。 2 n 222 nnn 2 n 2 n 42章节内容 因为在 P(1, 2, , n) 的对称的链划分的每个链中 存在唯一 -组合，共有 个 -组合，所 以在对称的链划分中有 个链。每个杂置中 的组合个数至多是 。 2 n 2 n n 2 n 2 n n 2 n n 43章节内容 5.5 多项式定理

23、knk n k n ananan nnn n nnnnt nnn n nnn n tt t t tt 二项式系数 的全排列数。是多重集 其中 定义多项式系数 , , 2 ! ! 2211 21 21 2121 44章节内容 公式。，这是即 ，时，当 。其中 的全排列数，的是第一个元素为 Pascal 1 1 1 1 1 1 1 2 , 1 1 1 1 1 1 1 1 111 212121 2211 1 212121 21 n n n n n n nn n nn n nn n t anananS Sa nnn n nnn n nnn n nnn n nnn n tt k tk ttt t 45章

24、节内容 的系数。的全排列数是所以， 乘积的每个全排列对应一项 。为非负整数，设 个 t t t t t n t n tt n t n tt n tt n t nnn nn n t n t n t xxxnxn xxxnxn xxxxxx xx nn n xx tn 1 1 1 1 1 111 111 111 0, 1 1 1 , , 证明 2定理 5.5.1 46章节内容 5.6 牛顿二项式定理 式定理。 定理即成为普通的二项为正整数，牛顿二项式令 其中 ，则是实数，设 ! ) 1() 1( )( |,5.6.1定理 0 k k k yx k yx yxyx k kk 47章节内容 在牛顿二项

25、式定理中，令 x = z，y =1，得 0 )1 ( k k z k z k kn k knnn k knnn k n kk 1 ) 1( ! ) 1() 1( ) 1( ! ) 1() 1)( 48章节内容 00 1 00 1 0 00 11 )1 ( 1 1 ) 1( 11 ) 1()1 ( 1 1 1 )1 ( 1 ) 1()1 ( , 1| k k k k k kk k kk k kn k kk k kn zz k k z z zz k k z z z k kn z z k kn z k n zz设 49章节内容 牛顿二项式定理的应用 1623. 3 62 13 3)1 (3) 13(

26、10 3 9 12 3 2 1 2 1 2 9 12 1 2 1 9 1 2 1 0 9 1 2 1 9 1 2 2 1 2 1 k k n k x的近似值求 50章节内容 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 显然，反链的子集仍是反链，链的子集仍是链。 51章节内容 例例 设 X = 1, 2, 10，考虑偏序集 (X, | )，其中 | 是整除

27、关系。4, 6, 7, 9, 10是反链，1 | 2 | 4 | 8 是 链。 52章节内容 设 (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 个链。 53章

28、节内容 定理定理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 分成反链的划分。54章节内容 任取 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 的极 小元。 57章节内容 令 A+ = x : xX 且存在 aA 使得 a x A = x : xX 且存在 aA 使得 x a 显然，A A+，A A 。下述性质成立： | A+ | | X |。设极小元 xA。若 xA+，则存在 aA 使得 a x