排列与组合

1. 计数的基本原则

1.1 相等原则

设$A,B$是两个有限集，如果存在由$A$到$B$上的一个一一对应映射(双射)，则$|A|=|B|$。

例题：$n$名选手参加乒乓球单打淘汰赛，需要打多少场比赛才能产生冠军？ 解：以$A$表示全部比赛所成之集，以$B$表示除了冠军之外的全部选手所成之集，则$|B|=n-1$。 作由$A$到$B$的映射$f$如下： 设$a\in A$，若在比赛$a$中选手$b$被淘汰，则$f(a)=b$，显然$f$是由$A$到$B$的一个一一映射。 由相等原则，$|A|=|B|=n-1$，所以要打$n-1$场比赛才能产生冠军。

1.2 加法法则

若具有性质$A$的事件有$m$个，具有性质$B$的事件有$n$个，则具有性质$A$或性质$B$的时间有$m+n$个。

例题：设$n$为大于1的正整数，求满足条件$x+y\le n$的有序正整数对$(x,y)$的个数。 解：设所求为$N$。因为满足条件$x+y\le n$，且$x=k(1\le k\le n-1)$的有序对$(x,y)$有$n-k$个，故由加法法则，有 $$\begin{array}{rl}N& =\sum _{k=1}^{n-1}(n-k)\\ & =(n-1)+(n-2)+\cdots +2+1\\ & =\frac{n(n-1)}{2}\end{array}$$

1.3 乘法法则

若具有性质$A$的事件有$m$个，具有性质$B$的事件有$n$个，则具有性质$A$和性质$B$的时间有$m+n$个。

2. 排列与组合

2.1 排列

排列是集合中元素的一个有序选取。两个排列是不同的，当且仅当它们的元素不同或者它们的元素排列顺序不同。

2.11 $n$元素的$r-$排列

$n$个元素集合$S$的一个$r-$排列，是从$S$中选取$r$个元素且各个元素不相同的排列。排列数为$P(n,r)=n(n-1)(n-2)\dots (n-r+1)=\frac{n!}{(n-r)!}$。

2.12 $n$元素的$r-$可重复排列

$n$个元素集合$S$的一个$r-$可重复排列，是从$S$中选取$r$个元素且允许元素相同的排列。排列数为$n^r$。

2.13 多重集的排列

定义1：由$n_1$个$a_1$，$n_2$个$a_2，\dots ，n_k$个$a_k$组成的集合$M$记为$M=\left\{n_1\cdot a_1,n_2\cdot a_2,\cdots ,n_k\cdot a_k\right\}$，$M$称为多重集，也称$M$是一个$n-$多重集，其中$n=n_1+n_2+\cdots +n_k$。定义2：设$M=\left\{n_1\cdot a_1,n_2\cdot a_2,\cdots ,n_k\cdot a_k\right\}$，$\pi$是集合$A=\{a_1,a_2,\dots ,a_k\}$的一个$n-$可重复集合且$\pi$中有$n_1$个$a_1$，$n_2$个$a_2，\dots ，n_k$个$a_k$，则称$\pi$是多重集$M$的一个全排列，此时也称$\pi$是由$n_1$个$a_1$，$n_2$个$a_2，\dots ，n_k$个$a_k$作成的全排列。定理：：多重集$M=\left\{n_1\cdot a_1,n_2\cdot a_2,\cdots ,n_k\cdot a_k\right\}$的全排列个数为： $$\frac{\left(n_1+n_2+\cdots +n_k\right)!}{n_1!n_2!\cdots n_k!}$$

2.2 组合

组合就是集合中元素的一个无序的选取

2.21 $n$元素的$r-$组合

设集合$S$有$n$个不同的元素，$S$的一个$r-$组合就是$S$中$r$个元素的一个集合，组合数为 $$C(n,r)=\left(\begin{array}{l}n\\ r\end{array}\right)=\frac{P(n,r)}{r!}=\frac{n!}{r!(n-r)!}$$

2.22 $n$元素的$r-$可重复组合

从集合$S$中可重复地选取$r$个元作成的多重集，称为集合$A$的一个$r-$可重复组合，组合数为$\left(\begin{array}{c}n+r-1\\ r\end{array}\right)$。

