# 《离散数学》杨争锋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)

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_图文.ppt
《离散数学》讲义 - 4 - 第七章 图论 7.1 图的基本概念 离散数学 1

《离散数学》第七章_图论-第3-4节_图文.ppt
《离散数学》第七章_图论-第3-4节 - 7-3 图的矩阵表示 除用图形表示图外
《离散数学》,屈婉玲、耿素云-KefeiChen陈克非_图文.ppt
《离散数学》,屈婉玲、耿素云-KefeiChen陈克非_数学_自然科学_专业资料

0004《离散数学》 答案_图文.doc
0004《离散数学》 答案_理学_高等教育_教育专区。且 A∩B={xx∈A 且 x...电大离散数学作业答案04... 4页 1下载券 电大离散数学作业答案06... 暂无...

? 离散数学是现代数学的一个重要分支,是计算机科学与技术 的理论基础,所以又称为计算机数学,是计算机科学与技术 专业的核心、骨干课程。离散数学是什么课? ? 它以...

《离散数学》集合的基本概念和运算_图文.ppt
《离散数学》集合的基本概念和运算_数学_自然科学_专业资料。第3章 集合的概念
《离散数学》第六章 集合代数_图文.pdf
《离散数学》第六章 集合代数_理学_高等教育_教育专区。《离散数学》(屈婉玲版)
《离散数学》图的基本概念-2_图文.ppt
《离散数学》图的基本概念-2_数学_小学教育_教育专区。7.2 通路、回路与图的

《离散数学》第6章 图的基本概念_图文.ppt
《离散数学》第6章 图的基本概念_理学_高等教育_教育专区。好 图论简介 图论是
《离散数学》二元关系和函数-_图文.ppt
《离散数学》二元关系和函数-_数学_高中教育_教育专区。文档均来自网络,如有侵权