当前位置:首页 >> 数学 >>

《离散数学》杨争锋ch04-4_图文

§4.4 Binomial Coefficients (二项式系数) 1. The Binomial Theorem (1) Example 1 (page 227)

(x+y)3=x3+3x2y+3xy2+y3

(2) Theorem 1 The Binomial Theorem (page 327)

(x+y)n = ∑j=0 n C(n,j) xn-j yj
=C(n,0)xn + C(n,1)xn-1y + C(n,2)xn-2y2 + ……………….. + C(n,n-1)xyn-1 + C(n,n)yn

Proof: 当乘积被展开时其中的项都是下述形式: xn-jyj, j=0,1,2, …, n。为计数形如xn-jyj的项 数,观察到必须从n个和中选n-j个x(从而 乘积中其他的j个项都是y)才能得到这种项。 因此, xn-jyj的系数是 C(n,n-j)=C(n,j) 定理得证。

(3) Example (page 328) (a) Example 2 What is the expansion of (x+y)4? Solution: (x+y)4 = ∑j=0 n C(4,j)

x4-j yj = C(4,0)x4 + C(4,1)x3y + C(4,2)x2y2 + C(4,3)xy3 + C(4,4)y4 =x4 + 4x3y + 6x2y2 + 4xy3 + y4

(b) Example 4 What is the coefficient of x12y13 in the expansion of (x+y)25? Solution: C(25,13) = 25! / (13! ×12!)

(c) Example 4 What is the coefficient of x12y13 in the expansion of (2x-3y)25? Solution: (2x+(-3y))25 = ∑j=0 25

C(25,j) (2x)25-j (-3y)j

The coefficient of x12y13 is C(25,12) 212 (-3)13 = - 25!/(13!×12!) 212313

(4) Corollary 1 Let n be a nonnegative integer. The

∑k=0 n C(n,k) = 2n
Proof: 2n = (1+1)n
= ∑k=0 n

C(n,k) 1k 1n-k

= ∑k=0 n C(n,k)

(5) Corollary 2 Let n be a positive integer. Then

∑k=0 n (-1)k C(n,k) = 0
Proof: 0 = 0n = ((-1) + 1)n = ∑k=0 n (-1)k 1n-k = ∑k=0
n

(-1)k C(n,k)

Remark: Corollary 2 implies that
C(n,0) + C(n,2) + C(n,4) + ……. = C(n,1) + C(n,3) + C(n,5) + …….

(6) Corollary 3 Let n be a nonnegative integer. Then

∑k=0 n C(n,k) 2k = 3n
Proof: (1+2)n = ∑k=0 n C(n,k) 1n-k 2k = ∑k=0 n C(n,k) 2k

2. Pascal’s Identity and Triangle (1) Pascal’s Identity Let n and k be positive integers with n≥k. Then C(n+1,k) = C(n,k-1) + C(n,k) Proof: 假设T是一个含有n+1个元素的集合,令a是T中 的一个元素,且S=T-{a}。注意到T的包含k个元 素的子集有C(n+1,k)个。然而T的含k个元素的子 集或者包含a和S中的k-1个元素,或者不包含a但 包含S中的k个元素。由于S的k-1元素子集有 C(n,k-1)个,故T含a在内的k元素子集有C(n,k-1) 个。又由于S的k元素子集有C(n,k)个,故T的不 含a的k元子集有C(n,k)个。从而可得: C(n+1,k) = C(n,k-1) + C(n,k)

Remark: Pascal’s Identity, together with the initial conditions C(n,0)=C(n,n)=1 for all integers n, can be used to recursively define the binomial cofficients

(2) Pascal’s Triangle 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 ………………………………………………

3. Some Other Identities of the Binomial Coefficients (1) Vandermondes’s Identity Let m, n, and r be nonnegative integers with r not exceeding either m or n. Then C(m+n, r) = ∑k=0r C(m, r-k) C(n,k)

Proof: 假定在第一集合中有m个项,第二集合中有n个 项。从这两个集合的并集中取r个元素的方式数是 C(m+n,r)。从并集中取r个元素的另一种方式是先 从第一个集合中取k个元素,接着从第二个集合中 取r-k个元素,其中k是满着0≤k≤r的整数。用乘积 法则,这可以用C(m,k) C(n,r-k)种方式完成。所 以,从这个并集中选取 r个元素的总方式数等于 C(m+n, r) = ∑k=0r C(m, r-k) C(n,k) 这就证明了范德蒙德恒等式

(2) Corollary 4 If n is a nonnegative integer. Then C(2n, n) = ∑k=0n C(n,k) 2 Proof: 我们使用范德蒙德恒等式且m=r=n: C(2n, n)
= ∑k=0n C(n, n-k) C(n,k) = ∑k=0n C(n, k)2

