【转】排列组合与杨辉三角

绪论:加法原理、乘法原理

分类计数原理:完成一件事,有 n 类办法,在第 1 类办法中有 m_1 种不同的方法,在第 2 类办法中有 m_2 种不同的方法 … 在第 n 类办法中有 m_n 种不同的方法,那么完成这件事共有 N=m_1+m_2+...+m_n 种不同的方法。

分步计数原理:完成一件事,需要分成 n 个步骤,做第 1 步有 m_1 种不同的方法,做第 2 步有 m_2 种不同的方法 … 做第 n 步有 m_n 种不同的方法,那么完成这件事共有 N=m_1\times m_2\times ...\times m_n 种不同的方法。

区别:分类计数原理是加法原理,不同的类加起来就是我要得到的总数;分步计数原理是乘法原理,是同一事件分成若干步骤,每个步骤的方法数相乘才是总数。

排列问题(需要排序)

排列数

n 个不同元素中取出 m(m\leq n) 个元素的所有不同排列的个数,叫做从 n 个不同元素中取出 m 个元素的排列数,用符号 A_n^m 表示。

排列数公式

\begin{aligned}A_n^m=n(n-1)(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!},\quad n,m\in \mathbb{N}^* \quad and\quad m\leq n\end{aligned}

规定 0!=1

排列数推导

n 个不同的元素任选 m 个排序,按计数原理分步进行:

取第一个:有 n 种取法;
取第二个:有 (n-1) 种取法;
取第三个:有 (n-2) 种取法;
……
取第 m 个:有 (n-m+1) 种取法;

根据分步乘法原理,得出上述公式。

排列数性质

A_n^m = nA_{n-1}^{m-1} 可理解为:“ 某特定位置 ” 先安排,再安排其余位置。

A_n^m = mA_{n-1}^{m-1} + A_{n-1}^m 可理解为:含特定元素的排列有 mA_{n-1}^{m-1} ,不含特定元素的排列有 A_{n-1}^m ,具体解释如下所示:

A_3^2 = 2A_2^1 + A_2^2 为例,A_3^2 表示在数列 “ 123 ” 中找到两个元素进行排序,共有下列 6 个排列:

12 13 21 23 31 32

假设不包含 3 这个特定元素,不含特定元素的排列有 A_2^2 ,那么就是指的 12 和 21 ,也就是相当于从数列 “ 12 ” 中取出 2 个元素进行排列;含特定元素的排列有 2A_2^1 ,那么就是指的 13 、23 、31 和 32 ,也就是相当于从两个数列 “ 12 ” 和 “ 12 ” 中取出 1 个元素进行排列(把数列中的 “ 3 ” 全部挖掉)。

组合问题(不需要排序)

组合数

n 个不同元素中取出 m(m\leq n) 个元素的所有不同组合的个数,叫做从 n 个不同元素中取出 m 个元素的组合数,用符号 C_n^m 表示。

组合数公式

\begin{aligned}C_n^m=\frac{A_n^m}{A_m^m}=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!}=\frac{n!}{m!(n-m)!},\quad n,m\in \mathbb{N}^* \quad and\quad m\leq n\end{aligned}

C_n^0=C_n^n=1

组合数推导

利用排列和组合之间的关系以及排列的公式来推导证明。

将部分排列问题 A_n^m 分解为两个步骤:

第一步,就是从 n 个球中抽 m 个出来,先不排序,此即组合数问题 C_n^m

第二步,则是把这 m 个被抽出来的球进行排序,即全排列 A_m^m

根据乘法原理,A_n^m=C_n^m A_m^m ,那么:

\begin{aligned}C_n^m=\frac{A_n^m}{A_m^m}=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!}=\frac{n!}{m!(n-m)!}\end{aligned}

组合数性质

C_n^m = C_n^{n-m}  可以理解为:将原本的每个组合都反转,把原来没选的选上,原来选了的去掉,这样就变成从 n 个元素中取出 n - m 个元素,显然方案数是相等的。

递推公式 C_n^m=C_{n-1}^m+C_{n-1}^{m-1} 可理解为:含特定元素的组合有 C_{n-1}^{m-1} ,不含特定元素的组合有 C_{n-1}^m ,具体解释如下所示:

