算法第四版练习答案 1.4.1

柔光的暖阳◎ 2022-03-17 04:17 280阅读 0赞

# 题目 #

证明从N个数中,取出3个整数的不同组合的总数为N(N-1)(N-2)/6  
提示 使用数学归纳法

# 分析 #

百度了下什么是数学归纳法:  
**数学归纳法**（Mathematical Induction, MI）  
是一种数学证明方法，通常被用于证明某个给定命题在整个（或者局部）自然数范围内成立  
**原理**  
最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步：  
证明当n= 1时命题成立。  
假设n=m时命题成立，那么可以推导出在n=m+1时命题也成立。（m代表任意自然数）  
这种方法的原理在于：首先证明在某个起点值时命题成立，然后证明从一个值到下一个值的过程有效。当这两点都已经证明，那么任意值都可以通过反复使用这个方法推导出来。把这个方法想成多米诺效应也许更容易理解一些。  
**例如**：你有一列很长的直立着的多米诺骨牌，如果你可以：  
证明第一张骨牌会倒。  
证明只要任意一张骨牌倒了，那么与其相邻的下一张骨牌也会倒。  
骨牌一个接一个倒下就如同一个值接下一个值  
骨牌一个接一个倒下就如同一个值接下一个值  
那么便可以下结论：所有的骨牌都会倒下  
**解题要点**  
数学归纳法对解题的形式要求严格，数学归纳法解题过程中，  
第一步：验证n取第一个自然数时成立  
第二步：假设n=k时成立，然后以验证的条件和假设的条件作为论证的依据进行推导，在接下来的推导过程中不能直接将n=k+1代入假设的原式中去。  
最后一步总结表述。

# 证明过程 #

证明1:数学归纳法

第一步:证明从N个数中,取出2个整数的不同组合的总数为N(N-1)2  
(1)假设n=2和n=3  
从2个整数中,取2个整数的总数只有1种,符合2*1/2=1  
从3个整数中,取2个整数的总数3种,3*2/2=3种,符合  
(2)假设a从N个整数中取出2个整数的不同组合的总数为N(N-1)2  
那么从N+1个整数中取出2个整数的不同组合的总数可以分成两部分  
一部分是从N个整数中取出2个整数的不同组合的总数为N(N-1)2  
另一部分是必须包含第N+1元素,另外一个元素可以随意取的情况(范围从1到N),那么这一部分的数量为N  
把上述两个部分相加得到  
从N+1个整数中取出2个整数的不同组合的总数为N(N-1)/2+N=N(N+1)/2  
(3)而假设二a中f(n)=n(n-1)/2;f(n+1)=(n+1)\*2/2  
上面两者是相等的,因此数学归纳法就可以得出证明从N个数中,取出2个整数的不同组合的总数为N(N-1)2

分割下

第二步:证明从N个数中,取出3个整数的不同组合的总数为N(N-1)(N-2)/6  
(1)假设N=3和N=4  
从3个整数中,取3个整数的总数只有1种,符合3*2*1/6=1  
从4个整数中,取3个整数的总数4种,符合4*3*2/6=4  
比如有数字1,2,3,4.那么只有4种可能(1,2,3);(1,2,4);(1,3,4);(2,3,4)  
(2)假设b从N个数中,取出3个整数的不同组合的总数为N(N-1)(N-2)/6  
那么从N+1个整数中取出3个整数的不同组合的总数可以分成两部分  
第一部分:不包含第N+1元素的,有f(n)即假设b…f(n)=N(N-1)(N-2)/6个  
第二部分:包含第N+1元素的,那么另外2个数只能从N个元素中取,即第一步我们证明的结论:**从N个数中,取出2个整数的不同组合的总数为N(N-1)2**  
把上述的一二部分相加N(N-1)(N-2)/6+N(N-1)/2=(N的三次方-N)/6  
(3)根据假设f(n)=N(N-1)(N-2)/6,那么  
f(n+1)=(N+1)*N*(N-1)/6,  
上面两者是相等的,因此数学归纳法就可以得出证明从N个数中,取出3个整数的不同组合的总数为N(N-1)(N-2)/6

证明方法2

区别  
Combine，组合，不分顺序，组合比排列所取得的种数更少。如5取3，C(5,3)=5!/(3!*(5-3)!)=5!/(3!2!)=(54*3)/(3*2*1)

Arrange，排列，区分顺序，因而排列比组合取得的种数更多。比如5取3。A(5,3)=5!/(5-3)!=5!/2!=5*4*3

公式：  
n>m,即从n中取m个

排列：A(n,m)=n!/(n-m)!  
组合：C(n,m)=n!/(m!\*(n-m)!) 即C(n,m)=A(n,m)/m!  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]: /images/20220317/212b9f4291694ed88406e1c2d393f8bb.png