引：“我們要把厚書讀薄，再把薄書讀厚.”
進(jìn)一步的系統(tǒng)化將在讀完這本書后，以表格或者思維導(dǎo)圖的形式出現(xiàn).
一、乘法原理
乘法原理討論分階段辦事過程中的計數(shù)問題.
用集合論觀點解釋：
把分階段進(jìn)行的事情看作一種多重選取過程，每一個過程都是自某個集合挑選一個元素，然后考慮有多少種不同的挑選方式.
【應(yīng)用】數(shù)的整除，因數(shù)分解問題
【例3】2160的正約數(shù)個數(shù).
2160 = 2^4 * 3^3 * 5^1
則任意約數(shù)形式為2^i * 3^j * 5 ^k (0<=i<=4, 0<=j<=3, 0<=k<=1)
所以約束個數(shù)為(4+1)(3+1)(1+1)=32.
【例5】從題目中抽象出模型.
【例6】 一個結(jié)論：[u,v]=n, 令n的因子r的個數(shù)為n(r)，有k個因子.
則符合要求的數(shù)對個數(shù)為 (2n(r)+1)*..*(2n(r)+1).
需要注意的是最大公約數(shù)，是去兩數(shù)某因子的最大值.
【例7】補(bǔ)集思想.(排除法)
在整除性問題中，確定前n-1位，然后分類討論第n位的情況.
【例8】看了，未懂.
二、重復(fù)排列
【定義】如果在同一個n階集合(有n個元素)中依次進(jìn)行k次選取，而且選過的元素還可以再選，則一共有n^k中不同的選取方式(即重復(fù)排列方式).
【應(yīng)用】空間解析幾何、集合子集性質(zhì)的討論
【例5】立方體{(x,y,z):0<=x,y,z<=a}頂點坐標(biāo).
證 顯然每個頂點(x,y,z)的三個坐標(biāo)都是集合{0,a}的元素，所以共有2^3個不同的頂點.坐標(biāo)略.
【例6】在三維歐氏空間給出9個格點(坐標(biāo)值為整數(shù))，求證其中必有兩點中點坐標(biāo)為格點.
證 若兩點A(x1,y1,z1)和B(x2,y2,z2)的中點為格點，必有x1和x2，y1和y2，z1和z2和為偶數(shù)，即兩者奇偶性相同.
考慮考慮歐氏空間格點奇偶性情況可知，每個坐標(biāo)值都是{奇數(shù)，偶數(shù)}中一個元素，所以格點有8種不同的奇偶性.從而，原命題由抽屜原理可證.
【例7】n階集合共有2^n個子集，2^n-1個真子集.
【例9】棋盤問題，從左下角走到右上角，n+1行，m+1列，求證f(m,n)<=2^(mn).
證 道路將城市分成mn個方塊，而路線又將方塊分成兩個子集(其中一個可能為空)，顯然不同子集個數(shù)為2^(mn).即f(m,n)<=2^(mn)，當(dāng)且僅當(dāng)m=n=1時等號成立.
三、排列
【定義】從n個不同的元素中有次序地選取k(1<=k<=n)個，叫做從n個不同元素中取出k個元素的一個排列.
【應(yīng)用】組數(shù)問題中的“無重復(fù)數(shù)字”問題.
【例4】利用補(bǔ)集思想處理無重復(fù)數(shù)字問題.考慮不參加組數(shù)的數(shù)字整除情況和所有數(shù)字整除情況(聯(lián)系1.7)
【例5】逐位討論.
【例7】注意到k個數(shù)字取自不同行列(聯(lián)想皇后問題)，所以子集個數(shù)為k!，每個子集的和分行列討論，累加即可.
【例10】有2n個人參加收發(fā)電報培訓(xùn)，每兩人結(jié)為一對互發(fā)互收，有多少種不同的結(jié)對方式.(搭配問題)
解 (2n-1)(2n-3)...3*1=(2n)!/(2^n*n!)
需要注意的是求和使用的思想: 先求出全部數(shù)的積，然后去掉里面的偶數(shù).也是一種間接的方法.
四、加法原理
【集合的分劃】
若把一個集合B分成一些子集B1,B2,...,Bk，使得
(i)B1∪B2∪...∪Bk = B;
(ii)B1∩B2=∅ ,...，Bk-1∩Bk=∅.滿足這兩條性質(zhì)的子集B1,B2,...,Bk，叫做B的一個分劃.
【定義】
|B|=|B1|+|B2|+...+|Bk| 加法公式
這種通過分劃計數(shù)的原理叫做加法原理.
【例1】現(xiàn)有長度分別為1,2,...,n的細(xì)木棍各一根，可以以它們?yōu)檫厴?gòu)成多少種不同的三角形?
解 以c的長度對這些三角形分類，將c=k的三角形集合記做Bk，則構(gòu)成了集合B的一個分劃.
在Bk中，三角形三邊分別為a<b<k，其中k為定值，于是可將
(a,b)對應(yīng)于平面中的格點.通過限制條件a<k,b<k,a+b>k我們可以知道，符合條件的格點在a=b,a+b=k,b=k三條直線圍成的三角形內(nèi),
所以若k為偶數(shù)，有|Bk|=1/4*(k-2)^2
若k為奇數(shù)，有|Bk|=1/4(k-1)(k-3)
從而可以求得|B|.(二階等差數(shù)列求和不熟)
【例2】求方程x^2-[x]^2=(x-x[x])^2在區(qū)間[1,n]中根的數(shù)目.
解
將區(qū)間[k,k+1)中根的集合記做Bk.若x∈[k,k+1)，記k=[x],p=x-[x](0<=p<1)，可得2kp=[2kp+p^2].
顯然等式兩邊為整數(shù)，所以p=0,1/2k,...,2k-1/2k，故而|Bk|=2k。
由加法原理可知，|B|=n^2-n+1
五、帶限制條件的排列問題
(i) 間接方法
【排除法】先假定不存在限制條件，求出所有情況的數(shù)目；再考慮受到限制條件，而不允許出現(xiàn)的情況數(shù)目.
(ii) 直接方法
【優(yōu)限法】優(yōu)先解決受限對象(受限對象或受限元素)的安置，然后再考慮一般對象的安置問題.
【插入法】首先安排一般元素，然后將首先元素插入到允許的位置上.(某些元素相鄰或者不相鄰)
【視一法】首先要把要求相鄰排列的元素看成一個整體，同其他元素一同排列，然后再考慮這個整體內(nèi)部的元素間的排列問題.
【例8】10個節(jié)目中有6個演唱，4個舞蹈，要求每兩個舞蹈之間至少安排一個演唱.
解 反過來看問題，原命題等價于在任意兩演唱(邊界情況的話一個)中安排或不安排一個舞蹈，而這樣的可能位置共7個.所以共6!*P(7,4)種順序.
六、組合
【定義】從n個不同物件中無次序地(不計順序地)選取k個，叫做從n個物件中選k個的一個組合.
如果考慮k個物件的選取順序，可得P(n,k)=C(n,k)*k!
從而得到組合的計算公式C(n,k)=n!/k!(n-k)!
(i)C(n,n-k)=C(n,k)
(ii)C(n,k)+C(n,k-1)=C(n+1,k)