排列组合
四种基本计数原理
Four Basic Counting Principles
加法原理,减法原理,除法原理,乘法原理
集合的排列
Permutations of Sets
我们用 P(n,r)P(n,r)P(n,r) 表示 nnn 元素集合的 rrr 排列的数目.
其他表示方式 AnrA_{n}^{r}Anr
定理1
对于正整数 nnn 和 r,r≤n,r, r \leq n,r,r≤n, 有
P(n,r)=n!(n−r)!P(n,r) = \frac{n!}{(n-r)!}
P(n,r)=(n−r)!n!
定理2
nnn 元素集合的循环 rrr 排列的数目是
P(n,r)r=n!r∗(n−r)!\frac{P(n,r)}{r} = \frac{n!}{r*(n-r)!}
rP(n,r)=r∗(n−r)!n!
例1
用20个不同颜色的珠子串成项链,能做出多少项链?
解:解:解: 19!2\large \frac{19!}{2}219!
因为项链还可以翻转过来
集合的组合 (子集)
Combinations (Subsets) of Sets
用 (nr)\Large \binom{n}{r}(rn) 表示 nnn 元素集合的 rrr 子集数目
其他表示方式 C(n,r),CnrC(n,r),C_{n}^{r}C(n,r),Cnr
定理1
P(n,r)=r!(nr)P(n,r) = r! \binom{n}{r}
P(n,r)=r!(rn)
定理2
(nr)=(nn−r){n \choose r}={n \choose n-r}
(rn)=(n−rn)
定理3
(nr)=(n−1k)+(n−1k−1){n \choose r}={n-1 \choose k}+{n-1 \choose k-1}
(rn)=(kn−1)+(k−1n−1)
组合证明:组合证明:组合证明:
设 SSS 为 nnn 元素集合, xxx 为其中指定的一个元素
把 SSS 的 rrr 子集划分成两个部分:
令 AAA 为不含 xxx 的 rrr 子集, BBB 为含 xxx 的 rrr 子集.
∣A∣=(n−1r)|A|=\Large {n-1 \choose r}∣A∣=(rn−1) , ∣B∣=(n−1r−1)|B|=\Large {n-1 \choose r-1}∣B∣=(r−1n−1)
因此 ∣S的r子集∣=∣A∣+∣B∣|S的r子集|=|A|+|B|∣S的r子集∣=∣A∣+∣B∣
即为原命题
定理4
(n0)+(n1)+(n2)+...+(nn)=2n{n\choose 0}+{n\choose 1}+{n\choose 2}+...+{n\choose n}=2^n
(0n)+(1n)+(2n)+...+(nn)=2n
即为所有的子集数
多重集合的排列
Permutations of Multisets
定理1
SSS 是有 kkk 个不同元素的多重集合,每个元素的重复数 ≥r,\ge r,≥r,那么 SSS 的 rrr 排列为
krk^r
kr
定理2
SSS 是有 kkk 个不同元素的多重集合 ,,, 每个元素的重复数分别为 n1,n2,...,nk,n_1,n_2,...,n_k,\quadn1,n2,...,nk,设 SSS 的大小为 n=n1+n2+...+nk,n = n_1+n_2+...+n_k,\quadn=n1+n2+...+nk, 则 SSS 排列数目为
n!n1!n2!⋯nk!\frac{n!}{n_1!n_2!\cdots n_k!}
n1!n2!⋯nk!n!
证明:证明:证明:
设 kkk 种元素分别为 a1,a2,...,aka_1,a_2,...,a_ka1,a2,...,ak
从 nnn 个位置中选 n1n_1n1 个放 a1a_1a1
从 n−n1n-n_1n−n1 个位置中选 n2n_2n2 个放 a2a_2a2
.........
答案即为
(nn1)(n−n1n2)(n−n1−n2n3)⋯(n−n1−n2⋯−nk−1nk)=n!n1!n2!⋯nk!{n\choose n_1}{n-n_1\choose n_2}{n-n_1-n_2\choose n_3}\cdots{n-n_1-n_2\cdots-n_{k-1} \choose {n_k}}=\frac{n!}{n_1!n_2!\cdots n_k!}
(n1n)(n2n−n1)(n3n−n1−n2)⋯(nkn−n1−n2⋯−nk−1)=n1!n2!⋯nk!n!
定理3
设 nnn 为正整数,并设 n=n1+n2+...+nkn=n_1+n_2+...+n_kn=n1+n2+...+nk ,把 nnn 个不同元素划分到 kkk 个标有标签的盒子中 ,,, 第 111 个盒子中有 n1n_1n1 个 ,,, 第 222 个盒子中有 n2n_2n2 个 ,..., ...,... 第 kkk 个盒子中有 nkn_knk 个元素的方案数为
n!n1!n2!...nk!\frac{n!}{n_1!n_2!...n_k!}
n1!n2!...nk!n!
证明同上证明同上证明同上
若 n1=n2=n3=...=nk,n_1=n_2=n_3=...=n_k,n1=n2=n3=...=nk, 且这些盒子没有标签 ,,, 那么方案数为
n!k!n1!n2!...nk!\frac{n!}{k!n_1!n_2!...n_k!}
k!n1!n2!...nk!n!
定理4
有 kkk 种颜色,共 nnn 个车 ,,, 第一种颜色有 n1n_1n1 个 ,,, 第二种颜色有 n2n_2n2 个 ,⋯,\cdots,⋯ 第 kkk 种颜色有 nkn_knk 个 ... 把这些车放在 n∗nn*nn∗n 的棋盘上使得车之间不得互相攻击的方案数等于
(n!)2n1!n2!⋯nk!\frac{(n!)^2}{n_1!n_2!\cdots n_k!}
n1!n2!⋯nk!(n!)2
证明:证明:证明:
每一行上都恰有一个车 ,,, 每一列上也恰有一个车 ,,, 所有行上的车所在的列数可以看成为一个排列 ,,, 那么假设这些车都相同 ,,, 共有 n!n!n! 种选择,把这 nnn 个车分给 kkk 个颜色的方案数见 $1.4.3 , $再使用乘法原理即可得到答案
多重集合的组合
Combinations of Multisets
定理1
设 SSS 为 kkk 种类型元素的多重集合 ,,, 每种元素的重复数至少为 nnn 个 ,,, 则 SSS 的 nnn 组合为
(n+k−1n)=(n+k−1k−1){n+k-1\choose n}={n+k-1\choose k-1}
(nn+k−1)=(k−1n+k−1)
证明:证明:证明:
SSS 的 nnn 组合数即为方程 x1+x2+⋯+xk=nx_1 +x_2+\cdots+x_k=nx1+x2+⋯+xk=n 的非负整数解的个数
我们令多重集合 T={n⋅1,(k−1)⋅∗}T= \begin{Bmatrix} n\cdot 1,(k-1)\cdot * \end{Bmatrix}T={n⋅1,(k−1)⋅∗}
在T的一个排列中 ,∗,*,∗ 之间的 111 的数量表示 xix_ixi 的值, TTT 的每一种排列都对应着上述方程的一组解 ,,, 所以 TTT 的排列数就是上述方程解的个数 ,,, 为
(n+k−1)!n!(k−1)!=(n+k−1n)\frac{(n+k-1)!}{n!(k-1)!}={n+k-1\choose n}
n!(k−1)!(n+k−1)!=(nn+k−1)
例1
每一项都是 [1,k][1,k][1,k] 之间的整数 ,,, 长度为 nnn 的非递减序列的个数是多少
解:解:解:
相当于求 S={∞⋅1,∞⋅2,⋯ ,∞⋅k}S= \begin{Bmatrix} \infty\cdot 1,\infty\cdot 2, \cdots,\infty \cdot k \end{Bmatrix}S={∞⋅1,∞⋅2,⋯,∞⋅k} 的 nnn 组合数 ,,, 为
(n+k−1n){n+k-1 \choose n}
(nn+k−1)
例2
x1+x2+⋯+xk=nx1≥a1,x2≥a2,⋯ ,xk≥akx_1 +x_2+\cdots+x_k=n\\
x_1 \geq a_1 , x_2 \geq a_2 , \cdots , x_k \geq a_k
x1+x2+⋯+xk=nx1≥a1,x2≥a2,⋯,xk≥ak
方程的整数解的个数是多少
解:解:解: 我们引入新变量
y1=x1−a1,y2=x2−a2,⋯ ,yk=xk−aky1+y2+⋯+yk=n−a1−a2−⋯−aky_1=x_1-a_1,y_2=x_2-a_2, \cdots , y_k=x_k-a_k\\
y_1 + y_2+\cdots+y_k=n -a_1-a_2-\cdots -a_k
y1=x1−a1,y2=x2−a2,⋯,yk=xk−aky1+y2+⋯+yk=n−a1−a2−⋯−ak
所以我们将问题转化成了定理1