离散数学是计算机专业基础课程之一。本课程重点讲解离散对象的计数问题、图论问题、网络流问题等计算机科学中的重要基本知识。本课程将为后续如数据结构、算法设计、复杂性理论提供必要的基础，课程内容在人工智能、机器学习、网络设计与分析等前沿领域有重要应用。课程重点培养学生逻辑思维能力及解决问题的能力。
估值实例
Loading...
From the course by Shanghai Jiao Tong University
离散数学
14 ratings
Meet the Instructors
Long Huan 龙环助理研究员
计算机系
[音乐]
[音乐] [音乐]
各位 大家好，本次我们继续讲解有关估值的定理和性质
这次我们讲解的是阶乘估值以及二项式系数估值。
回忆一下什么是阶乘 n 的阶乘定义为 n 乘以 n-1 一直乘到
1 这样一个连续的乘法 阶乘的一个实际应用是，我们如果已知一个
有限集合的大小为 n，那么关于这个集合上的置换正好是 n 的阶乘个 那么我们现在想对
n 的阶乘的具体的值大小 有一个估计，首先是最简单的方法，我们用极值估计法
我们同时估计上界和下界 我们说当 n 大于等于 2
的时候，因为是连续的 n 个数相乘，而每个数都小于等于 n
大于等于 2 的，注意我们在分析下界的时候，我们是从 i=2
开始的 那么上界我们说，连续
的 n 个 n 相乘的话，就是 n 的n 次方，而下界，当
i 从 2 到 n 的时候，显然是 2 的 n-1 次方
当然这是一个相当粗糙的界，我们希望对这个估计做 改进。
改进的可能有两种，第一个我们希望降低上界，第二个希望提高下界 我们仍然是使用极值点估计方法，只不过这个
时候我们把对原始问题的那个分析，变得稍微更精细一点 首先以上界为例，我们不再把所有的
乘项的上界都设成 n 前一半，1 到 n/2
的上界是 n/2 而后一半的上界，也就是 i 从（n+1）/2
到 n 的时候，我们取上界 n 这个时候我们得到一个新的上界，它是
n 除以根号 2 的 n 次方 显然这是一个比原来的上界，n 的 n
次方要好的一个上界，因为它比原来的上界要小 我们再看下界。
我们下界也不再单纯地使用 2 作为下界
我们只使用，注意我们现在连乘的范围是从 i=1
变成了 i=（n+1）/2 开始相乘
当然我们既然只考虑了后一半数的相乘的话，那么后一半数中间最小的那个 是 i，是一个 i。
那么我们说，这个值它是 大于什么呢？是大于
n/2 的连续的后一半的相乘 这样我们就得到了一个新的下界，它是根号
n/2 的 括号 n 次方，它比原来的下界，2 的
n 次方要好非常多 我们看一下，改进的上下界会给我们带来什么好处呢？
我们考虑这样一个问题，我们用大 F 表示所有的从 n 到
n 的函数 当然我们知道，这样大 F 的大小，一共是
n 的 n 次方个 然后我们想问的是，任意取一个函数 g，g
函数是单射函数的概率是多少？ 那么我们知道，任何一个单函数
是单射函数，把它放在一起的话，这个集合的大小正好是 n 的阶乘
既然我们是求概率，我们也就是想求 n 的阶乘除以 n
的 n 次方的比值 这个时候 n 的阶乘我们用我们新得到的这个上界，n
除以根号 2 的括号 n 次方 我们把这个式子简化，就得到 2
的负的二分之 n 次方 大家注意，这个界，如果我们用原来的这个
n 的 n 次方的这个界的话，是得不到 2 的负的二分之 n 次方这个结果的
而 2 的，负的二分之 n 次方在很多时候也够用了 因为显然随着
n 的增大，我们抽取到一个函数它是单射函数的概率
迅速下降，换句话说，比如说我们说当 n 为 10
的时候，你随便抽取这样一个函数 几乎它是正好是单射函数的可能性就已经非常之小了
好了，我们希望进一步改进对阶乘的估计
这里呢，我们表示出了我们原来，就刚刚得到的这两个下界和上界 首先我们希望降低上界。
我们为了 改进上下界，一般来说会用到新的一些数学公式，尤其是一些不等式
这个时候为了改进上界，我们用到的一个不等式呢，是算术几何不等式 它说对任意的实数
x，y，必有根号 xy 小于等于（x+y）/2，当
x 和 y 都为正数的时候 那么我们怎么样用这个来改进上界呢？
我们说 n 的阶乘，当然我们知道是 1 到 n
的乘积 那么我们可以把这个阶乘按照从小到大乘的顺序
写下来，也可以按照从大到小相乘的顺序写下来 那么 n！
显然等于 n！的平方开根号 所以我们不妨写成根号
n！×n！ 这个时候是好处是什么呢？我们可以把
n！的两种 表达式中的每一项一一配对起来，我们把 1 和
n 配对起来 2 和 n-1 配对起来，类似的我们把 n 和最后的这个
1 配对起来 也就是说我们得到了图中这里 的这样一个表达式。
这个时候我们就可以使用算数 几何均值不等式。
因为 我们说，中间的这一项，根号中的这一项，是小于等于
两分之 i 加上 n+1-i，也就是二分之 n+1
的 那么这样我们就整理之后得到一个新的上界，是（n+1）/2
的括号 n 次方 它是比原来的界要更小的一个上界
好了我们把上界改进了之后 我们又希望进一步改进下界。
我们说了，下界的改进就是希望把它提高一点 这个时候，前面的分析和我们改进上界的分析是一样的
但是为了改进下界，我们需要用到一个新的不等式 这个不等式是说，当
i=1，一直到 n 中的某一个值的时候 那么有 i
乘以（n+1-i）的积是大于等于 n 的 这个不等式非常容易验证。
这个不等式虽然简单，但是它确实能够帮助我们有效地改进下界 我们说，在这里出现了
i（n+1-i） 我们把它改成 n ，我们把它改成这里的
n 然后整理之后，我们得到新的下界，是 n 的二分之 n
次方 这是一个比原来的下界要大的一个下界，所以它是一个更好的一个下界
好了，我们想对问题作进一步优化。
我们这里 先列出了我们前面得到的上下界。
那么我们进一步优化 是什么做呢？我们这里要用到一个新的
常量，是所谓的欧拉数 也是一个无理数，它等于
2.7182 等 关于欧拉数有这样的一个不等式
它说 1+x 是小于等于 ex，这对任意的 x
都成立 我们在图中画出了 1+x 的 函数曲线和
ex 的那个函数曲线 大家可以看到，黑色这条是
ex 而下面的蓝色是 1+x，显然，ex 是始终 是在 1+x
这条曲线的上方，所以不等式成立 那么我们怎么样用它来改进上下界呢？
而且我们说，我们最后要得到的上界和下界 是我们这里说的 n！是小于
en 再乘以 （n/e）的 n 次方，以及大于 e 再乘以 n 除以 e 的 n次方。
我们首先看一下怎么样得到上界 上下界我们都会使用归纳法。
我们对 n 做归纳，当 n=1 的时候 我们说显然
1 大于 1！，不等式平凡成立 第二个说，当
n=k 的时候，我们假设，结论仍然成立 那么我们需要证
n=k+1 的时候结论成立，这个怎么样做呢？ 我们把 n！写成 n
乘以（n-1）！ 这个时候对（n-1）！我们就可以用我们的归纳假设的结论
它说 是（n-1）！是小于等于
e 乘以（n-1）再乘以（n-1）/e 的（n-1）次方
那么我们把右边，这个等式右边 不等式右边整理一下，我们得到红色和绿色的
两块，大家注意一下，红色这块其实就是我们想要证的结论 也就是我们想要证的，就是
n！是小于等于 en 再乘以 n 除以 e 的 n 次方，那么我们只要能够证明绿色的这一块是小于
1 的，就是我们能够证明这一块 是小于等于 1 的话，那么我们的结论就出来了。
那么怎么样证明它小于等于 1 呢？ 这个时候就要用到我们刚才所说的那个
基本不等式，也就是说，我们在这里用黄色高亮的这个不等式 1+x 小于等于 ex。
那么我们把 绿色的中间的 n-1 除以 n，重新写成
1 减去 1/n 那么我们用这个基本不等式就得到
这块是小于等于 e 的 -1 的除以
n，整理以后就得到 最后这个绿色这一块确实是小于等于
1 由此我们证明了这个新的上界，这个新的上界可以验证，它比
刚才我们得到的那个上界要小，是一个更好的上界 好了，我们接下来想要研究一下下界
下界的证明方法我们刚才说了，也是用归纳法 当
n=1 的时候，结论是成立的 接着我们假设当 n=k
的时候，这个不等式也成立 那当 n=k+1 的时候，我们怎么做呢？
n=k+1 的时候是类似的，我们把 n 的阶乘写成 n
乘以 n-1 的阶乘 那么 n-1 的阶乘，那其实也就是 k
这一块，它其实是满足我们的归纳 条件，那么我们说应该有归纳
步骤的那个不等式成立，所以说有蓝色标注的这两块成立 那么我们同样把右边这红色这一块重新整理
得到了下面的这两部分，一个是 e 乘以 n/e 的 n
次方，另外一块是 e 乘以 n-1 的 n，再 n-1 次方。
那么我们现在既然是要证明下界 所以我们只需要证明新的这一块绿色的部分
它是大于等于 e，那么我们的结论就成立 好了，我们从新翻一页，用它来，我们现在集中证明这一块是大于等于
1 我们还是要使用基本不等式，但是这个时候呢，要小心一点，我们要对式子做一点重写
注意到我们把指数上的 n-1 重写成了
1-n 这样的好处是，最后的不等式的方向是我们所需要用到的那个不等式方向
那么我们把 n 除以 n-1 重写成 1 加上 1/n-1
接着就是按照之前的，直接使用基本不等式，1 加上 x 的小于等于
1x，这个时候的 x 呢就是 1/n-1
这一块 所以这里为什么是大于等于，这是因为上一步中间这里是一个
-1的符号 -1 的符号，所以这里原始的基本不等式的小于等于，在有了取了一次倒数之后，它会变成大于等于
而这一块正好就是 e，那么就得到了我们所想求的，也就是说 n 的阶乘
是大于等于我们所，我们的目标项再乘以一个 e
那么这个显然就有 n 的阶乘是大于等于我们的目标项 这样一个结论。
关于 n 的阶乘大家会问，是否有进一步的改进？确实是有的
而最好的结论是 Stirling 公式，它说 n 的阶乘跟 根号 2πn 再乘以
n/e 的 n 次方，它们是近似相等的 换句话说，当 n
趋于无穷的时候，这两个项是等于 1 的 这个 Stirling
公式的介绍呢，就不在本课中介绍了 现在我们有了
n 的阶乘的估计，我们接下来要介绍的是二项式公式的估计
二项式系数大家回忆一下，它的定义是什么？它有一些相等的 定义，最后一个我们大家可能最熟悉的就是
n 的阶乘除以 k 的阶乘再乘以 n-k 的阶乘。
我们现在想估计它的值 一个最自然的办法，就是说我们刚刚已经提了，因为有 Stirling
公式 Stirling 公式我们已经有了 n 阶乘的这样一个渐进相等的这样一个表示
那么我们只需要用 Stirling 公式对 n
的阶乘做一个表示，然后对 k 的阶乘 n-k 的阶乘都用
Stirling 公式的话，那么我们应该能够得到二项式系数的这样一个 一个表达。
但是这个因为它使用到了一些比较复杂的，比如说根号啊或者
是一些无理数，我们会问，有没有在结论上不够完美，但是
相对表达是简单一些的估计方式？这里就是我们想要介绍的 首先我们看最简单的估值。
我们 说从 n 中间选 k，显然是小于等于 n 的 k
次方 因为我们说，注意的话，左边其实是不重复选择，而右边的话就是允许重复的选择
那么不允许重复当然是小于等于允许重复的选择总数 第二个，我们要用到一个
简单的观察，是说当 n 大于等于 k 大于 i 大于等于 0 的时候
n-i 除以 k-i 是大于等于 n-k，这个很容易验证
所以说，我们由，但是我们从这一块我们能够得到 n 选
k 的一个下界，一个 n 选 k 的下界，为什么呢？ 因为我们说
n 选 k 它有一个等式是连乘 n-i 除以 k-i，i 是从
0 到 k-1 那么我们把上面这个不等式带进来，它就得到 n 选 k
的 k 次方 这里我们想要对刚才的界做一个
改进，而且最有意思的一点呢，我们这里会要用到二项式定理，来对二项式系数做一个估值
回忆一下二项式定理，它是说对任意的非负整数 n，下面的
这个等式都成立，就是 1+x 的 n 次方等于 ∑ k 等于 0 到 n，n
中选 k x 的 k 次方，大家如果还记得的话，这也是为什么我们叫 n 选 k 叫做二项式系数。
好了，我们想要很巧妙地使用这个二项式定理 现在我们说，n
大于等于 1，k 是小于等于 n、 大于等于 1 的一个数，我们选择一点
注意，我们选的 x 是小于 1，大于 0 的一个实数 我们把
x 放进二项式定理里面，那么显然有 这里的第一行成立，就是左边的这些加起来等于 1+x
的 n 次方 所以我们把，因为这每一项都是正数
所以说我们只取前 k 项，这里是 x 的 k 次方，我们只取了
前面这一列的前 k 项的话，那么它一定是比原始等式的结果要小
因为我们省去了一些非负的值，那么它的结果不会变大 那么又
在上面这个等式两边，我们都除以 x 的 k 次方，就得到新的这一行
就是 1 除以 x 的 k 次方，n 选 0，再加上 1 除以 x 的 k-1 次方，n 选
1 最后小于等于 1 加上 x 的 n 次方除以 x 的 k 次方
这个显然成立的，我们知道，在不等式的两边除以一个正数的话 不会影响不等式的方向。
但是这个时候就要用到 x 是一个小于 1 大于 0 的一个 实数的这样一个性质。
因为 x 是小于 1 的，所以 我们知道，1 除以 xk 也好，1 除以 x k-1 也好 都是大于 1 的数。
换句话说，我们把前面这个式子中的系数去掉 我们会得到 n 中选
0，再加上 n 选 1，再一直加加加，加到 n 选 k，是小于等于 1 加上 x 的 n 次方除以
x 的 k 次方 好了，我们把刚才的结论在这里重新写一次
你要记住我们最后想找的界 是 n 选 k 的一个上界。
这个时候我们将要找上界，所以我们 x
现在又是一个变量，那么我们想要找一个 x 呢，使得 这个不等式的右边越小越好，这个时候我们选了
x=k/n 这个通过数学分析会证明，这是一个好的一个选择 我们把
x=k/n 代到上面的式子中，就有了
这个新的这一行的不等式成立 新的不等式中间又出现了
1 加上 k 除以 n 这就提示我们又可以使用基本不等式，1 加上
x 小于等于 ex，注意 1 加上 x 小于等于 ex 是对任意 x 都成立
所以我们可以重写这个不等式为 1 的 k 除以 n 次方的 n
次方，再乘以 n 除以 k 的 k 次方 那么整理一下，就得到 en/k 的
k 次方 那么这个时候就得到我们的结论了，因为我们说了，我们最后想找的是
n 选 k 的界 n 选 k 的界，那么 n 选 k 既然是这个连续的加中的一项，那么它一定是小于等于
右边这个连续的加的，它也就是小于等于它的上界
所以说我们得到了一个比我们一开始给的那个上界要好的一个上界
好了，本次我们讲了有关阶乘和二项式系数的估值，谢谢大家
[音乐]
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
