科数网
公式
首页
初中
高中
高数
线代
概率
高中物理
赞助
在线教程
高中数学
统计与概率
计数原理
排列
最后更新:
2023-10-03 11:17
查看:
268
次
下载
编辑本文
科数网
排列
## 排列数 从 $n$ 个不同元素中,任取 $m$($m\leq n$,$m$ 与 $n$ 均为自然数,下同)个元素按照一定的顺序排成一列,叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列;从 $n$ 个不同元素中取出 $m$($m\leq n$) 个元素的所有排列的个数,叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列数,用符号 $\mathrm A_n^m$(或者是 $\mathrm P_n^m$)表示。 排列的计算公式如下: $$ \mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!} $$ $n!$ 代表 $n$ 的阶乘,即 $6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6$。 公式可以这样理解:$n$ 个人选 $m$ 个来排队 ($m \le n$)。第一个位置可以选 $n$ 个,第二位置可以选 $n-1$ 个,以此类推,第 $m$ 个(最后一个)可以选 $n-m+1$ 个,得: $$ \mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!} $$ 全排列:$n$ 个人全部来排队,队长为 $n$。第一个位置可以选 $n$ 个,第二位置可以选 $n-1$ 个,以此类推得: $$ \mathrm A_n^n = n(n-1)(n-2) \cdots 3 \times 2 \times 1 = n! $$ 全排列是排列数的一个特殊情况。 **定义** 抽屉原理,亦称鸽巢原理(the pigeonhole principle)。 它常被用于证明存在性证明和求最坏情况下的解。 简单情况 将 $n+1$ 个物体,划分为 $n$ 组,那么有至少一组有两个(或以上)的物体。 这个定理看起来比较显然,证明方法考虑反证法:假如每个分组有至多 $1$ 个物体,那么最多有 $1\times n$ 个物体,而实际上有 $n+1$ 个物体,矛盾。 例如:桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1个元素放到n个集合中去,其中必定有一个集合里至少有两个元素。” **推广** 将 $n$ 个物体,划分为 $k$ 组,那么至少存在一个分组,含有大于或等于 $\left \lceil \dfrac{n}{k} \right \rceil$ 个物品。 推广的形式也可以使用反证法证明:若每个分组含有小于 $\left \lceil \dfrac{n}{k} \right \rceil$ 个物体,则其总和 $S\leq (\left \lceil \dfrac{n}{k} \right \rceil -1 ) \times k=k\left\lceil \dfrac{n}{k} \right\rceil-k < k(\dfrac{n}{k}+1)-k=n$ 矛盾。 此外,划分还可以弱化为覆盖结论不变。 给定集合 $S$, 一个 $S$ 的非空子集构成的簇 $\{A_1,A_2\ldots A_k\}$ - 若满足 $\bigcup_{i=1}^k A_i$ 则称为 $S$ 的一个覆盖(cover) - 若一个覆盖还满足 $i\neq j\to A_i\cap A_j=\varnothing$ 则称为 $S$ 的一个划分。 鸽巢原理可以有如下叙述:对于 $S$ 的一个覆盖 $\{A_1,A_2\ldots A_k\}$ 有至少一个集合 $A_i$ 满足 $\left\vert A_i \right\vert \geq \left\lceil \dfrac{\left\vert S \right\vert}{k} \right\rceil$。 例题1:有300人到招聘会求职,其中软件设计有100人,市场营销有80人,财务管理有70人,人力资源管理有50人。那么至少有多少人找到工作才能保证一定有70人找的工作专业相同呢? 解:此时我们考虑的最差情况为:软件设计、市场营销和财务管理各录取69人,人力资源管理的50人全部录取,则此时再录取1人就能保证有70人找到的工作专业相同。因此至少需要69*3+50+1=258人。 根据第一抽屉原理之原理2推导:mn+1个人的时候必有m+1个人找到的工作专业相同,所以是要求出mn+1的人数,已知n=3,m+1=70。考虑到人力资源专业只有50人,得出mn+1=(69*3+50)+1=258人。 例题2:一个抽屉里有20件衬衫,其中4件是蓝的,7件是灰的,9件是红的,则应从中随意取出多少件才能保证有5件是同颜色的? 解:根据鸽巢原理,n个鸽巢,kn + 1只鸽子,则至少有一个鸽巢中有k + 1只鸽子。若根据鸽巢原理的推论直接求解,此时k=4,n=3,则应抽取 3 X 4 + 1 = 13件才能保证有5件同色。其实不然,问题的模型和鸽巢原理不尽相同。在解决该问题时,应该考虑最差的情况,连续抽取过程中抽取出4件蓝色的衬衣,即4件蓝色,取走后,问题变成有灰色和红色构成相同颜色的情况,这时,n=2,k + 1 = 5, k = 4. 故应取 4 + 4 X 2 + 1 = 13件。 问题分析:该情况下鸽巢原理的推论不再适用,由于蓝色的衬衫只有4件,而题目中要求有5件是同色的,导致4件蓝色衬衫都被抽取出这一最差情况的存在,所以应该先考虑最差情况,然后在此基础上再运用鸽巢原理。
上一篇:
组合
下一篇:
没有了
本文对您是否有用?
有用
(
0
)
无用
(
0
)
科数网知识库旨在打造一个可以顺序阅读的在线电子学习教程,点击顶部的
编辑本文
来完善本文,如果本文对您有用,我们感觉很高兴。 科数网目前处于严重的亏损状态,也欢迎
赞助我们
,支持本站的发展。
0
篇笔记
写笔记
更多笔记
提交笔记