[具体数学]第五章·二项式系数(第一部分)
第五章·二项式系数分8节,包含基本恒等式、生成函数、超几何函数、机械求和法等内容。这是笔记第一部分,包括基本恒等式、一些练习、处理的技巧,以及牛顿级数、二项式反演。
基本恒等式
二项式系数
注意上式中,,而 可以是任意实数(甚至复数)。
- 只有当 取非负整数时, 才有组合解释。但是,鉴于二项式系数还有许多其他用途,所以将范围推广至实数;
- 可以把 视为 的 次多项式,此观点常常有用;
- 下指标 是非整数的情形应用很少,故这里不考虑。
最重要的十个二项式系数恒等式
其中,范德蒙德卷积公式有如下推论:
注意对称性+上指标反转可以把上/下指标中的变量给移动到下/上指标去。上述的推论都可以通过不断进行对称和反转得到。
上述恒等式的证明
吸收/提取恒等式:
在杨辉三角中,即
的数等于 的数乘上 .加法恒等式:代数证明略,组合证明:先设
,从 个人中选取 个人,等价于设一个特殊的人,选他+从 人中选 个,不选他+从 人中选 个。推广到实数,由于等号两边都是 的 次多项式,它们的差也是 的 次多项式,最多有 个零点,或者恒为零;然而易知这个等式在 内恒成立,已经有多于 个零点了,所以二者之差恒为零,即等式在 上恒成立。上述过程称为多项式推理法,非常重要!
在杨辉三角中,即上两个相加等于下面一个。
上指标反转:
三项式版恒等式:
故二者相等。平行求和法:
在杨辉三角中,即一条斜
向下的线上的所有值加起来等于末尾那个数的下一行的数。上指标求和法:
在杨辉三角中,即一条竖线上的
个值加起来等于末尾那个值的右下角的值。范德蒙德卷积公式:组合证明:先设
,左式是从 个男生中选 个,加上从 个女生中选 个,枚举这个 ,右式是从 个人中选 个人,二者显然相等。然后再由前面提及的多项式推理法推广到 上。
我的批注:上面许多恒等式都可以在杨辉三角中形象化地记忆,其证明也在杨辉三角中有直观体现。
除此以外,关于二项式系数的恒等式还有茫茫多……
基本练习
问题1:比值的和式
求
解:由三项式恒等式
上述过程怎么想到的呢?首先运用三项式恒等式可以使分母不含
,得以提出求和号;然后,考虑 在杨辉三角中的形态,是一个斜 向下的形态,于是转换到平行求和法。
问题2:来自排序文献
求
解:
设
于是乎:
故
上述解答的思考过程:首先,
中二项式系数外有个 ,自然想到用吸收恒等式把 给吸进去,为了应用吸收恒等式,把原式拆成了两部分;观察 的形态,在杨辉三角中,它们都是某一竖条相加,自然转换成上指标求和法求解。
问题3:来自以往的考试题
求
于是
当找不到公式予以化简时,不妨考虑寻找递归式。
问题4:包含两个二项式系数的和式
求
解:这个就是问题2中的
问题5:有三个因子的和式
求
解:
如果把
吸进 ,得到的 中 有可能是负的,则不能运用对称性继续推导了(一定注意对称性要求上指标是正整数)。
问题6:一个令人惊悚的和式
求
解:
再三强调对称性只能应用在上指标是正整数的情形下,上面推到过程如果对
使用了对称性,会得到错误的结果(恒为 )。
问题7:新的障碍
求
解:
解题思路:如果
,就是上一题了,可惜这个 使得三项式版恒等式无法使用,后续也就难以进行了。既然这个 这么讨厌,那就让它消失,精彩之处在于逆用范德蒙德卷积公式的推论达到这个效果。
问题8:不同的障碍
求
解:
根据问题1的结论,
处理的技巧
技巧1:取一半
加倍公式(duplication formula):
对加倍公式两边除以
这个技巧常常怎么使用呢?我们对形如
的二项式系数特别不爽,因为无论是对称性还是上指标反转都无法将其处理为上下指标只有一边含有 的形式。还记得问题6、7、8中,我们是靠着三项式版恒等式把它干掉的。现在我们多了一种工具,即把 写成 的式子,其中 是某个适当的整数(常取 )。核心公式:
技巧2:高阶差分
差分:
应用1(负的下降幂的一个情形)
考虑函数
应用2(牛顿级数)
设
根据后面章节的内容,任何幂次都能表示成下降幂的和式,从而
由加法恒等式:
应用3( 对阶乘的推广)
上述推导中,先使用了一个差分把阶乘干掉了,再套用高阶差分公式,着实妙哉!
于是,
技巧3:反演
二项式反演:
另一个形式:
应用(足球胜利问题)
就是著名的错排问题。
显然,
一个简单的观察是,对于所有
实施二项式反演,得到:
我们知道:
从上述推导中的