数学 - 排列与组合 (高中教科书 笔记)

创建时间:
2018-09-28 22:51
最近更新:
2018-09-28 23:05

Source

本文内容摘自 《人教版高中数学A版选修2-3__普通高中课程标准实验教科书_数学_选修2-3_A版_人民教育出版社_扫描版.pdf》 第一章 计数原理。

1.1 分类加法计数原理 与 分步乘法计数原理

  • 分类加法计数原理: (最重要的特征是 "或" 字的出现) 完成一件事有两类不同方案 (两类不同方案中的方法互不相同),在第 1 类方案中有 m 种不同的方法,在第 2 类方案中有 n 种不同的方法,那么完成这件事共有 N=m+n 种不同的方法。
  • 分步乘法计数原理: (最重要的特征是 "和" 字的出现) 完成一件事需要两个步骤 (无论第 1 步采用哪种方法,都不影响第 2 步方法的选取),做第 1 步有 m 种不同的方法,做第 2 步有 n 种不同的方法,那么完成这件事共有 N=m*x 种不同的方法。
  • 分类加法计数原理 和 分步乘法计数原理,回答的都是有关做一件事的不同方法的种数问题。区别在于: 分类加法计数原理 针对的是 "分类" 问题,其中各种方法相互独立,用其中任何一种方法都可以做完这件事; 分步乘法计数原理 针对的是 "分步" 问题,各个步骤中的方法互相依存,只有各个步骤都完成才算做完这件事。
  • 用两个 计数原理 解决计数问题时,最重要的是 在开始计算之前要进行仔细分析 -- 需要分类还是需要分步。
  • 分类要做到 "不重不漏"。分类后再分别对每一类进行计数,最后用 分类加法计数原理 求和,得到总数。
  • 分步要做到 "步骤完整" -- 完成了所有步骤,恰好完成任务,当然步与步之间要相互独立。分步后再计算每一步的方法数,最后根据 分步乘法计数原理,把完成每一步的方法数相乘,得到总数。
  • 子集的个数: n 元集合 A={a1, a2, ..., an} 的不同子集有 2^n 个。证明: 集合中的任一元素 是否在任一子集中 只有两种可能 -- 元素i∈子集i元素i∉子集i,根据 分步乘法计数原理,对于由 n 个元素组成的集合,共有 2*2*...*2=2^n 个不同的子集。

1.2 排列 与 组合

1.2.1 排列

  • 一般地,从 n 个不同元素中取出 m (m≤n) 个元素,按照一定的顺序排成一列,叫做从 n 个不同元素中取出 m 个元素的一个 排列 (arrangement)
  • 根据排列的定义,两个排列相同,当且仅当两个排列的元素完全相同,且元素的排列顺序也相同。
  • n 个不同元素中 取出 m (m≤n) 个元素的 所有不同排列的个数 叫做 "从 n 个不同元素中 取出 m 个元素的 排列数",用符号 Amn (TonyNote: m 为上标、n 为下标) 表示。
  • 排列数公式: Amn=n(n-1)(n-2)...(n-m+1)n, m∈N+m≤n
  • 排列数公式 还可以写成 Amn=(Ann)/[A(n-m)(n-m)]=n!/(n-m)!
  • 可证得 Amn=nA(m-1)(n-1)
  • n 个不同元素全部取出的一个排列,叫做 "n 个元素的一个 全排列"。这时公式中 m=n,即有 Ann=n(n-1)(n-2)...3*2*1,就是说,n 个不同元素全部取出的排列数,等于正整数 1n连乘积。正数 1n 的 连乘积,叫做 n阶乘,用 n! 表示。所以 n 个不同元素的 全排列数公式 可以写成 Ann=n!。另外,我们规定 0!=1

