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