计数基本原理

你会数数吗？这个问题是不是问得太傻了：谁不会数数啊？三岁毛毛都会。我说的可不是扳着手指头、脚指头数数，也不是数天上星星的个数，而是数学上的组合计数。遗憾的是，加拿大的高中生大都不会数数，尽管老师们整天强调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}。再用两种不同办法去计算这个级数，还可导出在集合的并、交、补运算下的公式；就可以对集合元素的某种计量分布有一个清晰的认识。世界也就因此变得光明了许多：人对自然的认识又进了一步。