1.2.2 组合

  • 一般地,从 n 个不同元素中取出 m (m≤n) 个元素 合成一组,叫做从 n 个不同元素中取出 m 个元素的一个 组合 (combination)
  • 排列、组合 的 共同点: 两者都是 "从 n 个不同元素中取出 m (m≤n) 个元素"。
  • 排列、组合 的 不同点: 排列 与元素的顺序有关; 组合 与元素的顺序无关。只有元素相同且顺序也相同的两个排列才是相同的; 只要两个组合的元素相同,不论元素的顺序如何,都是相同的组合。
  • n 个不同元素中 取出 m (m≤n) 个元素的 所有不同组合的个数 叫做 "从 n 个不同元素中 取出 m 个元素的 组合数",用符号 Cmn (TonyNote: m 为上标、n 为下标) 表示。组合数 还可用符号 {nm} 表示 (TonyNote: n 为上标、m 为下标)。
  • 元素相同 顺序不同 的 两个组合 相同。
  • 元素相同 顺序不同 的 两个排列 不同。
  • 组合数公式: 求从 n 个不同元素中取出 m 个元素的排列数,可看作由以下 2 个步骤得到的: 第 1 步,从这 n 个不同元素中取出 m 个元素,共有 Cmn 种不同的取法; 第 2 步,将取出的 m 个元素做全排列,共有 Amm 种不同的排法。根据 分步乘法计数原理,有 Amn=Cmn*Amm。因此 Cmn=Amn/Amm=[n(n-1)(n-2)...(n-m+1)]/(m!),这里 n, m∈N*,并且 m≤n,这个公式叫做 组合数公式。因为 Amn=n!/(n-m)!,所以,上面的 组合数公式 还可以写成 Cmn=n!/[m!(n-m)!],另外,我们规定 C0n=1
  • 组合数 性质一: 一般地,从 n 个不同元素中取出 m 个元素后,必然剩下 n-m 个元素,因此从 n 个不同元素中取出 m 个元素的组合,与剩下的 `n-m`` 个元素的组合一一对应。这样,从 n 个不同元素中取出 `m 个元素的组合数,等于从这 n 个不同元素中取出 n-m 个元素的组合数。于是我们有 Cmn=C(n-m)n。由于 C0n=1,因此上面的等式在 m=n 时也成立。
  • 组合数 性质一 的证明: C(n-m)n=n!/[(n-m)![n-(n-m)]!]=n!/[m!(n-m)!]=Cmn
  • 组合数 性质一 的特征: 等式两边 下标相同 且 上标之和等于下标。
  • 组合数 性质一 的作用一: 当 m>n/2 时,用 C(n-m)n 代替 Cmn 来简化运算。
  • 组合数 性质一 的作用二: Cxn=Cyn 可推导出 x=y 或者 x+y=n
  • 组合数 性质二: 一般地,从 n+1 个不同元素中取出 m 个元素的组合数是 Cm(n+1),这些组合可以分为两类: 一类不含有元素 ax、另一类含有元素 ax。不含有 ax 的组合是从 n 个元素中取出 m 个元素组成的,共有 Cmn 个; 含有 ax 的组合是从 n 个元素中取出 m-1 个元素与 ax 组成的,共有 C(m-1)n 个。根据 分类加法计数原理 可以得到 组合数 性质二 Cm(n+1)=Cmn+C(m-1)n
  • 组合数 性质二 的证明: Cmn+C(m-1)n={n!/[m!(n-m)!]}+{n!/[(m-1)!(n-(m-1))!]}=[n!(n-m+1)+n!m]/[m!(n-m+1)!]=(n+1)!/[m!(n+1-m)!]=Cm(n+1)
  • 组合数 性质二 的特征: 下标相同而上标差1 的两个组合数 之和,等于 下标比原下标多1 而 上标与大的相同 的一个组合数。
  • 组合数 性质二 的作用: 恒等变形、简化运算。在之后的 "二项式定理" 中 会看到它的主要应用。
  • 可证得 C0n+C1n+...+Cnn=2^n,因为可将其理解为 n 二进制 的全部组合情况。
  • 可证得 Cnn+Cn(n+1)+...+Cn(n+m)=C(n+1)(n+m+1),因为 Cnn=C(n+1)(n+1),代入等式后 与第二个加数 按 组合数性质二 求和,该和与第三个加数也符合 组合数性质二,以此类推可至最后一个加数。此公式可解 C22+C23+...+C29C04+C15+C26+...+C59 类型的题。
  • 组合数公式 可证得 Cmn=[(m+1)/(n+1)]*C[(m+1)(n+1)]

1.3 二项式定理

2018-09-28 Tony Note: 以后找时间再学习。

Resource

  1. 高二数学组合数的两个性质
  2. 组合数的性质 (2)