【排列组合】
1、加法原理与乘法原理
加法原理：分类思想。一个事件的发生，分为几类事件的发生，通俗的说是好几种情况的发生。
乘法原理：分步思想。一个事件的发生，分为几个子事件分步发生。
这里要注意：（1）子事件：如何把事件划分为几个子事件呢，子事件是独立的，内部发生的概率一样。（2）分步，子事件安步骤完成
2、排列与组合
排列：从n个不同的元素里取m个。排列本身就是乘法原理的引申。
根据乘法原理，把事件分为m步，挑选一个有n种可能，挑选第二个有n-1种可能，则A(n,m)。
组合：c(n,m)
例题：
1、0~999999之间的所有数字中，任何一位都不包括数字1的数字总数为多少？
解析：
这里要和组合数做一个区别。组合数是：从n个取m个，第一次去有n种选择，第二次去有n-1种选择....，而本题，个位有9种选择，十位仍然有 9种选择....，所以，不是组合数，而是用乘法原理9*9.....。组合数与本题都是基于乘法原理。只是细节不一样而已。
任何一位都不包含1，采用乘法原理。个位不为1，有9种情况；十位不为1，有9种情况......，所以，9^6=531441。
2、6×9的的方格中，起点的左下角，终点在右上角，从起点到终点，只能从下向上，从左向右走，问一共有多少种不同的走法。
解析：对于只能向上，或者向右走，意思就是说要走6+9步，一共也就是15步，其中选6步向上走，先9步向下走。
然后分析是排列，还是组合。显然这是一个组合，因为，先出来的步法，不能再进行排列。
所以答案是组合数：C(15,6)*C(9,9)或者C(15,9)C(6,6)
3、你有一个3X3X3的立方体。你现在在正面左上的顶点，需要移动到对角线的背面右下的顶点中。每次移动不限距离，但只能从前至后、从左至右、从上至下运动，即不允许斜向或后退。有多少种方法?
解析：一共需要9步。C(9,3)C(6,3)C(3,3)
4、七夕节n对恋人（n>=2）围成一圈举行篝火晚会。晚会的规则是：男女相同，且每对恋人处在相邻的位置上。请问有多少种不同的圈子？
解析：根据题设，要求不同的圈子，这意味着圈子可以转动时造成的差异，可以不计。n个人站一竖排的全排列为n!，n个人站一圈子且不计圈子转动的差异的全排列为(n-1)!。
又，n个人其实是2n个情侣，每组情侣有2种站位，n组有2^n种站位。
所以共2^n(n-1)!。
5、 一个合法的表达式由()包围，()可以嵌套和连接，如(())()也是合法 表达式；现在有 6 对()，它们可以组成的合法表达式的个数为多少？
解析：卡特兰数列
我们可以把左括号看做1，右括号看做0，这些括号的组合就是01的排列、这里需要满足从第一个数开始的任意连续子序列中，0的个数不多于1的个数，也就是右括号的个数不多于左括号的个数。
答案：法的排列数有C（2n,n）-C（2n,n-1）
类似的题：12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
6、每份考卷都有一个8位二进制序列号。当且仅当一个序列号含有偶数个1时，它才是有效的。例如，00000000、01010011都是有效的序列号，而11111110不是。那么，有效的序列号共有（） 个。
解析：分类：0个1
2个1
4个1
6个1
8个1
组合问题：要求1的位置不能变。
结果是组合数：C(8,0)+C(8,2)+C(8,4)+C(8,6)+C(8,8)=1+28+70+28+1=128
7、书架上有编号为1-19的19本书，从中拿5本，问5本编号都不相邻的拿法有多少种？
解析：插空法。3003。这道题可以理解为把5本书插到14本书的中间，即加头尾的15个空格里，有多少种组合。因为不能相邻，组合问题，所以是有C (15,5) 种方法。
【线性规划】
作为特使，你需要组织A/B两国元首相约在杭州萧山机场交换一份重要文件（假设交换文件不需要时间）。约定两国飞机在晚上的20点至24点这4个小时会面，A国的飞机如果到了，会等待1个小时，B国的飞机如果到了，会等待2个小时，如果假设两架飞机在这段时间内降落机场的概率是均匀分布的，那么能顺利完成交换的概率是多少？
解：
设x为a到达的时间 y为b到达的时间
则 20<x<24
20<y<24
0<x-y<1
0<y-x<2
然后画图像求出面积比，答案19/32。
