绪论:加法原理、乘法原理
分类计数原理:完成一件事,有 类办法,在第 1 类办法中有 种不同的方法,在第 2 类办法中有 种不同的方法 … 在第 类办法中有 种不同的方法,那么完成这件事共有 种不同的方法。
分步计数原理:完成一件事,需要分成 个步骤,做第 1 步有 种不同的方法,做第 2 步有 种不同的方法 … 做第 步有 种不同的方法,那么完成这件事共有 种不同的方法。
区别:分类计数原理是加法原理,不同的类加起来就是我要得到的总数;分步计数原理是乘法原理,是同一事件分成若干步骤,每个步骤的方法数相乘才是总数。
排列问题(需要排序)
排列数
从 个不同元素中取出 个元素的所有不同排列的个数,叫做从 个不同元素中取出 个元素的排列数,用符号 表示。
排列数公式
规定
排列数推导
把 个不同的元素任选 个排序,按计数原理分步进行:
取第一个:有 种取法;
取第二个:有 种取法;
取第三个:有 种取法;
……
取第 个:有 种取法;
根据分步乘法原理,得出上述公式。
排列数性质
可理解为:“ 某特定位置 ” 先安排,再安排其余位置。
可理解为:含特定元素的排列有 ,不含特定元素的排列有 ,具体解释如下所示:
以 为例, 表示在数列 “ 123 ” 中找到两个元素进行排序,共有下列 6 个排列:
12 13 21 23 31 32
假设不包含 3 这个特定元素,不含特定元素的排列有 ,那么就是指的 12 和 21 ,也就是相当于从数列 “ 12 ” 中取出 2 个元素进行排列;含特定元素的排列有 ,那么就是指的 13 、23 、31 和 32 ,也就是相当于从两个数列 “ 12 ” 和 “ 12 ” 中取出 1 个元素进行排列(把数列中的 “ 3 ” 全部挖掉)。
组合问题(不需要排序)
组合数
从 个不同元素中取出 个元素的所有不同组合的个数,叫做从 个不同元素中取出 个元素的组合数,用符号 表示。
组合数公式
组合数推导
利用排列和组合之间的关系以及排列的公式来推导证明。
将部分排列问题 分解为两个步骤:
第一步,就是从 个球中抽 个出来,先不排序,此即组合数问题 :
第二步,则是把这 个被抽出来的球进行排序,即全排列 。
根据乘法原理, ,那么:
组合数性质
可以理解为:将原本的每个组合都反转,把原来没选的选上,原来选了的去掉,这样就变成从 个元素中取出 个元素,显然方案数是相等的。
递推公式 可理解为:含特定元素的组合有 ,不含特定元素的组合有 ,具体解释如下所示:
以 为例, 表示在数列 “ 12345 ” 中找到两个元素的组合,共有下列 10 个组合:
12 13 14 15 23 24 25 34 35 45
假设不包含 1 这个特定元素,不含特定元素的组合有 ,那么就是指的 23 、24 、25 、34 、35 和 45 ,也就是相当于从数列 “ 2345 ” 中取出 2 个元素进行组合;含特定元素的组合有 ,那么就是指的 12 、13 、14 和 15 ,也就是相当于从数列 “ 2345 ” 中取出 1 个元素进行组合(把数列中的 “ 1 ” 全部挖掉)。
组合数求和公式
我们感性认知一下,上面这个式子的左边表示什么呢?
把从 个球中抽出 0 个球的组合数(值为 1 )、抽出 1 个球的组合数、抽出 2 个球的组合数 … 抽出 个球的组合数相加。
换句话说,就是从 个球中随便抽出一些不定个数的球,问一共有多少种组合。
对于第 1 个球,可以选,也可以不选,有 2 种情况;
对于第 2 个球,可以选,也可以不选,有 2 种情况;
对于任意一个球,可以选,也可以不选,有 2 种情况。
根据乘法原理,一共 种组合。
组合数求和公式推导
想要严谨的证明?可用数学归纳法:
1 、当 时, 成立。
2 、假设 时等式成立,即
当 时,
等式也成立。
3 、由 1 和 2 得,等式对 都成立。
也可偷懒地用二项式定理证明(其实二项式定理也是用数学归纳法证明的):
令 ,就得到了:
杨辉三角
这个神奇的图形和组合数、二项式定理密切相关。

杨辉三角可以帮助你更好地理解和记忆组合数的性质:
- 第 行的第 个数可表示为 ,即为从 个不同元素中取 个元素的组合数;
- 第 行的数字有 项;
- 每行数字左右对称(第 行的第 个数和第 个数相等,),由 1 开始逐渐变大;
- 每个数等于它上方两数之和(第 行的第 个数等于第 行的第 个数和第 个数之和,即 );
- 的展开式中的各项系数依次对应杨辉三角的第 行中的每一项(二项式定理)。
转自:
- https://www.cnblogs.com/1024th/p/10623541.html
发表评论?