9512.net
甜梦文库
当前位置:首页 >> 数学 >>

组合数学课件(第四章二项式系数)



组合数学课件
制作授课:王继顺

目录(1)


第1章 什么是组合数学 1.1引例 1.2组合数学研究对象、内容和方法 第2章 鸽巢原理 2.1 鸽巢原理:简单形式 2.2 鸽巢原理:加强形式 2.3 Ramsey定理 2.4 鸽巢原理与Ramsey定理的应用 本章小结 习题 第3章 排列与组合 3.1 两个基本的

计数原理 3.2 集合的排列与组合 3.3 多重集的排列与组合 本章小结 习题


第四章 二项式系数 4.1 二项式定理 4.2组合恒等式 4.3非降路径问题 4.4牛顿二项式定理 4.5多项式定理 4.6 基本组合计数的应用 本章小结 习题 第五章 包含排斥原理 5.1 包含排斥原理 5.2 多重集的r-组合数 5.3错位排列 5.4 有限制条件的排列问题 5.5有禁区的排列问题 本章小结 习题

目录(2)
第八章 Polya定理 8.1置换群中的共轭类与轨道 8.2 Polya定理的特殊形式及其应用 本章小结 习题

第六章 递推关系 6.1 Fibonacci数列 6.2 常系数线性齐次递推关系的求解 6.3 常系数线性非齐次递推关系的求 解 6.4 用迭代和归纳法求解递推关系 本章小结 习题 第七章 生成函数 7.1生成函数的定义和性质 7.2多重集的r-组合数 7.3正整数的划分 7.4指数生成函数与多重集的排列问 题 7.5 Catalan数和Stiring数 本章小结 习题

********************** 课程总结

第4章 二项式定理
教学目标:
1.掌握二项式定理、证明方法及其应用; 2.掌握推广的二项式定理; 3.掌握多项式定理、证明方法及其应用; 4.理解一些组合恒等式的意义及其证明方法; 5.非降路径问题的组合意义及应用;

重点:二项式定理、多项式定理证明方法及其应用; 难点:一些组合恒等式证明方法,非降路径问题组合意
义及应用。

第4章 二项式定理

§4.1二项式定理
1.二项式系数 n 组合数C(n,k)或者 k 2. 组合数的定义
k ? n, ? 0, n ? ? ? n! ? ?k ? ??? ? ? ? k!(n ? k )! , 0 ? k ? n. ?

()

也叫二项式系数.

§4.1 二项式定理 3.组合数的一些恒等式 (1)对称式

?n? ? n ? ? ?k ? ??? ?n ? k ? ? ? ? ? ?

(4.1)

(2)抽取式
? n ? n ? n ? 1? ? ?k ? ?? k? ? n ? 1? ?, n, k为正整数. ? ? ? ?

(4.2)

(3)Pascal公式
? n ? ? n ? 1? ? n ? 1 ? ? ?k ? ??? ? k ? ??? ? k ? 1? ?, n, k为正整数. ? ? ? ? ? ?

(4.3)

§4.1二项式定理
n,k∈N,有C(n,k)=(n/k) C(n-1,k-1) 抽取式(4.2):如 §4.2 组合恒等式及其含义抽取式 (4.2)

证明:从 n个元素中取 k个的组合可先从 n个元素中取 1个,再从 剩下的n-1个元素中选择k-1个,组合数为C(n-1,k-1)。选出的k个 元素都有可能被第一次选中,因是组合,故重复度为k。得证。 或通过计算证明: n 若 k ? n, n ? n ? 1 ? 0 k k k ?1 若1 ? k ? n, 有 n ? n( n ? 1)...( n ? k ? 1) k k ( k ? 1)...1 n ( n ? 1)( n ? 2)...( n ? k ? 1) n n ? 1 ? ? ? k ( k ? 1)( k ? 2)...1 k k ?1

?) ? )

?)

? )

? n ? ? n ? n ? 1? ?k? ? ? ? ? n?k ? k ? 证:某班有n名同学,要选出k位班委会成 员,再选1名作书记,这名书记不可以是班 委会成员,问有多少种不同的方案?

? n? ? n ? k ? 1 ? n ? ?k? ? k ? 1? ? ? ? ? k

证明:从n名同学中选出k位组成班 委,在k位班委中选1人做班长,问 有多少种方法?

§4.1 二项式定理
n

§4.1二项式定理

定理 4.1

如n ? N , ?x , y ? R, 有( x ? y )n ? ? n x k y n?k k k ?0

?)

证明:因为 (x+y)n=(x+y)(x+y)…(x+y) ,等式右端有 n 个因子,项 xkyn-k 是从这 n 个因子中选取 k 个因子, k=0,1,…,n 。在这 k 个 (x+y) 里都取 x,而从剩下的 n-k个因子 (x+y)中选取 y作乘积得到,因此 xkyn-k的系数为上述选法的个数C(n,k)。故有

证毕。 注:可用数学归纳法证明,证明略; C(n, k)又称二项式系数。

( x ? y )n ? ? n x k y n ? k k k ?0

n

?)

§4.1二项式定理推论1 § 4. 1二项式定理

四个推论
n

如n ? N , ?x , y ? R, 有( x ? y ) ? ? n x k y n ? k 推论4.1.1: n?k k ?0 n n ? ? n x n?k y k ? ? n x n?k y k k n?k k ?0 k ?0 n n n n k 如n ? N , ?x ? R, 有(1 ? x ) ? ? x ? ? n xk 推论4.1.2: k n?k k ?0 k ?0 n 如n ? N , 有? n ? 2n 推论4.1.3: (4.4) n元集合的所有子集个数是2n k k ?0

?)

?)

? ) ? ) ?) ? )
n

证明:在推论4.1.2中令x=1,即可得证。 利用组合分析,等式左端相当于从 A={an}中任意选择 k(0≤k≤n)个 元素的所有可能数目,即对 n个元素,每一个都有被选择和不被 选择的可能,总的可能数为2n。 另外,该等式还表明A的所有子集个数为2n。

§4.1二项式定理推论2 § 4.1 二项式定理

四个推论
n

