计数基本原理

数论是一门学科,也是我的人生。有人把酒论英雄,我用数字描天下。
打印 被阅读次数

你会数数吗?这个问题是不是问得太傻了:谁不会数数啊?三岁毛毛都会。我说的可不是扳着手指头、脚指头数数,也不是数天上星星的个数,而是数学上的组合计数。遗憾的是,加拿大的高中生大都不会数数,尽管老师们整天强调Number Sense, Number Sense,他们就是不教计数的基本原理—中国三、四年级的小学生都会的东西,他们到了12年级的《Data Management》课程里,才教加法原理和乘法原理;而且,如果是一开课就教数数的话,那么至少有一半的学生会在第一个月内,Drop掉该门课程。所以近年来老师们也变聪明了,一开始就教统计,mean-median-mode(就像那个mini maini mo),花上大半个学期,最后的计数和概率就敷衍了事了。

学会数数就那么重要吗?如果一个学生连数数都不会的话,又谈何学习数学?而且在数学竞赛中,难题大多数是组合计数。我又不去参加什么竞赛,以后只要打个Labor工就行了,还要学数数吗?数钱总得会吧。可那也是老板数好了交给我的,关我什么事?如果你数学好的话,也许能够多挣点工钱呢!如果还说服不了你学习数数的话,那就只能啃爹娘了。

第三个基本计数原理是容斥原理:两个有限集合的并的基数,等于每个集合的基数之和,减去它们交集的基数。这可以推广到任意有限多个有限集合。当有多个成员部分重合的小组,集体举办某个活动时,你能安排好不冲突的时间表吗?当给定前n个质数时,你能求出下一个质数吗?给定一个正整数m, 你知道m! 的末尾有几个零吗?这些都可以用容斥原理来解决。

容斥原理说白了就是减法原理,而加法原理是它的特例。有了加、减、乘法原理,我们还有除法原理吗?有,不过它叫鹊巢原理或者Dirichlet原则。说的是,如果把m只鸽子放进n个巢中,那么必定有一个巢含有至少【m/n】(取整)只鸽子。这么简单的道理谁不明白啊?它可是所有数学存在性证明的根本。实数的有理数逼近就靠它了。

无穷集合怎么计数呢?用一对一原则:如果两个集合之间可以建立一个一一对应的关系,那么它们所包含的元素个数(基数)相等。可我怎么也不能相信,有理数的个数与正整数的个数相等?数学上就是这样的,与人们的有限意识并不相符;不然,又能怎么定义可数无穷大ω呢?Bernstein定理说得更绝:如果一个集合A与另一个集合B的某个子集B1有一对一关系,而且B与A的某个子集A1有一对一关系,那么A与B的基数相等。

所有实数的个数叫作连续基数c(不是光速)。连续统公设说的是,在c与ω之间的基数不存在;也就是说,没有一个集合,它的基数是介入c与ω之间。有不有比c更大的基数呢?那是以所有实数的子集构成的幂集,它的基数记作2^c;与所有实函数的个数一样多。然后呢,就没有然后了,谁还能想象幂集的幂集不成?

计数的最高境界是生成函数:对于一个给定集合S中的每一个元素x,定义一个重量函数w(x)(要求具有某种可加性),再取一个形式变量t,构成一个级数sigma{t^w(x): x属于S}。再用两种不同办法去计算这个级数,还可导出在集合的并、交、补运算下的公式;就可以对集合元素的某种计量分布有一个清晰的认识。世界也就因此变得光明了许多:人对自然的认识又进了一步。

登录后才可评论.