計數基本原理

你會數數嗎？這個問題是不是問得太傻了：誰不會數數啊？三歲毛毛都會。我說的可不是扳著手指頭、腳指頭數數，也不是數天上星星的個數，而是數學上的組合計數。遺憾的是，加拿大的高中生大都不會數數，盡管老師們整天強調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}。再用兩種不同辦法去計算這個級數，還可導出在集合的並、交、補運算下的公式；就可以對集合元素的某種計量分布有一個清晰的認識。世界也就因此變得光明了許多：人對自然的認識又進了一步。