排列数 P(n,k)

定义

排列：从n个不同元素中，选出k个元素，并且 考虑顺序，排成一列。

排列数记作：

\[P(n,k) \quad\text{或}\quad A_n^k\]

公式是：

\[P(n,k)=\frac{n!}{(n-k)!}\]

也可以写成：

\[P(n,k)=n(n-1)(n-2)\cdots(n-k+1)\]

也就是从n开始，连续乘k个数。

例子

从 (A,B,C) 三个字母中选 2 个，考虑顺序：

\[AB,\ BA,\ AC,\ CA,\ BC,\ CB\]

一共 6 种。

用公式：

\[P(3,2)=\frac{3!}{(3-2)!}=\frac{6}{1}=6\]

再比如从 6 个字里选 3 个，考虑顺序：

\[P(6,3)=6\cdot5\cdot4=120\]

---

组合数 \(\binom{n}{k}\)

定义

组合：从n个不同元素中，选出k个元素，不考虑顺序，只看选出了哪几个。

组合数记作：

\[\binom{n}{k} \quad\text{或}\quad C(n,k) \quad\text{或}\quad C_n^k\]

公式是：

\[\binom{n}{k} = \frac{n!}{k!(n-k)!}\]

也可以写成：

\[\binom{n}{k} = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}\]

例子

从 (A,B,C) 三个字母中选 2 个，不考虑顺序：

\[\{A,B\},\ \{A,C\},\ \{B,C\}\]

一共 3 种。

用公式：

\[\binom{3}{2} = \frac{3!}{2!(3-2)!} = \frac{6}{2\cdot1} = 3\]

再比如从 6 个字里选 3 个，不考虑顺序：

\[\binom{6}{3} = \frac{6!}{3!3!} = 20\]

---

排列和组合的关系

先不管顺序，从n个元素中选k个：

\[\binom{n}{k}=\frac{n!}{k!(n-k)!}\]

再把这k个元素排列：

\[k!\]

所以：

\[P(n,k)=\frac{n!}{k!(n-k)!}*k!=\binom{n}{k}\cdot k!=\frac{n!}{(n-k)!}\]

反过来：

\[\binom{n}{k}=\frac{P(n,k)}{k!}\]