202606161406排列组合

排列组合

1 排列数

问题引入：有 $n$ 个座位，坐 $n$ 个同学，请问有多少种坐法？

对于第一个座位，可以从 $n$ 个同学里面任选一个坐，所以共有 $n$ 种选择。对于第二个座位，只能从剩下的 $n-1$ 个同学中挑一个坐，故有 $n-1$ 种选择。依此类推，最后一个座位，只剩最后一位同学，只有 $1$ 种选择。根据乘法原理共有，

$$n\times (n-1)\times \cdots \times 1=n!\triangleq A_n^n$$

种坐法。不失一般性，我们把它记为 $A_n^k$，叫做排列数，其含义是从 $n$ 个里面选 $k$ 个做排列，共有多少种排列方法。如无特殊说明，默认 $k\le n$.

类似的，3个座位，5个同学，有多少种坐法？第一个座位可选5，第二个可选4，第三个可选3，共有 $5\times 4\times 3=A_5^3$ 种坐法。再类似的，5个座位，3个同学，有多少种坐法？第一个同学任选5个座位，第二个任选余下的4个，第三个任选余下的3个，所以共有 $5\times 4\times 3=A_5^3$ 种坐法。一般的，

$$A_n^k=\underset{k项相乘}{\underbrace{n\times (n-1)\times \cdots \times (n-k+1)}}=\frac{n!}{(n-k)!}$$

特别的，称 $A_n^n=n!$ 为 $n$ 的全排列。

2 组合数

问题引入：有 $n$ 个同学，挑 $k$ 个去参加活动，请问有多少种挑法？

现在我们只是要挑选出来，不要求做排列。如果考虑挑出 $k$ 个同学按顺序落座，那么答案显然就是 $A_n^k$. 但我们其实不考虑顺序，想象一下，这件事我们其实分了两步，

1. 挑选 $k$ 个同学出来，
2. 给 $k$ 个同学落座（做排列）

其实我们想要的是第一步的答案，但我们额外做了 $k$ 个同学的全排列。因此，要在结果种去掉这些重复的。所以从 $n$ 选 $k$，不考虑顺序，共有，

$$\frac{A_n^k}{A_k^k}=\frac{n!}{(n-k)!\times k!}\triangleq C_n^k$$

种选法，我们把这个数叫做组合数。有些教材也用下面的记号表示组合数，

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{(n-k)!\cdot k!}$$