排列组合问题

hymcr052024-09-172024-12-15

排列公式

从 $n$ 个数中选出 $m$ 个数并且排序。

公式推导：

A^2_3 = 3 \times 2 = 6\\3_6 = 6 \times 5 \times 4 = 120\\ A^2_6 = 6 \times 5 = 30\\ \therefore A^m_n = n(n-1)(n-2)\dots (n-m+1)\\ 又\because n!=n\times (n-1)\times (n-2) \dots \times 2\times 1 \\ 综上所述：A^m_n = \frac{n!}{(n-m)!}

组合公式

从 $n$ 个数中选出 $m$ 个数。

公式推导：

C^m_n=\frac{A^m_n}{A^m_m}=\frac{n(n-1)(n-2)\dots(n-m+1)}{m!}\\ c^m_n=\frac{n!}{(n-m)!}\\ 特殊的：C^0_1 = 1

例题

例一

一位教练的足球队共有 $17$ 名初级学员，他们中以前没有一人参加过比赛。按照足球比赛规则，比赛时一个足球队的上场队员是 $11$ 人。

问：
（1）这位教练从这 $17$ 名学员中可以形成多少种学员上场方案？
（2）如果在选出 $11$ 名上场队员时，还要确定其中的守门员，那么教练员有多少种方式做这件事情？

解答：
（1） $C^{11}_{17} = 12376$
（2） $C^{1}_{17} \times C^{10}_{16}= 12376$ （先找出守门员有多少种选取方案，再找出其余由多少种选择方案）

例二

（1）平面内有 $10$ 个点，以其中每 $2$ 个点为端点的线段共有多少条？
（2）平面内有 $10$ 个点，以其中每 $2$ 个点为端点的有向线段共有多少条？

解答：
（1） $C^2_{10} = 45$ （显然是在 $10$ 个点中选取 $2$ 个点）
（2） $A^2_{10} = 90$ （因为是有向线段所以选择 a,b 和选择 b,a 是不一样的，于是属于排列）

例三

（1）凸五边形有多少条对角线？
（2）凸 $n(n>3)$ 边形有多少条对角线？

解答：
（1）
alt text
根据图片，我们可以证出凸五边形有 $5$ 条对角线。同时我们可以这样理解：
对角线即为在图形中选择两个点，但是我们不能选到边，可得出公式： $C^2_5-5=5$ （减去边的数量）。
（2）可以根据上面的公式得出： $C^2_n-n$ 。

知识点小结

1、分类计数原理：做一件事情，完成它可以有 $n$ 类办法，在第二类办法中有 $m_1$ 种不同剖方法，在第二类办法中有 $m_2$ 种不同的方法， ……，在第 $n$ 类办法中有 $m_n$ 种不同的方法。
那么完成这件事共有 $N=m_1+m_2+\ldots+m_n$ 种不同的方法。

2、分步计数原理：做一件事情，完成它需要分成 $n$ 个步骤，做第一步有 $m_1$ 种不同的方法，做第二步有 $m_2$ 种不同的方法， ……，做第 n 步有 $m_n$ 种不同的方法，那么完成这件事有 $N=\ldots m_1{ }^ \times m_2{ }^ \times \ldots m_n$ 种不同的方法。