如n ? N , ?x , y ? R, 有( x ? y ) ? ? n x k y n ? k 推论4.1.1: n?k k ?0 n n ? ? n x n?k y k ? ? n x n?k y k k n?k k ?0 k ?0 n n n n k 如n ? N , ?x ? R, 有(1 ? x ) ? ? x ? ? n xk 推论4.1.2: k n?k k ?0 k ?0 n 如n ? N , 有? n ? 2n 推论4.1.3: k k ?0 n 如n ? N , 有? ( ?1)k n ? 0 推论4.1.4: (4.5) k k ?0 证明:在推论4.1.2中令x=-1,即可得证。 另外,该等式还表明A={an}的偶数子集个数和奇数子集个数相等。

?)

?)

? ) ? ) ?) ? )
n

?)



?n? ?n? ?n? ?n? ? ?0? ??? ? 2? ? ?? ? ? ?1? ??? ? 3? ? ? ?. ? ? ? ? ? ? ? ?

n 元集合的偶子集个数与 奇子集个数相等

(4.5)’

§4.2 (4.6) § 4. 组合恒等式及其含义恒等式 2 组合恒等式及其含义
n ?1 如 n ? N , 有 k ? C ( n , k ) ? n ? 2 恒等式(4.6) : ? k ?1 n

证明:考虑盒子1中有n个有区别的球,从中取一个球放入盒子2 中,再取任意多个球放入盒子 3中。等式左端表示先从盒子 1 中 取k(k=1,2,…,n)个球,再从中取一个放入盒子 2中,剩下的 k-1个 球放入盒子3中。等式右端表示先从盒子1中取一个放入盒子2中, 剩下的 n-1 个球是否放入盒子 3 中均有两种可能。显然两种取法 结果是一样的。得证。 或通过计算证明: n n n n n ? k ? n ?1 ? n n ?1 k ? ? ? k k ? 1 k ?1 k k ?1 k ?1 k ?1 n n ?1 n ? 1 n ?1 ? n ? n ? n ? 1? ? n ? n ? ? 由式(4.2) : ? k ? 1 k ?k ? ?? k? ? n ? 1? ? k ?1 k ?0 ? ? ? ? ? n ? 2n ?1

?)

? ) ? ) ? ) ? )

§ 4. 2 组合恒等式及其含义
n ?1 如 n ? N , 有 k ? C ( n , k ) ? n ? 2 恒等式(4.6) :§4.2 组合恒等式及其含义 ? 恒等式(4.6) k ?1 n

证明:证法3 由二项式定理有

对上式两边微商得

?n? k (1 ? x) ? 1 ? ? ? ?k ? ?x , k ?1 ? ?
n n

然后令x=1得

? n ? k ?1 n(1 ? x) ? ? k ? ?k ? ?x , k ?1 ? ? n ?n? n ?1 n2 ? ? k ? ?k ? ?. k ?1 ? ?
n ?1 n

注:如令x=-1,可证明下面恒等式 。

§4.2 组合恒等式及其含义恒等式(4.6)

§ 4. 2 组合恒等式及其含义
n

类(4.6)恒等式(习题4.7) : 如n ? N , 有? ( ?1)k k ? C ( n, k ) ? 0 证明:
(1 ? x ) ? ? n x k k k ?0 将等式两边对x微分得 n n(1 ? x )n ?1 ? ? k n x k ?1 k k ?1 在上式中,令x=-1得 n n ?0 k ?1 ( ? 1) k ? k k ?1 n n ?0 k ?1 即 ( ? 1) k ? k k ?0
n n

?)

k ?0

?)

?) ?)

得证。

§ 4.2 组合恒等式及其含义 恒等式(4.6) § 4. 2 组合恒等式及其含义
1 2 n ?1 ? 1 ? C ( n, k ) ? 恒等式(习题4.8积分方法):如n ? N , 有? n ?1 k ?0 k ? 1 n n 证明: (1 ? x ) ? ? n x k k k ?0 将等式两边对x从0到1积分得 n 1 1 n n k (1 ? x ) dx ? x dx ? ?0 ? k 0 k ?0
n

?)
n k ?0

即 得证。

?) (1 ? x ) x n ? ?? ) k k ?1 n ?1 2 ?1 1 n ?? n ?1 k ? 1 ?k )
n ?1 1 n ?1 0 n k ?0

k ?1 1

0

§ 4.2 组合恒等式及其含义 恒等式(4.7) § 4. 2 组合恒等式及其含义
恒等式(4.7): 如n ? N , 有? k 2 ? C ( n, k ) ? n( n ? 1) ? 2n? 2
k ?1 2 如 n ? N , 有 ( ? 1) k ? C ( n, k ) ? 0 (4.7) ’ 类恒等式 : ?
k ?0 n

n

证明: (1 ? x )n ? ? n x k k k ?0 将等式两边对x微分得 n n(1 ? x )n ?1 ? ? k n x k ?1 k k ?1 将等式两边同乘以x后再对x微分得

n

?)

k ?0

?)

n ?1 n?2 2 n k ?1 ? n? (1 ? x ) ? ( n ? 1) x (1 ? x ) ? k x ? ? ? k k ?1 在上式中,令x=1得 n 2 n n?2 k ? n ( n ? 1)2 ? k k ?1 得证。 注:如令x=-1,即可证明另一恒等式(4.7)’ 。

n

?)

?)

§ 4. 2 组合恒等式及其含义
恒等式(4.8):如n,l,r∈N,l≥r,有C(n,l)C(l,r)=C(n,r)C(n-r,l-r) §4.2 组合恒等式及其含义恒等式(4.8) 证明:等式的左端可看作是先从n个元素中取l个元素,然后再从 所得的l个元素中再选择 r个元素的方法数。这种选法与直接从 n 个元素中选取r个元素的选法不同. 因为同样的r个元素可以多次 出现. 例如7元集{a,b,c,d,e,j,k},从中选5个元素,比如说{a,b,c,d,e} 和 {a,b,c,j,k},它们都可以选出同样的 3 个元素 {a,b,c},不难看出, 某r个元素可以重复出现的次数就是包含它们的 l元子集的个数, 而这种l元子集的其余l-r个元素可以取自n元集的n-r个元素, 所以 C (n ? r , l 个 ? r.) 综上所述,通过先选l个元素然后 这种l元子集有 ? n ?? l ? ? ? n ? ? n ? r ? ? ? n ? C(n,r)C(n-r,l-r)种。得证。 再选r个元素的选法应该有 ? l ?? r ? ? r ? ? l ? r ? ? r ? ? ?? ? ? ? ? ? ? ? 或通过计算证明: n! l! n! n l

