[音乐]
[音乐] [音乐]
各位 大家好,本次我们继续讲解有关估值的定理和性质
这次我们讲解的是阶乘估值以及二项式系数估值。
回忆一下什么是阶乘 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 既然是这个连续的加中的一项,那么它一定是小于等于
右边这个连续的加的,它也就是小于等于它的上界
所以说我们得到了一个比我们一开始给的那个上界要好的一个上界
好了,本次我们讲了有关阶乘和二项式系数的估值,谢谢大家
[音乐]