(3) Theorem 4 Let n and r be nonnegative integers with r≤n. Then C(n+1, r+1) = ∑j=rn C(j,r) Proof: See next slide

Proof: 由§4.3中的Example 10可知,等式的左边, C(n+1, r+1)计算了长度为n+1的二进制位串中含 r+1个1 的位串的个数。 现考虑等式右边,考虑二进制位串中最后一 个1的位置,显然可知,最后一个1的位置肯定在 位置r+1, r+2, …… ,或n+1。更进一步讲,若最后 1的位置是k,那么二进制位串中前k-1个位置必须 有r个位置上是1。所以,由§4.3中的Example 10, 相应的二进制位串有C(k-1,r)个。由于k的取值范 围是:r+1≤k≤n+1,所以我们有

∑k=r+1n+1 C(k-1, r) = ∑j=rn C(j, r)
个含有r+1个1 的长度为n的二进制位串。

Exercises
? 8、10、20、22、24、28 (Fifth and Sixth Edition)


相关文章:
2019《离散数学》杨争锋ch04-4.ppt_图文.ppt
2019《离散数学》杨争锋ch04-4.ppt - §4.4 Binomial
2019《离散数学》杨争锋ch04-2.ppt_图文.ppt
2019《离散数学》杨争锋ch04-2.ppt - §4.2 The Pigeo
《离散数学》杨争锋ch01-1-精选文档_图文.ppt
《离散数学》杨争锋ch01-1-精选文档 - Chapter 1 The Fou
离散数学4.3-4_图文.ppt
离散数学4.3-4_数学_自然科学_专业资料。4.3 关系的性质 ? ? 自反性
《离散数学》讲义 - 4_图文.ppt
《离散数学》讲义 - 4 - 第七章 图论 7.1 图的基本概念 离散数学 1
离散数学ch2 (4)_图文.ppt
离散数学ch2 (4)_计算机软件及应用_IT/计算机_专业资料。第五章 一阶逻
离散数学CH04图论基本概念_图文.ppt
离散数学CH04图论基本概念 - 离散数学 Discrete Mathemati
离散数学1-3,1-4_图文.ppt
离散数学1-3,1-4_理学_高等教育_教育专区。离散数学 Discrete Mathematics 陈明 Email:mingchen_gang@163.com 信息科学与工程学院 二零一三年九月离散数学 课程...
《离散数学》第七章_图论-第3-4节_图文.ppt
《离散数学》第七章_图论-第3-4节 - 7-3 图的矩阵表示 除用图形表示图外
《离散数学》,屈婉玲、耿素云-KefeiChen陈克非_图文.ppt
《离散数学》,屈婉玲、耿素云-KefeiChen陈克非_数学_自然科学_专业资料
精品课程《离散数学》PPT课件(全)_图文.ppt
言1 为什么学习离散数学?离散数学是现代数学的一个重要分支,是计算机科学与技术
0004《离散数学》 答案_图文.doc
0004《离散数学》 答案_理学_高等教育_教育专区。且 A∩B={xx∈A 且 x...电大离散数学作业答案04... 4页 1下载券 电大离散数学作业答案06... 暂无...
精编精品课程《离散数学》ppt课件(全_图文.ppt
? 离散数学是现代数学的一个重要分支,是计算机科学与技术 的理论基础,所以又称为计算机数学,是计算机科学与技术 专业的核心、骨干课程。离散数学是什么课? ? 它以...
方世昌《离散数学》课程教案(上)_图文.pdf
离散数学 离散数学 离散数学结构 离散数学习题解答 离散数学习题与解析 1 课程教学进度安排周次 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11...
《离散数学》集合的基本概念和运算_图文.ppt
《离散数学》集合的基本概念和运算_数学_自然科学_专业资料。第3章 集合的概念
《离散数学》第六章 集合代数_图文.pdf
《离散数学》第六章 集合代数_理学_高等教育_教育专区。《离散数学》(屈婉玲版)
《离散数学》图的基本概念-2_图文.ppt
《离散数学》图的基本概念-2_数学_小学教育_教育专区。7.2 通路、回路与图的
离散数学-一阶谓词逻辑_图文.ppt
离散数学-一阶谓词逻辑 - 《离散数学》 课程学时:48 讲授:杨绍禹 ysy@
《离散数学》第6章 图的基本概念_图文.ppt
《离散数学》第6章 图的基本概念_理学_高等教育_教育专区。好 图论简介 图论是
《离散数学》二元关系和函数-_图文.ppt
《离散数学》二元关系和函数-_数学_高中教育_教育专区。文档均来自网络,如有侵权