? l )? r ) ? l !(n ? l )! ? r !(l ? r )! ? r !(n ? l )!(l ? r )!
n! ( n ? r )! ? r !( n ? r )! ( l ? r )!( n ? l )! ? n n?r r l ?r ?

? )? )

从n个候选人中,选出l个常委,再选出r位政 治局常委,选法的个数?

§4.2 组合恒等式及其含义恒等式(4.9)

§ 4. 2 组合恒等式及其含义

恒等式(4.9):Vandermonde恒等式,如n,m∈N且r≤min(m,n),有 C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+…+C(m,r)C(n,0)
证明:设 A={am},B={bn}, 且 A∩B=Φ , 则 A∪B=C 有 m+n 个元素。 C的r?组合个数为C(m+n,r),而C的每个r?组合无非是先从A中取 k个元素,再从 B中取出 r-k个元素组成 (k=0,1,…,r)。由乘法法则 共有C(m,k)C(n,r-k)种取法,再由加法法则即可得证。 或通过比较系数法证明: (1 ? x )m ? n ? (1 ? x )m (1 ? x )n m?n m n m ? n xr ? ? m xi ? ? n xj? ? ? ?? i ? ?? j r r ?0 ? i ?0 ? ? j ?0 ? m?n ? r m n r? ? ? ?? x ? k r ? k r ?0 ? k ?0 ? 比较等式两边xr的系数即可得证。

?

)

? ) ?) ? )? )

§ 4. 2 组合恒等式及其含义
n,m∈ N且r≤min(m,n), 恒等式(4.9)’:Vandermonde 恒等式,如 §4.2 组合恒等式及其含义 恒等式 (4.10) 有C(m+n,r)=C(n,0)C(m,r)+C(n,1)C(m,r-1)+…+C(n,r)C(m,0)
恒等式(4.10): 如m , n ? N , 有? C ( m , k ) ? C ( n, k ) ? C ( m ? n, m )
k ?0 m

恒等式(4.10)’:如m, n ? N , 有

? C (m, k )C (n, k ) ? C (m ? n, n).
k ?0
n k ?0

n

恒等式(4.10特例): 如n ? N , 有? C ( n, k ) ? C ( n, k ) ? C (2n, n)

§4.2 组合恒等式及其含义 恒等式(4.11) § 4. 2 组合恒等式及其含义 n 证明:利用组合分析法,在集合 A={an +1} 的 n+1 个不同元素选出 (4.11): 恒等式 如n, k ? Z 且n, k ? 0, 有? C ( i , k ) ?个元素中包含 C ( n ? 1, k ? 1) a , k+1 k+1 个元素的组合可分为以下多种情况:如 1 i ?0 相当于从除去 a1 的 n 个元素中选出 k 个元素的组合,组合数为 C(n,k);如不包含a1但包含a2,相当于从除去a1,a2的n-1个元素中 选出k个元素的组合,再加上a2而得到,组合数为C(n-1,k), …,同 理如不包含 a1,a2,…,an-k+1 ,但包含 an-k+2 ,相当于从剩下的 k 个元 素中选出 k个元素的组合,再加上 an-k+2 而得到,组合数为C(k,k); 注意,i<k时 ,C(k,k)=0。由加法法则得 n ? C (i , k ) ? C (n ? 1, k ? 1)

或对固定的k,对n使用归纳法,当n=0时,有 0 ? 1 ? 1 k ?0 k k ?1 0 k ?0 可见,当n=0时,等式成立。 如对任意n等式成立,则有 n ?1 n i ? i ? n ?1 ? n ?1 ? n ?1 ? n ? 2 ? ? k k k k ?1 k k?2 i ?0 i ?0 可见等式对n+1也成立。由归纳原理,得证。

i ?0

?) ? )?

?) ?)? ) ? )? ) ? )

§4.2 组合恒等式及其含义恒等式(4.12)

§ 4. 2 组合恒等式及其含义

恒等式(4.12):如n,r∈N,有C(n+r+1,r) = C(n+r,r)+C(n+r-1,r-1)+…+C(n+1,1)+C(n,0)

证明I:反复利用Pascal公式,即可证明。 或利用组合分析法,在集合A={an+r+1}的n+r+1个不同元素选出r 个元素的组合可分为以下多种情况:如r个元素中不包含a1,相 当于从除去a1的n+r个元素中选出r个元素的组合,组合数为 C(n+r,r);如r个元素中包含a1但不包含a2,相当于从除去a1,a2的 n+r-1个元素中选出r-1个元素的组合,再加上a1而得到,组合数 为C(n+r-1,r-1), …,同理如r个元素中包含a1,a2,…,ar-1,但不包含ar, 相当于从剩下的n+1个元素中选出1个元素的组合,再加上 a1,a2,…,ar-1而得到,组合数为C(n+1,1);如r个元素中包含 a1,a2,…,ar,相当于从剩下的n个元素中选出0个元素的组合,组 合数为C(n,0) 。由加法法则得 C(n+r+1,r)= C(n+r,r)+C(n+r-1,r-1)+…+C(n+1,1)+C(n,0)

§4.2 组合恒等式及其含义恒等式(4.12)

§ 4. 2 组合恒等式及其含义

恒等式(4.12) :如n,r∈N,有C(n+r+1,r) = C(n+r,r)+C(n+r-1,r-1)+…+C(n+1,1)+C(n,0)

证明 II :等式的左端可看作是在集合 A={an+2} 的 n+2 个不同元素 允许重复的选出r个元素的组合,可分为以下多种情况:如r个元 素中不包含a1,相当于从除去a1的n+1个元素中允许重复的选出r 个元素的组合,组合数为C(n+r,r);如r个元素中只包含一个a1, 相当于从除去a1的n+1个元素中允许重复的选出r-1个元素的组合, 再加上a1而得到,组合数为C(n+r-1,r-1);如r个元素中包含两个 a1,相当于从除去a1的n+1个元素中允许重复的选出 r-2个元素的 组合,再加上两个 a1而得到,组合数为 C(n+r-2,r-2), …,同理如 r 个元素中包含r个a1,其组合数为C(n,0) 。由加法法则得 C(n+r+1,r)= C(n+r,r)+C(n+r-1,r-1)+…+C(n+1,1)+C(n,0)

