<数音>(科普娱乐入门向连载)[之一]

前言
====================================================================
这是个一时兴起而决定的计划
之前学的许多东西在弃置一段时间之后往往就不再记得其细节,而影响到了后续的学习,因而
希望能够通过某种形式记录下自己的学习历程,自己的想法以及某些观点,不过实际内容应该
会是娱乐向的,毕竟目前的水平写不出什么高质量的东西,而在IRC又丢掉了过多的节操,想想
也只能如此了.
本人实际上应该算是个实用主义派,在这一点上,所学和所写的东西看起来并不是那么具有说
服力---实际上我自己也已经不太了解自己究竟想要做什么了,起初接触这一切的缘由本身也
非常的胡来---只是因为失恋而选择的这样一个专业,而之前颓靡的18年让我也已经输在了起
跑线上,不过已然如此想想也未然不是一件好事---相对较低的自我期望极大的解放了自己的
身心.
本文并不期望让读者掌握什么具体的知识---这显然对于大多数人都没有什么意义,而是希望
读者能对鄙人的思路有所共鸣,哪怕是一个step也好,亦或是能从鄙人这里学到一些新的思路
又或者指出鄙人的疏漏,又或者能成为诸位饭后的谈资.文章绝大多数都会要求读者具有一些
基本的数学基础---也并不多,高中足矣.文中或许也会穿插一些数学趣史---不要忘记这是一
则娱乐向的文章.
如果有必要的话(或者说鄙人能挤出更多的时间并且能够学会某些东西)重要的篇章可能会有
续章,描述一些更深层次(非入门向)的数学理论与思想.

### 0.符号约定

并不是些什么故弄玄虚的符号,但实际上在专业的数学读物上比较少见,不过Knuth.使用这些
符号约定,考虑面向大都是计算机相关背景的读者,因而选取他老人家的符号约定也在情理之
中.

(利用加法公式反复展开即可得到)

(利用加法公式反复展开具有最小下指标的二项式系数项即可得到)
(关于上指标求和<summation on the upper index>)
此类组合数是由于二项式定理(binomial theorem)而被命名为二项式系数的,简单叙述如下:
令n是一个正整数.于是对于任意的x,y,有

回忆起组合数的定义,实际上这个定理的证明非常容易---$x^{k}y^{n-k}$的系数实际上就是
k个因子x与n-k个因子y的项的个数,这恰好是从n个(x+y)的因子中选取k个的方法数--他们都
提供一个x.

### 2.基本性质
在推广了二项式定理之后,我们仍然希望其能够具有整数情况下的那些美妙的性质,否则这种
推广就没什么意义的---他甚至不能够向下兼容.幸运的是,情况正如我们希望的那样.
推广证明的方法一般称之为多项式推理法(polynomial argument),这个方法通过考察等式两
边多项式的零点来证明他们相等.譬如之前所提到的吸收律,推广证明大致如下:
考虑到等式两边其实都是关于r的k+1次多项式,而由代数基本定理我们能知道:一个非零的
d次多项式或者更低次数的多项式在复数域上至多只能有d个的零点,也就是说,两个这样的
多项式之差不可能在多于d个点处为零(因为他们的差是一个不高于d次的多项式)除非这两
个多项式相等.而在整数情况下我们已经证明,只要r是一个非负整数,那么吸收律就是成立的,
因而两个多项式在无穷多处取相同的值,则他们必然是完全相同的.
借助这一强大的工具,我们能够推广其他所有在整数情况下已经证明的组合恒等式.
处理完这些遗留下的问题之后,一个很自然的问题便出现在了我们的眼前---我们是否能够通
过上指标r是正数或正整数的值推导出上指标为-r的值或是建立某种联系呢.这个工作是有必
要的---根据以往的经验,非负总是更加容易处理,我们对它也更加的熟悉.而实际在定义(续)
这一节之中我们已经给出了这个关系

通常我们称这个变换为反转上指标(negating the upperindex).
通过微分

我们能得到对于任意正整数p成立的这样一个恒等式

### 3.和式
我们会在很多地方遇到组合式和式,例如排序查找算法分析,又或是深入一些的数理统计与概
率论---它们并不是什么无用的,纯理论的东西,尽管他们时常看起来异常鬼畜.如果你还未遇
到组合式和式,也不知道它有什么用处,就赶紧去翻翻TAOCP.vol.3吧:).
以下几道简单的示例/习题主要来自以下参考书:
1).Introductory Combinatorics(5th Edition)
2).Concrete Mathematics (2nd Edition)
3).The Art Of Computer Programming - Fundamental Algorithms(3rd Edition)

### 4.后记
无论何时,遇到怎么样复杂的问题,在尝试完最后一种已知手段之前都不要放弃,并且要善于使
用之前使用过的思路和方法,或是将新的问题归约为已知问题,就像我们在ex.3中所做的那样,
这种思维方式叫最归化,正如G.Polya所言"如果你无法解出一个问题,那么一定是有一个更简
单的问题你未能解决".善于观察问题与现有手段的联系才能够帮助你快速解决问题.