本文属于《程序员的数学》读书笔记系列。本篇主要数数，要做到的“不遗漏，不重复”。
植树问题-不要遗忘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 开始找也困难。