§4.2 组合恒等式证明方法

§ 4. 2 组合恒等式及其含义

常用的证明方法

? 数学归纳法 ? 二项式系数公式,特别是Pascal 公式 ? 比较级数展开式中的系数(二项式定理或母函数法) ? 积分微分法 ? 组合分析法

§ 4. 2 组合恒等式及其含义
r4.2 <n组合恒等式及其含义例 , 有C(n,r+1) 例4.1 如n,r∈N, § 4.1 = C(r,r)+C(r+1,r)+…+C(n-1,r) 证明

C (r,r ) ? C (r ? 1,r ) ? ? ? C (n ? 1,r ) ? C (r ? 1,r ? 1) ? [C (r ? 2 ,r ? 2) ? C (r ? 1,r ? 1)] ? ? ? [C (n, r ? 1) ? C (n ? 1,r ? 1)] ? C (n, r ? 1).
在上面的等式中,用n+r代替n,得 恒等式(4.13) : C(n+r,r+1) = C(r,r)+C(r+1,r)+…+C(r+n-1,r).

§ 4. 2 组合恒等式及其含义 在式(4.13)中,如果令r=1,就得到 1+2+3+…+n=C(n+1,2)=n(n+1)/2. 这是等差级数的求和公式.如果令r=2 ,则有 1+C(3,2)+C(4,2)+…+C(n+1,2)= C(n+2,3) = n(n+1) (n+2)/6. 在这个等式中每相邻两项之差就是等差级数的项, 称这个等式叫做二阶等差级数求和公式. 如果令r=3 ,则有 1+C(4,3)+C(5,3)+…+C(n+2,3)= C(n+3,4). 其中每相邻两项之差就是二阶等差级数的项,把这个 等式叫做三阶等差级数的求和公式.

§4.2 组合恒等式及其含义例4.2

§ 4. 2 组合恒等式及其含义

例4.2 计算 12+22+32+…+n2, 13+23+33+…+n3. 解 对任何正整数k,有 k2 =2C(k,2)+C(k,1), k3 = 6C(k,3)+6C(k,2)+C(k,1). 所以有 12+22+…+n2 =2[C(1,2)+C(2,2) +…+C(n,2)]+[C(1,1)+C(2,1)+…+C(n,1)] =2(n+1)n(n-1)/6+(n+1)n/2 = n (n+1) (2n+1)/6. 13+23+…+n3 = 6[C(1,3)+C(2,3) +…+C(n,3)]+6[C(1,2)+C(2,2) +…+C(n,2)]+[C(1,1)+C(2,1)+…+C(n,1)] =6(n+1,4)+6(n+1,3)+(n+1,2) =2(n+1)n(n-1)/6+(n+1)n/2 = [n (n+1)/2]2.

§ 4. 2 组合恒等式及其含义
2的素数,则当C例 (2 p,p)被p除时余数是2. 例4.3 证明若p是不等于 §4.2 组合恒等式及其含义 4.3 证明 在恒等式(4.10)中

? C (m, k )C (n, k ) ? C (m ? n, m).
k ?0

m

令m=n=p得

2 C ( p , k ) ? C (2 p, p). ? k ?0

m

(4.14 )

可以证明,如果p为素数且0<k<p,则p|C(p,k). 因为由组合数 C(p,k)的计算公式知k!整除p(p-1)…(p-k+1). 又由于p是素数且 k<p,若k>1, 则k!|(p-1) …(p-k+1);若k=1, 也有k!|(p-1) …(pk+1). 所以C(p,k)是p的倍数. 在等式(4.14)中,C(p,1)2+C(p,2)2+…+C(p,p-1)2一定是p的倍 数,而 C(p,0)2+C(p,p)2 =1+1=2 ,故当 p>2时, C(2p,p) 除以 p 的 余数是2.

§ 4. 2 组合恒等式及其含义

例4.4

? n ? ? 2? n ? ? ? ? n? n ? ? n ? ? 2n ? 1 ? ? 1? ? 2? ? n? ? n?1 ? ? ? ? ? ? ? ? ?

2

2

2

证明:
从n名女同学和n名男同学中,选出n名同学组 成一个社团,其中一人担任社团主席,且必须 由女同学担任,问有多少种选法?

? n ? ? k ?? n ?? n ? ? n ?? k ?? n ? k? ?k? ? ?? ? 1? ?? ?k? ?? ?n? k? ??? ?k? ?? ? 1? ?? ?n? k? ? ? ? ? ?? ?? ? ? ?? ?? ?

2

§4.3 例 §非降路径问题引 4.3 非降路径问题
Y 非降路径问题 引例、非降路径问题从 (0,0) 点 出发沿 X 轴或 Y 轴的正方向每步 走一个单位,最终走到 (m,n) 点, 有多少条路径? ≈ (m-1,n)(m,n) (m,n-1) ≈ ≈ … ≈ (0,0) X

解:设从(0,0)点水平方向向前进一步为 x,垂直方向向上进一步 为 y 。于是从 (0,0) 点到 (m,n) 点,水平方向走 m 步,垂直方向走 n 步。一条从(0,0)点到(m,n)点的非降路径与重集 {m*x,n*y}的一个 全排列一一对应,故所求非降路径数为(m+n)!/(m!n!)=C(m+n,m)。 另外,垂直方向需要走n步,相当于在X轴0,1,…,m共m+1个端点 处重复的选择n个位置向上走,与一条从(0,0)点到(m,n)点的非降 路径一一对应,故所求非降路径数为F(m+1,n)=C(m+n,n)。 多重集S={∞*a1, ∞*a2, … , ∞*ak} 的r?组合数F(k,r) = C(k+r-1, r)

§4.3 非降路径问题例 2 § 4.3 非降路径问题

非降路径问题 例 2 、非降路径问题从 (0,0) 点出 发沿 X 轴或 Y 轴的正方向每步走 一个单位,最终走到 (m,n) 点, 有多少条路径?

