排列组合
加法/乘法法则
加法法则
相互独立的事件 A、B 分别有 k 和 l 种方法产生，则产生 A 或 B 的方法数为 k+l 种。
集合论定义
若|A|=k，|B|=l ，且A∩B=Φ ，则|A∪B| = k+l 。
S = S1 ∪ S2 ∪ · · · ∪ Sm, Si ∩ Sj = ∅ (i ≠ j)
⇒
|S| = |S1| + |S2| + · · · + |Sm|。
例1
a食堂有3种汉堡，b食堂有4种小吃，c食堂有2种包子，你的早餐只想吃一种，共有多少种选择方法？
解：
设S是所有食物的集合，Si是第i类食物的集合(i=1,2,3)，显然，Si∩Sj=Φ (i≠j) ，根据加法法则有：
|S| = |S1| + |S2| + |S3| = 3 + 4 + 2 = 9。
例2
大于0小于10的奇偶数有多少个？
解：
设S是符合条件数的集合，S1、S2分别是符合条件的奇数、偶数集合，显然，S1∩S2=Φ ，根据加法法则有：
|S| = |S1| + |S2| = 5 + 4 = 9。
乘法法则
相互独立的事件 A、B 分别有 k 和 l 种方法产生，则选取A以后再选取B 的方法数为 k×l 种。
集合论定义
若|A|=k，|B|=l ，A×B={(a,b)|a∈A，b∈B}，则|A×B| = k×l 。
S = P × Q
⇒
|S| = |P | × |Q|。
例
从A 地到B地有二条不同的道路，从B地到C地有四条不同的道路，而从C地到D地有三条不同的道路。求从A地经B、C两地到达D地的道路数。
解：
设S是所求的道路数集合，S1、S2、S3分别是从A到B、从B到C、从C到D的道路集合，根据乘法法则有
|S| = |S1 | × |S2| × |S3| = 2 × 4 × 3 = 24。
计数问题的分类
有序安排或有序选择
——允许重复/不允许重复
无序安排或无序选择
——允许重复/不允许重复
重集的概念
标准集的特性：确定、无序、相异等。
重集：B={k1 b1, k2 b2, …, kn * bn}，其中：bi为n个互不相同的元素，称 ki为bi的重数， i = 1, 2, …, n，n=1,2,…, ∞，ki = 1, 2, …, ∞。
排列
线排列
从n个不同元素中，取r个(0≤r≤n)按一定顺序排列起来，其排列数P(n,r)。
集合论定义
设A={an} ，从A中选择r个(0≤r≤n)元素排列起来，A的r−有序子集，A的r−排列。
定理
若n, r∈Z且n≥r≥0, P(n,r)=n!/(n-r)!。
若n=r，称全排列P(n,n)= n!；
若n＜r, P(n,r)=0；
若r=0, P(n,r)=1。
证明
构造集合A的r−排列时，可以从A的n各元素中任选一个作为排列的第一项，有n种选法；第一项选定后从剩下的n-1个元素中选排列的第二项有n-1种选法；…由此类推，第r项有n-r+1种选法。根据乘法原理有：
P(n,r) = n(n-1)……(n-r+1) = n!/(n-r)! 。
推论1
若n, r∈N且n≥r≥2，则P(n,r)=n×P(n-1,r-1) 。
证明
在集合A的n个元素中，任一个元素都可以排在它的r−排列首位，故首位有n种取法；首位取定后，其他位置的元素正好是从A的另n-1个元素中取r-1个的排列，因此有P(n-1,r-1)种取法。由乘法法则有：
P(n,r)=n×P(n-1,r-1)
推论2
若n, r∈N且n≥r≥2，则P(n,r)= r×P(n-1,r-1)+P(n-1,r) 。
证明
当r≥2时，把集合A的r−排列分为两大类：一类包含A中的某个固定元素，不妨设为a1，另一类不包含a1 。第一类排列相当于先从A-{a1}中取r-1个元素进行排列，有P(n-1,r-1)种取法，再将a1放入每一个上述排列中，对任一排列，a1都有r种放法。由乘法法则，第一类排列共有r×P(n-1,r-1)个。第二类排列实质上是A-{a1}的r−排列，共有P(n-1,r)个。再由加法法则有：
P(n,r)= r×P(n-1,r-1)+P(n-1,r)
例1
由数字1,2,3,4,5可以构成多少个所有数字互不相同的四位数？
解：
由于所有的四位数字互不相同，故每一个四位数就是集合{1,2,3,4,5}的一个4−排列，因而所求的四位数个数为
P(5,4)=5!/(5-4)!=120。
例2
将具有9个字母的单词FRAGMENTS进行排列，要求字母A总是紧跟在字母R的右边，问有多少种这样的排法？如果再要求字母M和N必须相邻呢？
解：
由于A总是R的右边，故这样的排列相当于是8个元素的集合{F,RA,G,M,E,N,T,S}的一个全排列，个数为
P(8,8) = 8! = 40320。
如果再要求M和N必须相邻，可先把M和N看成一个整体={M,N}，进行7个元素的集合{F,RA,G,E,T,S,}的全排列，在每一个排列中再进行 {M,N}的全排列，由乘法法则，排列个数为
P(7,7) P(2,2) = 7! 2! = 10080。
例3
有多少个5位数，每位数字都不相同，不能取0，且数字7和9不能相邻？
解：
由于所有的5位数字互不相同，且不能取0，故每一个5位数就是集合{1,2,…,9}的一个5-排列，其排列数为P(9,5)，其中7和9相邻的排列数为[c(7,3)4!2]4×2×P(7,3)，满足题目要求的5位数个数为
P(9,5) - 4 2 P(7,3) = 15120 -1680 = 13440
圆排列
设A={an} ，从A中取r个(0≤r≤n)元素按某种顺序（如逆时针）排成一个圆圈，称为圆排列（循环排列）。
定理
设A={an}，A的r圆排列个数为P(n,r)/r。
证明
由于把一个圆排列旋转所得到另一个圆排列视为相同的圆排列，因此线排列a1a2…ar，a2a3…ara1，… ara1a2…ar-1在圆排列中是一个，即一个圆排列可产生r个不同的线排列；同理， r个不同的线排列对应一个圆排列。而总共有P(n,r)个线排列，故圆排列的个数为
P(n,r)/r= n!/(r×(n-r)!)
例1
有8人围圆桌就餐，问有多少种就座方式？如果有两人不愿坐在一起，又有多少种就座方式？
解：
由上述定理知8人围圆桌就餐，有8!/8=7!=5040种就座方式。
又有两人不愿坐在一起，不妨设此二人为A、B，当A、B坐在一起时，相当于7人围圆桌就餐，有7!/7=6!种就座方式。 而A、B坐在一起时，又有两种情况，或者A在B的左面，或者A在B的右面，因此A、B坐在一起时，共有2×6!种就座方式，因此如果有两人不愿坐在一起，就座方式为
7!-2×6!= 5×6!=3600
例2
4男4女围圆桌交替就座有多少种就座方式？
解：
显然，这是一个圆排列问题。首先让4个男的围圆桌就座，有4!/4=3!种就座方式。 因为要求男女围圆桌交替就座，在男的坐定后，两两之间均需留有一个空位，女的就座相当于一个4元素集合的全排列，就座方式数为4!。由乘法法则知，就座方式数为
3!×4!=144
重排列
从n个不同元素中，可重复选取r个按一定顺序排列起来，称为重排列。
集合论定义
从重集B={k1 b1, k2 b2, … , kn * bn}中选取r个按一定顺序排列起来。
定理1
重集B={∞ b1, ∞ b2, … , ∞ * bn} 的r−排列的个数为nr。
证明：
构造B的r−排列如下：选择第一项时可从n个元素中任选一个，有n种选法，选择第二项时由于可以重复选取，仍有n种选法，…，同理，选择第r项时仍有n种选法，根据乘法法则，可得出r−排列的个数为nr。
例1
由数字1,2,3,4,5,6这六个数字能组成多少个五位数？又可组成多少大于34500的五位数？
解：
一个五位数的各位数字可重复出现，是一个典型的重排列问题，相当于重集B={∞ 1,∞ 2,…,∞*6}的5−排列，所求的五位数个数为6^5=7776。
大于34500的五位数可由下面三种情况组成：
万位选4,5,6中的一个，其余4位相当于重集B的4−排列，由乘法法则知，共有3×6^4个五位数；
万位是3，千位5,6中的一个，其余3位相当于重集B的3−排列，由乘法法则知，共有2×6^3个五位数；
万位是3，千位4中的一个，百位选5,6中的一个，其余2位相当于重集B的2−排列，由乘法法则知，共有2×6^2个五位数；
由加法法则知，大于34500的五位数个数为3×6^4 + 2×6^3 + 2×6^2=4392
定理2
重集B={n1 b1,n2 b2,…,nk bk}的全排列个数为n! / ( n1! n2! …… nk! )，其中，n = n1 + n2 +…… +nk。
证明：
将B中的ni个bi看作不同的ni个元素，赋予上标1,2,…, ni，即b(1,i),b(2,i)……,b(ni,i), i=1, 2,…… k，如此，重集B就变成具有n1+n2+…+nk=n个不同的元素集合A = {b(1,1),b(2,1)……,b(n1,1),b(1,2),b(2,2)……,b(n2,2),……b(1,k),b(2,k)……,b(nk,k,}
显然，集合A的全排列个数为n!。又由于ni个bi赋予上标的方法有ni!种，于是对重集B的任一个全排列，都可以产生集合A的n1!×n2!×…×nk!个排列（由乘法法则），故重集B的全排列个数为n! / ( n1! n2! …… * nk! )。
注：利用组合数的计数方法同样可以得出证明。
例2
有四面红旗，三面蓝旗，二面黄旗，五面绿旗可以组成多少种由14面旗子组成的一排彩旗？
解：
这是一个重排列问题，是求重集{4红旗,3蓝旗,2黄旗,5绿旗}的全排列个数，根据定理，一排彩旗的种数为
14! / ( 4! 3! 2! * 5! ) = 2522520。
例3
用字母A、B、C组成五个字母的符号，要求在每个符号里，A至多出现2次，B至多出现1次，C至多出现3次，求此类符号的个数。
解：
这也是一个重排列问题。根据分析，符合题意的符号个数相当于求重集M={2A,1B,3*C}的5−排列个数，可分为三种情况：需要分别求M-{A}、M-{B}和M-{C}的全排列个数。根据加法法则，此类符号个数为
5! / (1! 1! 3!) + 5! / (2! 0! 3!) + 5! / (2! 1! 2!) = 60
项链排列
对圆排列，通过转动、平移、翻转、可重合的，即可看作项链排列。
若n个不同元素的r−项链排列个数为P(n,r)/(2×r)，具体参照Pólya定理。