C_5^2 = C_4^2 + C_4^1 为例,C_5^2 表示在数列 “ 12345 ” 中找到两个元素的组合,共有下列 10 个组合:

12 13 14 15 23 24 25 34 35 45

假设不包含 1 这个特定元素,不含特定元素的组合有 C_4^2 ,那么就是指的 23 、24 、25 、34 、35 和 45 ,也就是相当于从数列 “ 2345 ” 中取出 2 个元素进行组合;含特定元素的组合有 C_4^1 ,那么就是指的 12 、13 、14 和 15 ,也就是相当于从数列 “ 2345 ” 中取出 1 个元素进行组合(把数列中的 “ 1 ” 全部挖掉)。

组合数求和公式

C_n^0+C_n^1+C_n^2+\cdots+C_n^n=2^n

我们感性认知一下,上面这个式子的左边表示什么呢?

把从 n 个球中抽出 0 个球的组合数(值为 1 )、抽出 1 个球的组合数、抽出 2 个球的组合数 … 抽出 n 个球的组合数相加。

换句话说,就是从 n 个球中随便抽出一些不定个数的球,问一共有多少种组合。

对于第 1 个球,可以选,也可以不选,有 2 种情况;
对于第 2 个球,可以选,也可以不选,有 2 种情况;
对于任意一个球,可以选,也可以不选,有 2 种情况。

根据乘法原理,一共 \underbrace{2\times 2\times \cdots \times 2}_{n} = 2^n 种组合。

组合数求和公式推导

想要严谨的证明?可用数学归纳法:

1 、当 m = 1 时,C_1^0+C_1^1=2=2^1 成立。

2 、假设 n=k(k\in \mathbb{N}^*) 时等式成立,即

\begin{aligned}\sum_{i=0}^{k} C_k^i=2^n\end{aligned}

n=k+1 时,

\begin{aligned} & C_{k+1}^0 + C_{k+1}^1 + C_{k+1}^2 + \cdots + C_{k+1}^{k} + C_{k+1}^{k+1}\\ = & C_{k+1}^0+ \left(C_k^0+C_k^1\right) + \left(C_k^1+C_k^2\right) + \cdots + \left(C_k^{k-1}+C_k^k\right) + C_{k+1}^{k+1}\\ = & \left(C_k^0 + C_k^1 + C_k^2 + \cdots + C_k^k\right) + \left(C_k^0 + C_k^1 + C_k^2 + \cdots + C_k^k\right)\\ = & 2 \times 2^k\\ = & 2^{k+1} \end{aligned}

等式也成立。

3 、由 1 和 2 得,等式对 n\in \mathbb{N}^* 都成立。

也可偷懒地用二项式定理证明(其实二项式定理也是用数学归纳法证明的):

\begin{aligned}(a+b)^n=\sum_{k=0}^{n}C_n^k a^{n-k}b^k\end{aligned}

a=b=1 ,就得到了:

\begin{aligned}\sum_{i=0}^{n} C_n^i=2^n\end{aligned}

杨辉三角

这个神奇的图形和组合数、二项式定理密切相关。

杨辉三角
杨辉三角

杨辉三角可以帮助你更好地理解和记忆组合数的性质:

  1. n 行的第 m 个数可表示为 C_{n-1}^{m-1} ,即为从 n-1 个不同元素中取 m-1 个元素的组合数;
  2. n 行的数字有 n 项;
  3. 每行数字左右对称(第 n 行的第 m 个数和第 n-m+1 个数相等,C_n^m = C_n^{n-m}),由 1 开始逐渐变大;
  4. 每个数等于它上方两数之和(第 n+1 行的第 i 个数等于第 n 行的第i-1 个数和第 i 个数之和,即 C_{n+1}^i=C_n^i + C_n^{i-1});
  5. (a+b)^n 的展开式中的各项系数依次对应杨辉三角的第 n+1 行中的每一项(二项式定理)。

 

转自:

  • https://www.cnblogs.com/1024th/p/10623541.html
打赏 赞(0)
比特币钱包
以太坊钱包
比特币钱包二维码图片

比特币钱包扫描二维码打赏

以太坊钱包二维码图片

以太坊钱包扫描二维码打赏

Was this article helpful?

Related Articles

Leave A Comment?

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据