Y

(m-1,n)(m,n) (m,n-1) ≈





… ≈

(0,0)

X

由引例,我们已经知道,从 (0,0) 点到 (m,n) 点的非降路径数 就是组合数 C(m+n,m), 而且从 (0,0) 点到 (m,n) 点的非降路径数等 于从(0,0)点到(n,m) 点的非降路径数,即C(m+n,m)= C(m+n,n). 另外,一条从(0,0)点到(m,n)点的路径可分为两类情况,一种 是从 (0,0) 点到 (m,n-1) 点的非降路径,另一种是从 (0,0) 点到 (m1,n-1)点的非降路径,根据上述结论,有 C(m+n,n)=C(m+n-1,m)+C(m+n-1,m-1) 这是Pascal公式的另一种形式。

§ 4.3 非降路径问题
格路问题 Y (n,r)(n+1,r) ≈

§4.3 非降路径问题例3

例3、如n,r∈N,有 C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1) +…+C(n+1,1)+C(n,0)








(0,0) (n,0) X 证明:这是上一小节的组合恒等式。等式左端表示从 (0,0) 点到 (n+1,r) 点的非降路径数,右端第 1项表示从 (0,0) 点到(n,r) 点的路 径数,右端第 2 项表示从 (0,0) 点到 (n,r-1) 点的非降路径数, … , 右端最后1项表示从(0,0)点到(n,0)点的非降路径数。 这 说 明 从 (0,0) 点 到 (n+1,r) 点 的 非 降 路 径 根 据 是 否 经 过 (n,i) 到 (n+1,i)(i= 0,1,…,r),可分为r+1类,根据加法法则即可得证。

§ 4.3 非降路径问题
非降路径问题 例4、如n∈N,有 C(n,0)+C(n,1)+…+C(n,n)=2n Y P(0,n) P1(1,n-1)

§4.3 非降路径问题例4

≈ … ≈ ≈

X (0,0) Q(n,0) 组合含义:这是推论4.1.3。等式左端第1项表示从(0,0)点到P(0,n) 点的非降路径数,第 2项表示从 (0,0) 点到 P1(1,n-1) 点的非降路径 数,…,左端最后1项表示从(0,0)点到Q(n,0)点的非降路径数。 这说明从 (0,0) 点到 PQ上各格子点的非降路径总和为 2n。也说明 2n个人从(0,0)点出发,每到一个十字路口便分成两组,直至到达 PQ线为止,能保证每个人所走的非降路径不同。

§ 4.3非降路径问题
非降路径问题 例5、Vandermonde恒等式 如n,m∈N,r≤min(m,n),有 C(m+n,r)=C(m,0)C(n,r) +C(m,1)C(n,r-1) +…+C(m,r)C(n,0) Y P(m-r,r) (m+n-r,r) ≈

§4.3 非降路径问题例5



(m-l,l) …




(0,0) Q(m,0) X 证明:等式左端表示从 (0,0) 点到 (m+n-r,r) 点的非降路径数。从 (0,0) 点到 (m+n-r,r) 点的每一条路径均穿过 PQ 线上的格子点 (ml,l),l=0,1,…,r,从(0,0)点到(m-l,l)点的非降路径数为C(m,l),再从 (m-l,l)点到(m+n-r,r)点的非降路径数为C(n,r-l),由乘法法则,从 (0,0) 点 出 发 经 过 (m-l,l) 点 到 (m+n-r,r) 点 的 非 降 路 径 数 为 C(m,l)C(n,r-l),再由加法法则,即可得证。

§4.3 非降路径问题例6-1

§ 4.3 非降路径问题
Y



非降路径问题 例6、求从(0,0)点到(n,n)点 的除端点外不接触直线y=x 的非降路径数?

A

(n,n) (n,n-1)


≈ (0,1)

… ≈

(0,0 ) (1,0) Q(n,0) X 解:先考虑对角线下方的路径. 这种路径都是从(0,0)点出发经过 (1,0)点及 (n,n-1)点到达(n,n)的. 我们可以把它看作是从 (1,0)点出 发到达(n,n-1)点的不接触对角线的非降路径. 从(1,0)点到达(n,n-1)点的所有的非降路径数是 C(2n-2,n-1),对 其中的任意一条接触对角线的路径,我们可以把它从最后离开 对角线的点(如A点)到(1,0)点之间的部分关于对角线作一个反 射,就得到一条从(0,1)点出发经过A点到达(n,n-1)点的非降路径.

§ 4.3 非降路径问题 § 4.3 非降路径问题 例6-2
非降路径问题

例6、求从(0,0)点到(n,n)点的除端点外 不接触直线y=x的非降路径数?

反之,任何一条从 (0,1)点出发,穿过对角 线而到达 (n,n-1) 点的非降路径,也可以通过 这样的反射对应到一条从 (1,0) 点出发接触到 对角线而到达(n,n-1)点的非降路径. 从(0,1)点 到达 (n,n-1) 点的非降路径数是 C(2n-2,n) ,从 而在对角线下方的路径数是 C(2n-2,n-1)-C(2n2,n). 由对称性可知,所求的路径数是 2 [C(2n-2,n-1)-C(2n-2,n)] =2C(2n-2,n-1)/n =C(2n,n)/(2n-1).

§ 4.3 非降路径问题
非降路径问题 例6、求从(0,0)点到(n,n)点的除端点外 不穿过直线y=x的非降路径数?
(-1,1)

y P

(n,n)

O (0,0)

x

解:采用分类处理的方法。 将所有从(0,0)点到(n,n)的非降路径分成两类:穿过对角线的与 不穿过对角线的。只要求出穿过对角线的路径数 N1,那么从总数 中减去N1就得到所求的路径条数。 任何一条从 (0,0) 点到 (n,n) 的穿过对角线的路径一定要接触直 线y=x+1,有可能接触多次,但最后离开这条直线上的一点P,沿直 线y=x+1下方的一条非降路径到达(n,n)点。把这条路径的前半段, 即(0,0)点到P点的部分,以直线y=x+1为轴进行翻转,生成一段新 的从 (-1,1) 点到 P点的部分非降路径。用这段新路径替换原来路径 的前半段,就得到一条从(-1,1)点到(n,n)点非降路径.而这种路径与 从中间穿过对角线的非降路径之间是一一对应的。因此,从点(0,0) 点到(n,n)的穿过对角线的非降路径数N1=C(2n,n-1)。

