本文屬于《程式員的數學》讀書筆記系列。本篇主要數數，要做到的“不遺漏，不重複”。
植樹問題-不要遺忘0
在10米長的路上，從路的一端起每隔1米就要中一顆樹，那麼需要種多少課樹。
答案：11 顆，可能有人下意識的去10/1 =10. 不了解可以下面畫圖來輔助了解。
簡單的問題，用以用手數出來，複雜的問題，需要找規律。使用變量N把問題抽象出來。
加法法則
要數出分為兩個集合的事物時，可以用加法法則。
在一副撲克牌中，有10張紅桃數字牌（A、2、3、4、5、6、7、8、9、10），3張紅桃花牌（J、Q、K），那麼紅桃共有多少張？
答案：13張
上面使用的就是加法法則。
加法法則就是将無“重複”元素的兩個集合A、B相加，得到A∪B的元素數。
A∪B的元素數 = A的元素數 + B的元素數
如果将集合A的元素數寫作|A|，集合B的元素數寫作|B|，那麼加法法則就可以用以下等式來表示：
|A∪B| = |A| + |B|
注意：加法法則隻在集合中沒有重複元素的條件下成立，在有重複的情況下，必須減去重複才能得到正确的數量。
思考題 ：控制亮燈的撲克
在一副撲克牌中，有13個級别（A、2、3、4、5、6、7、8、9、10、J、Q 、K），在這裡分别将A、J、Q、K設為整數1、11、12、13，
在我們面前有一個裝置，隻有往裡放入一張撲克牌，會根據撲克牌的等級控制燈亮燈滅。我們假設放入撲克牌的等級為n（1-13的整數），
● 若n是2的倍數，則燈亮
● 若n是3的倍數，則燈亮
● 若n既不是2的倍數，也不是3的倍數，則燈滅
如果往這個裝置中依次放入這13張牌，那麼亮燈的有多少張牌呢？
答案：1-13裡面。2的倍數6張。3的倍數 4個，2,3的公共倍數 6.12 是2個。
是以亮燈的牌數= 6+4-2 =8
這是考慮了重複元素的加法法則。也稱之為容斥原理。
集合A、B的元素總數 = A的元素數 + B的元素數 - A和B共同的元素數。
如果将集合A的元素數寫作|A|，集合B的元素數寫作|B|，那麼容斥原理就可以用以下等式來表示：
|A∪B| = |A| + |B| - |A∩B|
使用容斥原理時，必須弄清楚“重複的元數”有多少個。
乘法法則
思考題一：紅桃的數量
一副撲克中，有紅桃、黑桃、方塊、梅花四種花色，每個花色都有A到K這13個等級。那麼，一副撲克共有多少張？
答案：4*13=52張（乘法法則）
現有A、B兩個集合，如果要将集合A和集合B中的所有元素組合起來，這裡組合的結果就是兩個集合的元素數相乘的結果。我們将集合A的元素數寫作|A|，将集合B的元素數寫作|B|，那麼元素的組合數就是：|A|×|B|
從集合A和集合B中取出一個元素作為一組，所有這種組合的集合即為A×B，表示為|A×B|=|A|×|B|
思考題 2 ：3個骰子
将3個寫有1到6的骰子并列排放，形成一個3位數，總共能形成多少個數字？
分析：
第1個骰子有1、2、3、4、5、6共6種情況
第2個骰子也有6種情況，則兩個骰子共有6×6=36種情況（乘法法則）
第3個骰子同樣有6種情況，則三個骰子總共有6×6×6=216種情況
答案：216個
32個燈泡
1個燈泡有亮和滅兩種狀态，若将32個這
樣的燈泡排成一排，共有多少種亮滅模式？
每個燈泡有亮、滅兩種模式。
1個就 2
2個就是2*2；
3個就是2*2*2；
。。。。
通常n位2進制數可以表示的數的總和是
個,這是常識。
置換
概念：
将n個事物按順序排進行排列稱為置換(substitution)
例如：A、B、C這3個字母按照ABC、ACB、BAC...進行順序排列，共有多少種排法？
第一個字母有3種選法，第二個字母有2種選法，第三個字母隻有1個選法；
故共有：3*2*1=6種排法。
記作：3！讀作：3的階乘（factorial：乘數呈階梯狀遞減）
5!=5×4×3×2×1=120
4!=4×3×2×1=24
3!=3×2×1=6
2!=2×1=2
1!=1×1=1
注意：0！ = 1 （0的階乘為1）
排列（permutation）
思考題一：從5張牌中取3張牌進行排列
如果你手中現在有A、B、C、D、E這5張牌，現在要從這5張牌中選3張進行排列，請問有多少張排法？
分析：
選第1張牌，從5張牌中選，有5種選法
選第2張牌，從剩下的4張牌中選，有4種選法
選第3張牌，從剩下的3張牌中先，有3種選法
答案：5×4×3=60種
注意：排列也跟置換一樣，要考慮順序的，順序不同，是不同的排列，要分别計數。
歸納排列：從n張牌中選取
第1張牌，從n張牌中選取，有n種選法
第2張牌，從n-1張牌中選取，有n-1種選法
第3張牌，從n-2張牌中選取，有n-2種選法
......
第k張牌，從n-(k-1)張牌中選取，有n-(k-1)種選法
是以，從n張牌中選取k張牌的排列總數就是：
n×(n-1)×(n-2)×......×(n-(k-1))
記作：
=n×(n-1)×(n-2)×......×(n-(k-1))
上面的例子就是可以表示位
= 5*4*3
用階乘表示
=
注意：
= 1
組合（combination）
不考慮順序。
假設現在有A、B、C、D、E五張牌，要從這5張牌中取出3張牌，并且不考慮它們的順序，即以3張牌一組進行選擇，則共有10種取法，這種取法被稱為組合。
分析：
首先和排列一樣進行計數，不考慮重複共有60種排列
。
然後除以重複計數的部分（重複度），3張牌置換的總數為6，即3張牌重複度為6(
=3*2*1)
這裡使用先考慮順序進行計數，在除以重複度的方法，是計算組合時常用的方法。
用階乘表示：
=
例如：
置換、排列、組合的關系：
置換合組合的結合就是排列。
上面的例子,置換是“3張牌的交替排列方式”，組合表示“3張牌的取法”，兩者結合就是“取出3張牌，進行交替排列”。
即
*
=
這跟前面求
=
是一樣的。
思考題：藥品調劑
假設現在要把顆粒狀的藥品調成一種新藥，藥品有A，B ，C三種，規則如下：
- 從A,B ,C 這三種藥品中取 100粒。
- 調劑是A\B\C 沒種至少有一顆。
- 不考慮藥品調劑的順序。
- 同種藥品每顆都相同。
這種情況下，新藥調劑的組合有多少種？
這是一個重複組合的問題。我在看完上面的概念時候，勉強能看懂，到了練習題有被打回原形。容易困擾。是以看了書上的介紹，從小數開始推算，找規律。100顆太複雜，那麼就從小數看。
3顆。1 種。 A,B,C
4顆，3 種。
5顆，6種。
還沒找到規律，看了書。
書上介紹思路是：把100顆排成一排，直接有間隙99個，任意間隙劃線兩道。第一道線左邊表示A，第二道線右邊表示C，兩線中間表示B。那麼問題就轉換為從99道線随意去2道線。即
=99*98/2 =4851. 套用前面的小數字也能驗證。3顆\4顆、5顆 分别對應的是
。找規律
思考題：至少有一端是王牌
現在有5張撲克牌，包含2張王牌，J,Q，K各一張。将這5張撲克牌排成一排，左端或者右端至少有一端是王牌的排法有多少種？
（不區分大小王）
至少有一端是王牌，包含了兩端都是王牌的情況，不區分大小王，要求我們計算
時，先區分大小王計算，在除以重複度。
分析：
我們把撲克牌分别設為x1,x2,J,Q,K .
【1】左端是王牌的情況
王牌位置有X1,X2 兩種選擇，剩餘的4張可以自由排序。
是以，使用乘法法則： 2*
= 2*4! =48
其中包含了兩端都是王牌的情況。
【2】右端是王牌的情況
與上面類似，左右颠倒下，也是48.
【3】兩端都是王牌
就是兩端的選法隻有2張王牌的選位，即
，剩餘3張牌可以自由排列。即
。
根據乘法原則：
*
= 2！* 3！= 12
按照【1】+【2】-【3】 就能求出至少一端是王牌【容斥原理】。在除以王牌的自由度就能得到“至少有一端是王牌的組合”。
好了，本章内容到此結束。我覺得有些難掌握，主要是N，K的抽象比較難，有時候從小數3,4,5 開始找也困難。