2.3 组合的基本性质

（1）$\left(\begin{array}{l}n\\ k\end{array}\right)=\left(\begin{array}{c}n\\ n-k\end{array}\right)(n⩾k⩾0)$ （2）$\left(\begin{array}{l}n\\ k\end{array}\right)=\left(\begin{array}{c}n-1\\ k\end{array}\right)+\left(\begin{array}{c}n-1\\ k-1\end{array}\right)(n>k⩾1)$ （3）$\left(\begin{array}{l}n\\ k\end{array}\right)=\frac{n}{k}\left(\begin{array}{l}n-1\\ k-1\end{array}\right)(n⩾k⩾1)$ （4）$\left(\begin{array}{l}n\\ k\end{array}\right)=\frac{n-k+1}{k}\left(\begin{array}{c}n\\ k-1\end{array}\right)(n⩾k⩾1)$ （5）$\left(\begin{array}{l}n\\ k\end{array}\right)=\frac{n}{n-k}\left(\begin{array}{c}n-1\\ k\end{array}\right)(n>k⩾0)$

定理 $$\left(\begin{array}{c}n\\ m\end{array}\right)\left(\begin{array}{l}m\\ k\end{array}\right)=\left(\begin{array}{c}n\\ k\end{array}\right)\left(\begin{array}{c}n-k\\ m-k\end{array}\right)(n⩾m⩾k)$$

2.4 圆周排列

如果在一圆周上讨论排列问题即将一排列排到一圆周上，称之为圆周排列问题，在这以前讨论的排列是排成一列。从$n$个中取$r$个在圆周上进行排列数以$Q(n,r)$表示。其中 $$Q(n,r)=\frac{P(n,r)}{r}$$

例：5个男生，3个女生围成一圆桌而坐。若没加任何要求，则$Q(8,8)=7!=5040$。若要求男生$B_1$不和女生$G_1$相邻而坐有多少种方案？若要求3个女生不相邻，又有多少种方案？ 解：先将$G_1$排除在外，7个人围成一圆桌，然后$G_1$插入，$G_1$插入有5种方法，故$B_1$和$G_1$不相邻的方案数为$5\times 6!=5\times 720=3600$。若3位女生不相邻，先考虑5个男生围成圆桌而坐的方案数，然后3个女生依次插入，其中的方案数为 $$4!\times 5\times 4\times 3=1440$$

3 排列组合例题

例题1

含有数字6的且能被3整除的五位数一共有多少个？ 解： 五位数中能被3整除的数有99999/3-9999/3=30000个。 先求五位数中不含有6且能被3整除的个数。 万位数可以有（1,2,3,4,5,7,8,9）共8个选择， 千位数可以有（0,1,2,3,4,5,7,8,9）共9个选择， 百位数可以有（0,1,2,3,4,5,7,8,9）共9个选择， 十位数可以有（0,1,2,3,4,5,7,8,9）共9个选择， 如果万位数+千位数+百位数+十位数的和除以3的余数是0，那么个位数可以有（0,3,9）共3个选择， 如果万位数+千位数+百位数+十位数的和除以3的余数是1，那么个位数可以有（2,5,8）共3个选择， 如果万位数+千位数+百位数+十位数的和除以3的余数是2，那么个位数可以有（1,4,7）共3个选择， 所以不管如何，个位数都是有3个选择。 所以五位数中不含有6且能被3整除的个数=8 $\times$ 9 $\times$ 9 $\times$ 9 $\times$ 3 = 17496。 所以五位数中至少出现一个6且能被3整除的个数=30000-17496= 12504

例题2

从1到300中取3个(不同的)数，其和能被3整除，有多少种取法？ 解： $$\begin{array}{l}{A}_1=\{1,4,7,\dots ,298\}表示除3余1的集合\\ A_2=\{2,5,8,\dots ,299\}表示除3余2的集合\\ A_0=\{3,6,9,\dots ,300\}表示除3余0的集合\end{array}$$ 取法为$3C(100,3)+C(100,1{)}^3$

例题3

$(x+y+z{)}^4$展开式有多少项(合并同类项后)? 解： 问题等价于从3个元素中有重复的选择4个元素，即 $C(3+4-1,4),C(3+4-1,3-1)$