§ 4.3 非降路径问题
非降路径问题 例6、求从(0,0)点到(n,n)点的除端点外 不穿过直线y=x的非降路径数?
(-1,1)

y P

(n,n)

O (0,0)

x

从点(0,0)点到(n,n)的非降路径总数为C(2n,n)条,从而得到 不穿过对角线的非降路径数是 N=C(2n,n)-C(2n,n-1)=

1 ? 2n ? ? ? ? ? n ?1? n ?

§4.3 非降路径问题例7-1

§ 4.3 非降路径问题

非降路径问题

例7、求集合{1,2, … ,n}上 的单调递增函数的个数.

解:任给集合 {1,2,…,n} 上的一个单调递增函数,我 们可以作一条对应的折线. 以横坐标代表x, 纵坐标代 表 f(x), 在 图 中 可 以 得 到 n 个 格 点 : (1, f(1)),(2, f(x)),…,(n, f(n)). 从(1,1)点出发向上作连线到(1, f(1)) 点 . 如果 f(2)=f(1), 则继续向右连线到 (2, f(2)); 如果 f(2)>f(1), 则由(1, f(1))点向右经过(2, f(1))再向上连线 到(2, f(2))点. 按照这种方法一直将折线连到(n, f(n))点.

§4.3 非降路径问题例7-2

§ 4.3 非降路径问题

非降路径问题

例7、求集合{1,2, … ,n}上 的单调递增函数的个数.

解:若f(n)=n,就将折线向右连到(n+1,n)点,若f(n)<n,

则向右经(n+1, f(n))点再向上到(n+1,n)点。这样就得 到一条从(1,1)点到(n+1,n)点的非降路径。 不难看出,所求的单调递增函数与这种非降路径 之间存在着一一对应,因此集合 {1,2,…,n} 上的单调 函数有C(2n-1,n)个.

§4.3 非降路径问题例8-1

§ 4.3 非降路径问题
Y



非降路径问题 例8、从(0,0)点到(m,n)点 (m≥n)的,要求中间经过 的每一个格子点(a,b)恒满 足a>b关系,问有多少条 路径?

(m,n)
≈ … ≈ ≈

(0,1)

(0,0 ) (1,0) Q(m,0) X 解:从(0,0)点到(m,n) 点的路径数为 C(m+n,m),但需要排除碰到 或穿过y=x格子点的路径数,即去掉a≤b的情况。第一步必须从 (0,0)点到(1,0)点,因此问题等价于求从(1,0)点到(m,n)点的路径数。 因为 m≥n ,故从 (0,1) 点到 (m,n) 点的路径必然穿过 y=x 上的格子 点。下面建立从 (0,1) 点到 (m,n) 点的每一条路径,与从 (1,0) 点到 (m,n)点但经过y=x上的格子点的路径时一一对应的。

§4.3 非降路径问题例8-2

§ 4.3 非降路径问题
Y



非降路径问题 例8、从(0,0)点到(m,n)点 (m≥n)的,要求中间经过 的每一个格子点(a,b)恒满 足a>b关系,问有多少条 路径?

(m,n)
≈ … ≈ ≈

(0,1)

y=)x(1,0) 若从 (0,1) 点到 (m,n) 点的路径与 的交点从左往右数最后一 (0,0 Q(m,0) X 个是P,作从(1,0)点到P点关于y=x的与上述(0,1)点到P点的路径对 称的一条路径,于是从(0,1)点到(m,n)点的一条路径,就有一条从 (1,0)点到 (m,n)点但经过 y=x上的格子点的路径与之对应。反之, 一条从 (1,0)点到(m,n)点但经过y=x上的格子点的路径,必存在一 条从(0,1)点到(m,n)点的一条路径与之对应。 故所求的路径数为 C(m+n-1,n)-C(m+n-1,n-1)=(m-n)(m+n-1)!/(m!n!)

§4.4牛顿二项式定理

§4.4 牛顿二项式定理

定义 4.1

?)

广义二项式系数 C (? , k ) 为: ?? ? R, ?k ? Z , ?? (? ? 1)...(? ? k ? 1) / k ! k ? 0 ? ?? 1 k ?0 ? k 0 k ?0 ? ?

定理 4.2

牛顿二项式定理: ? ? 如?? ? R,| x y | ? 1, 有( x ? y ) ? ? ? x k y? ? k k k ?0

?)

牛顿

§4.4 牛顿二项式定理恒等式
恒等式(4.15): §4.4 牛顿二项式定理

? r ? r ? r ? 1? ? ?k ? ?? k? ? k ? 1? ? (k为整数,k ? 0,r为实数) ? ? ? ?
恒等式(4.16):

? r ? ? r ? 1? ? r ? 1 ? ? ?k ? ??? ? k ? ??? ? k ? 1? ? (k为整数,r为实数) ? ? ? ? ? ? 恒等式(4.17):

? r ?? m ? ? r ?? r ? k ? ? ? m? ?? ?k? ??? ?k ? ?? ?m ? k ? ? (k , m为整数,r为实数) ? ?? ? ? ?? ?

§4.4 牛顿二项式定理 §4.4 牛顿二项式定理恒等式
如? ? R, k ? Z 且k ? 0,有? C (? ? j , j ) ? C (? ? k ? 1, k ) 恒等式(4.18):
j ?0 k

证明:注意,这个恒等式与前面的有一个很不一样的地方,就 是 C(α+j,j),C(α+k+1,k) 是广义的二项式系数。根据广义的二项式 系数的定义,Pascal公式C(α,k)=C(α-1,k)+C(α-1,k-1)对实数α和整 数k同样成立。与恒等式1类似,反复使用Pascal公式即可得证。

§4.4 牛顿二项式定理推论1 六个推论 推论4.2.1: 推论4.2.2: 证明:

§4.1 牛顿二项式定理
?

?|z| ? 1, 有(1 ? z )? ? ? ? z k k k ?0
?

?)

?|z| ? 1, 有(1 ? z )? n ? ? ( ?1)k n ? k ? 1 z k (4.19) k k ?0
? ? n( ? n ? 1)...( ? n ? k ? 1) k ? n k ?? z ?? z k k! k ?0 k ?0 ? ( ?1)k n( n ? 1)...( n ? k ? 1) k ?? z k! k ?0 ? ? ? ( ?1)k n ? k ? 1 z k k k ?0 ?

(1 ? z )

?n

? )

?

)

?

)

§4.4牛顿二项式定理推论2 六个推论

§4.1 牛顿二项式定理
?

推论1.10.1: ?|z| ? 1, 有(1 ? z )? ? ? ? z k k k ?0 ? k>0,有 证明:当α=1/2时,C(α,0)=1,而对于 ?n k n ? k ?1 k (4.19) | z | ? 1, 有 (1 ? z ) ? ( ? 1) z 推论1.10.2: ? ? ? 1) k ? ? 1 2 (1 2 ? 1)...(1 2 ?kk ?0 ? k k ! ?1 k k (4.20) 推论1.10.3: ?|z| ? 1, k ?1 有 (1 ? z ) ? ( ? 1) z ? ( ?1) 1 ? 3 ? ... ? (2k ? 3) k ?0 ? ? ? k 2 ?1 k ! k k ?1 |z | ? 1, 有 (1 ? z ) ? z 推论1.10.4: ?( (4.21) ?1) 1 ? 2 ? 3 ?? 4 ? ... ? (2k ? 3) ? (2 k ? 2) k ?0 ? ? k ?1 ? k ( ? 1) 2 21 ?? 4 ? ... ? (2k ? 2) ?? k2 ! zk 2k ? | z | ? 1, 有 1 ? z ? (4.22) 推论1.10.5: k ?1 ? 2 k ?1 k ? 1 ( ?1) (2k ? 2)!k ?1 k ? 2 ? ? 2 k ?1 k?2 (( k ? 1)!)2 ( ?1)k ?1 2k ? 2 ? ? k ?1 k ? 2 2 k ?1 将上式代入推论4.2.1即可得证。

?)

?)

?

)

?

)

?

)

§4.4 牛顿二项式定理推论3 六个推论 推论4.2.1: 推论4.2.2: 推论4.2.3:

§4. 1 牛顿二项式定理
?

?|z| ? 1, 有(1 ? z )? ? ? ? z k k k ?0
? ?

?)

?|z| ? 1, 有(1 ? z )? n ? ? ( ?1)k n ? k ? 1 z k k k ?0
?1 k ?0 ?

?

)

(4.19) (4.20) (4.21)

?|z| ? 1, 有(1 ? z ) ? ? ( ?1)k z k ?|z| ? 1, 有(1 ? z )?1 ? ? z k
k ?0 ?

推论4.2.4:
推论4.2.5: 推论4.2.6:

( ?1)k ?1 2k ? 2 k ?|z| ? 1, 有 1 ? z ? 1 ? ? z (4.22) 2 k ?1 k ? 1 k ?1 k ? 2 ?|rz| ? 1,即|z| ? 1 |r |, r是非0常数,有 ? ?n (1 ? rz ) ? ? n ? k ? 1 r k z k k k ?0

?

)

?

)

§ 4.5 多项式定理
§4.5多项式定理 ? 定理4.3(多项式定理)设 n是正整数,则对一 切实数x1, x2, …, xt有

?x1 ? x2 ? ? ? xt )

n

n! n1 n2 nt ? x1 x2 ? xt ? ?n2 !? nt ! n1 ? n2 ??? nt ? n n1 !

n ? ? n1 n2 nt ? ? ? ? ? n n ? n ?x1 x2 ? xt n1 ? n2 ??? nt ? n ? 1 2 t?

§ 4.5 多项式定理

多项式定理证明
对于n个因子中的每一个,选取 m 个数x1, x2,…,xt中的一 个并形成乘积。 用这种方法得到的结果共有t n项,并且每一项都可以写 成 x n1 x n2 ...x nt 的形式,其中n1,,n2,,…,nt是非负数,且其 1 2 t 和为n。 通过选择n个因子中的n1个为x1,剩下的n-n1个因子中的 n2个为x2,…,剩下的n-n1-…-…-nt-1个因子中的nt个为xt,得到

x x ...x

n1 n2 1 2

nt t

项。

由乘法原理得到该项出现的次数为
? n ?? n ? n1 ? ? n ? n1 ? ... ? nt ?1 ? n! ? ? ? ? ? ? ? ? ? n ?? n ? ? ? n !?n !?? n ! n t ? 1 ?? 2 ? ? ? 1 2 t

§ 4.5 多项式定理

有多少个不同的乘积项 ? §4.5多项式定理

乘积项的系数和是多少? n t n 推论1 ?x1 ? x2 ? ? ? xt ) 的展开式在合并同类项
n ? t ? 1? 以后不同的项数是 ? ? ? ? ? n ? ?

? t ? n ? 1? ? ? n ? ? ? ?

证明:?x1 ? x2 ? ? ? xt ) n 的展开式中每一项都可以写 成 x n1 x n2 ...x nt 的形式,其中n1+n2+…+nt = n. 每一项 1 2 t 对应于该方程的一组非负整数解,所以合并同类项后不 n ? t ? 1? 同的项数等于这个方程的非负整数解的个数 ? ? ? 推论2 一切非负整数解求和.
n ? ? n ? ? ?n n ?n ? ??t n1 ? n2 ??? nt ? n ? 1 2 t?

,其中求和是对方程的

? ?

n

? ?

证明: 在多项式定理中令 x1 ? x2 ? ? ? xt ? 1 即可.

§ 4.5 多项式定理
n § ? ? 4.5多项式定理 ? ? 多项式系数 ? 的组合意义: ? ? n1 n2 ? nt ?

1. 它是多项式 ?x1 ? x2 ? ? ? xt ) 中 x x ...x 项的 系数; 2. 它是多重集合S={n1· a1+n2· a2+…+nt· at}的排列数; 3.如果我们把n个不同的球放到t个不同的盒子里并 且使得第一个盒子里有n1个球,第二个盒子里 有n2个球,…,第t个盒子里有nt个球,那么放 球的方案数是 .
n

n1 n2 1 2

nt t

n ? ? ? ? n n ?n ? ? t ? ? 1 2

§ 4.5 多项式定理 § 4.5 多项式定理

? 例4.6 在 (2x-3y+5z)6 的展开式中,x3yz2 项的系数是多少? ? 解: ? 6 ? 3 2
? ?3 1 2? ? ? 2 ? ?? 3) ? ?5) ? ? 6! 2 3 ? ? 2 ? ?? 3) ? ?5) 3!2! ? ?36000.

§ 4.5 多项式定理
例4.7 试用组合学论证法证明恒等式
n n ?1 n ?1 n ?1 ? ? ? ? ? ? ? ? ? ? n n ?n ? ??? ? n ?1 n ?n ? ??? ? n n - 1? n ? ? ??? ? ? n n ? n - 1? ? t? 2 t? ? 1 2 t? t ? 1 2 ? 1 ? 1 2 ? 证明:左边是把n个不同的球放到t个不同的盒子里并且使得 第一个盒子里有n1个球,第二个盒子里有n2个球,…,第t个 盒子里有nt个球的方案数. 任取一个球n1 ,然后把放球的方 法进行分类:
n ?1 ? ? a1放到第一个盒子的放法数是 ? ? n ? 1 n ...n ? ? ; 2 t? ? 1 n ?1 ? ? a1放到第二个盒子的放法数是 ? ? n n ? 1...n ? ? ; t? ? 1 2 …… n ?1 ? ? a1放到t第二个盒子的放法数是 ? ? n n ...n ? 1? ? . ? 1 2 t ?
§4.5多项式定理

由加法法则等式得证.

§基本组合计数的应用 4.6基本组合计数的应用 § 4.6

例1某保密装置须同时使用若干把不同的 钥匙才能打开。现有7人,每人持若干 钥匙。须4人到场,所备钥匙才能开锁。 问①至少有多少把不同的钥匙?②每人 至少持几把钥匙?

4.6基本组合计数的应用 § 4.6§ 基本组合计数的应用

解:①每3人至少缺1把钥匙,且每3人所 ? 7? ? =35把不同 缺钥匙不同。故至少共有 ? 3 ? ? 的钥匙。 任一人对于其他6人中的每3人,都 至少有1把钥匙与之相配才能开锁。故 ? 6? 每人至少持 ? ? =20把不同的钥匙。 3 ? ? 为加深理解,举一个较简单的例子:4人 ? 4? 中3人到场,所求如上。共有 ?? 2 ?? =6把不 ? 3? 同的钥匙。每人有 ?? 2 ?? =3把钥匙。

§ 4.6 基本组合计数的应用

钥匙 1 A B √ 2 √ √ √ √ √ 3 √ √ √ √ √ √ 4 5 6


C D

§4.6 基本组合计数的应用 § 4.6 基本组合计数的应用

例2 脱氧核糖核酸(DNA)的分子由A(腺嘌呤),G(鸟 嘌呤),C(胞嘧啶)和T(胸腺嘧啶)4种碱基核糖核苷 酸,以不同数目和种类排列成两条多核苷酸单链, 这两条单链之间通过氢键把配对的碱基连接起来, 形成双螺旋结构。连接过程总是A和T配对,G和 C配对。显然长度为n的核苷酸链共有4n 种不同 方式。 生物遗传信息是由DNA分子中4个碱基核苷 酸象电报密码似的以不同的排列顺序记录下来, 它载着人类的全部基因或全部遗传信息。所谓基 因就是DNA上一小段, 平均长度为900-1500个碱 基对。人的DNA约有3×109 碱基对。核糖核酸 (RNA)也是一种遗传物质,它是由A,G,C,U(尿嘧 啶)4种碱基核苷酸排列而成的多核苷酸单链。

§4.6 基本组合计数的应用 § 4.6 基本组合计数的应用

通过基因将它的遗传信息传递给RNA,然 后再传给蛋白质来表现其功能。 (1)蛋白质分子中有20种氨基酸,在RNA 中以一定顺序相连的3个核苷酸决定1种氨 基酸,三联体遗传密码有43=64个排列方式。 它保证了20种氨基酸密码的需要。 (2)例如RNA链:CCGGUCCGAAAG 酶 将它分解成为G片断(即利用G将RNA分解)。 CCG,G,UCCG,AAAG.

§4.6 基本组合计数的应用 § 4.6 基本组合计数的应用

显然有4!=24种不同的RNA链有与此相同的G 片段。 若利用U,C酶将上述的RNA链分解成U,C 片段:C,C,GGU,C,C,GAAAG 由于GAAAG片段 只能在最后出现,而且C出现4次,故有C(5,4)=5 种不同的核苷酸链,它的U,C片段是上述的 C,C,C,C,GGU, GAAAG,它们是 CCCCGGUGAAAG CCCGGUCGAAAG CCGGUCCGAAAG CGGUCCCGAAAG GGUCCCCGAAAG.

§4.6 基本组合计数的应用 § 4.6 基本组合计数的应用

例题3 Ipv4协议的网址计数 Ipv4协议网址计数: 32 位地址(w.x.y.z):网络标识+主机 标识 A类:最大网络;B类:中等网络;C:最小网络;D类:多 路广播;E类:备用限制条件:1111111 在A 类中的网络标 识部分无效,主机标识部分不允许全0或全1

A 类: netid 27?1, hostid 224?2 , 地址数: 127 * 16777214 B 类: netid 214, hostid 216?2 , 地址数: 16384 * 65534 C 类: netid 221, hostid 28?2 , 地址数: 2097152 * 254 Ipv4协议网址总数= 2130706178+1073709056+532676608 = 3737091842

第4章 习题

习 题

P22
14、16、20、22。

结束

谢 谢



更多相关文章:
题目a93614d4b14e852458fb57e1
帮助去网页搜索 全部 DOC PPT TXT PDF XLS 首页分类教育文库精品文库 学术专区...填空题 数学 排列与组合、二项式定理与性质 已知的展开式中,二项式系数最大的...
更多相关标签:
二项式系数    二项式系数之和    二项式系数和    二项式系数的性质    二项式系数公式    二项式系数怎么求    二项式各项系数之和    二项式系数最大的项    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图