排列组合的一些公式及推导(非常详细易懂)[通俗易懂]

排列组合的一些公式及推导(非常详细易懂)[通俗易懂]绪论:加法原理、乘法原理分类计数原理:做一件事,有$n$类办法,在第$1$类办法中有$m_1$种不同的方法,在第$2$类办法中有$m_2$种不同的方法,…,在第$n$类办法中有$m_n$种不同的方法

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

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

分类计数原理:做一件事,有\(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×m_2×\cdots ×m_n\)种不同的方法。

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

排列问题

排列数

\(n\)个不同元素种取出\(m(m\leq n)\)个元素的所有不同排列的个数,叫做从\(n\)个不同元素种取出\(m\)个元素的排列数,用符号\(\mathrm{A}_n^m\)表示。

排列数公式

\[\mathrm{A}_n^m=n(n-1)(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!},\quad n,m\in \mathbb{N}^* ,\text{并且}m\leq n \]

(规定\(0!=1\)

推导:把\(n\)个不同的元素任选\(m\)个排序,按计数原理分步进行

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

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

排列数性质

\(\mathrm{A}_n^m = n\mathrm{A}_{n-1}^{m-1}\) 可理解为“某特定位置”先安排,再安排其余位置。

\(\mathrm{A}_n^m = m\mathrm{A}_{n-1}^{m-1} + \mathrm{A}_{n-1}^m\) 可理解为:含特定元素的排列有\(m\mathrm{A}_{n-1}^{m-1}\),不含特定元素的排列为\(\mathrm{A}_{n-1}^m\)

组合问题

组合数

\(n\)个不同元素种取出\(m(m\leq n)\)个元素的所有不同组合的个数,叫做从\(n\)个不同元素种取出\(m\)个元素的组合数,用符号\(\mathrm{C}_n^m\)表示。

组合数公式

\[\mathrm{C}_n^m=\frac{\mathrm{A}_n^m}{\mathrm{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}^* ,\text{并且}m\leq n \]

\[\mathrm{C}_n^0=\mathrm{C}_n^n=1 \]

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

将部分排列问题\(\mathrm{A}_n^m\)分解为两个步骤:

第一步,就是从\(n\)个球中抽\(m\)个出来,先不排序,此即组合数问题\(\mathrm{C}_n^m\)

第二步,则是把这\(m\)个被抽出来的球排序,即全排列\(\mathrm{A}_m^m\)

根据乘法原理,\(\mathrm{A}_n^m=\mathrm{C}_n^m \mathrm{A}_m^m\),那么

\[\mathrm{C}_n^m=\frac{\mathrm{A}_n^m}{\mathrm{A}_m^m}=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!}=\frac{n!}{m!(n-m)!} \]

组合数的性质

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

递推公式\(\mathrm{C}_n^m=\mathrm{C}_{n-1}^m+\mathrm{C}_{n-1}^{m-1}\) 可理解为:含特定元素的组合有\(\mathrm{C}_{n-1}^{m-1}\),不含特定元素的排列为\(\mathrm{C}_{n-1}^m\)。还不懂?看下面。

Example

从1,2,3,4,5(\(n=5\))中取出2(\(m=2\))个元素的组合(\(\mathrm{C}_n^m\)):

12 13 14 15 23 24 25 34 35 45

显然,这些组合中要么含有元素“1”,要么不含。

  • 其中含有“1”的是:12 13 14 15

    把里面的“1”都挖掉:2 3 4 5

    而上面这个等价于从2,3,4,5(\(n-1\))中取出1(\(m-1\))个元素的组合。

  • 其中不含“1”的是:23 24 25 34 35 45
    上面等价于从2,3,4,5(\(n-1\))中取出2(\(m\))个元素的组合。

而总方案数等于上面两种情况方案数之和,即\(\mathrm{C}_n^m=\mathrm{C}_{n-1}^m+\mathrm{C}_{n-1}^{m-1}\)

组合数求和公式

\[\mathrm{C}_n^0+\mathrm{C}_n^1+\mathrm{C}_n^2+\cdots+\mathrm{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\text{个2相乘}} = 2^n\)种组合。

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

  1. \(n=1\)时,\(\mathrm{C}_1^0+\mathrm{C}_1^1=2=2^1\)成立。
  2. 假设\(n=k(k\in \mathbb{N}^*)\)时等式成立,即

    \[\sum_{i=0}^{k} \mathrm{C}_k^i=2^n \]

    成立,当\(n=k+1\)时,

    \[\begin{aligned} & \mathrm{C}_{k+1}^0 + \mathrm{C}_{k+1}^1 + \mathrm{C}_{k+1}^2 + \cdots + \mathrm{C}_{k+1}^{k} + \mathrm{C}_{k+1}^{k+1}\\ = & \mathrm{C}_{k+1}^0+ \left(\mathrm{C}_k^0+\mathrm{C}_k^1\right) + \left(\mathrm{C}_k^1+\mathrm{C}_k^2\right) + \cdots + \left(\mathrm{C}_k^{k-1}+\mathrm{C}_k^k\right) + \mathrm{C}_{k+1}^{k+1}\\ = & \left(\mathrm{C}_k^0 + \mathrm{C}_k^1 + \mathrm{C}_k^2 + \cdots + \mathrm{C}_k^k\right) + \left(\mathrm{C}_k^0 + \mathrm{C}_k^1 + \mathrm{C}_k^2 + \cdots + \mathrm{C}_k^k\right)\\ = & 2 \times 2^k\\ = & 2^{k+1} \end{aligned}\]

    等式也成立。

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

也可偷懒地用二项式定理证明:

\[(a+b)^n=\sum_{k=0}^{n}\mathrm{C}_n^k a^{n-k}b^k \]

\(a=b=1\),就得到了

\[\sum_{i=0}^{n} \mathrm{C}_n^i=2^n \]

类似的公式(由\(\mathrm{C}_n^m = \mathrm{C}_n^{n-m}\)推导):

\[\mathrm{C}_n^0 + \mathrm{C}_n^2 + \mathrm{C}_n^4 + \cdots = \mathrm{C}_n^1 + \mathrm{C}_n^3 + \mathrm{C}_n^5 + \cdots =2^{n-1} \]

杨辉三角

这个神奇的图形和组合数、二项式定理密切相关。(图片来自百度百科)

排列组合的一些公式及推导(非常详细易懂)[通俗易懂]

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

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

以下来自维基百科(我只是随便贴这)

二项式系数

二项式系数可排列成帕斯卡三角形。
在数学上,二项式系数是二项式定理中各项的系数。一般而言,二项式系数由两个非负整数\(n\)\(k\)为参数决定,写作,定义为的多项式展开式中,项的系数,因此一定是非负整数。如果将二项式系数写成一行,再依照顺序由上往下排列,则构成帕斯卡三角形。 \(\tbinom nk {\displaystyle (1+x)^{n}}x^{k}{\displaystyle {\binom {n}{0}},{\binom {n}{1}},\dots ,{\binom {n}{n}}}{\displaystyle n=0,1,2,\dots }\)

二项式系数常见于各数学领域中,尤其是组合数学。事实上,可以被理解为从\(n\)个相异元素中取出\(k\)个元素的方法数,所以大多读作「\(n\)\(k\)」。二项式系数的定义可以推广至\(n\)是复数的情况,而且仍然被称为二项式系数。

二项式系数亦有不同的符号表达方式,包括:\(C(n,k)\)\(_n\mathrm{C}_k\)\(^n\mathrm{C}_k\)、、[注3],其中的C代表组合(combinations)或选择(choices)。很多计算机使用含有C的变种记号,使得算式只占一行的空间,相同理由也发生在置换数,例如写作\(P( n , k )\)\({\displaystyle \mathrm{C}_{n}^{k}}{\displaystyle \mathrm{C}_{k}^{n}}{\displaystyle P_{k}^{n}}\)

定义及概念
对于非负整数\(n\)\(k\),二项式系数定义为的多项式展开式中,项的系数,即 \(\tbinom nk{\displaystyle (1+x)^{n}}x^{k}\)

\({\displaystyle (1+x)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}={\binom {n}{0} }+{\binom {n}{1}}x+\cdots +{\binom {n}{n}}x^{n}}\)
事实上,若\(x\)\(y\)为交换环上的元素,则

\((x+y)^n=\sum_{k=0}^n\binom nk x^{n-k}y^k\)

此数的另一出处在组合数学,表达了从\(n\)物中,不计较次序取\(k\)物有多少方式,亦即从一\(n\)元素集合中所能组成\(k\)元素子集的数量。

计算二项式系数

除展开二项式或点算组合数量之外,尚有多种方式计算的值。 \(\tbinom nk\)

递归公式
以下递归公式可计算二项式系数:

\(\binom nk = \binom{n-1}{k-1} + \binom{n-1}k \quad \forall n,k\in\N\)

其中特别指定:

\(\binom n0 = 1 \quad \forall n\in\N\cup\{0\}, \binom 0k = 0 \quad \forall k\in\N\).

此公式可由计算(1 + X ) n −1 (1 + X )中的X k项,或点算集合{1, 2, …, n }的k个元素组合中包含n与不包含n的数量得出。

显然,如果k > n,则。而且对所有n,,故此上述递归公式可于此等情况下中断。递归公式可用作建构帕斯卡三角形。 \tbinom nk=0\tbinom nn=1

帕斯卡三角形(杨辉三角)

有关二项式系数的恒等式

关系式

阶乘公式能联系相邻的二项式系数,例如在k是正整数时,对任意n有:

\[{\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}} \]

\[\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1} \]

\[\binom {n-1}{k} – \binom{n-1}{k-1} = \frac{n-2k}{n} \binom{n}{k} \]

两个组合数相乘可作变换:

\[\binom ni \binom im=\binom nm \binom {n-m}{i-m} \]

\[\sum_{r=0}^n \binom nr = 2^{n} \]

\[{\displaystyle \sum _{r=0}^{k}{\binom {n+r-1}{r}}={\binom {n+k}{k}}} \]

\[{\displaystyle \sum _{r=0}^{n-k}{\frac {(-1)^{r}(n+1)}{k+r+1}}{\binom {n-k}{r} }={\binom {n}{k}}^{-1}} \]

\[\sum_{r=0}^n \binom {dn}{dr}=\frac{1}{d}\sum_{r=1}^d (1+e^{\frac{2 \pi ri}{ d}})^{dn} \]

\[\sum_{i=m}^n \binom {a+i}{i} = \binom {a+n+1}{n} – \binom {a+m}{m-1} \]

\[\binom {a+m}{m-1} + \binom {a+m}{m} + \binom {a+m+1}{m+1} + … + \binom {a+n} {n} = \binom {a+n+1}{n} \]

\[F_n=\sum_{i=0}^{\infty} \binom {ni}{i} \]

\[F_{n-1}+F_n=\sum_{i=0}^{\infty} \binom {n-1-i}{i}+\sum_{i=0}^{\infty} \binom {n-i }{i}=1+\sum_{i=1}^{\infty} \binom {n-i}{i-1}+\sum_{i=1}^{\infty} \binom {n-i}{i} =1+\sum_{i=1}^{\infty} \binom {n+1-i}{i}=\sum_{i=0}^{\infty} \binom {n+1-i}{ i}=F_{n+1} \]

主条目:朱世杰恒等式

\[ \sum_{i=m}^n \binom ia = \binom {n+1}{a+1} – \binom {m}{a+1} \]

\[\binom {m}{a+1} + \binom ma + \binom {m+1}a … + \binom na = \binom {n+1}{a+1} \]

二阶求和公式

\[{\displaystyle \sum _{r=0}^{n}{\binom {n}{r}}^{2}={\binom {2n}{n}}} \]

\[\sum_{i=0}^n \binom {r_1+n-1-i}{r_1-1} \binom {r_2+i-1}{r_2-1}=\binom {r_1+r_2+n-1 }{r_1+r_2-1} \]

\[(1-x)^{-r_1} (1-x)^{-r_2}=(1-x)^{-r_1-r_2} \]

\[(1-x)^{-r_1} (1-x)^{-r_2}=(\sum_{n=0}^{\infty} \binom {r_1+n-1}{r_1-1} x^ n)(\sum_{n=0}^{\infty} \binom {r_2+n-1}{r_2-1} x^n)=\sum_{n=0}^{\infty} (\sum_{ i=0}^n \binom {r_1+n-1-i}{r_1-1} \binom {r_2+i-1}{r_2-1}) x^n \]

\[(1-x)^{-r_1-r_2}=\sum_{n=0}^{\infty} \binom {r_1+r_2+n-1}{r_1+r_2-1} x^n \]

主条目:范德蒙恒等式

\[\sum_{i=0}^k \binom ni \binom m{k-i}=\binom {n+m}k \]

三阶求和公式
主条目:李善兰恒等式

\[{\binom {n+k}k}^2=\sum_{j=0}^k {\binom kj}^2 \binom {n+2k-j}{2k} \]

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168057.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 嵌入式Linux开发流程_嵌入式开发一般采用什么方式

    嵌入式Linux开发流程_嵌入式开发一般采用什么方式在学习嵌入式开发的过程中,尤其是开始入门时,包括各种各样的教程,都是在讲学习linux,很少讲如何利用linux来开发属于自己的嵌入式项目,也就是没有一个全局的概念,简单理解,大概流程如下:一、建立开发环境   操作系统当然是LInux,或者在win系统下安装虚拟机,通过网络下载相应的GCC交叉编译器进行安装,或者安装产品厂家提供的交叉编译器。  这一步,就相当于在win系统下,要

    2022年10月26日
  • Academic social networks: Modeling, analysis, mining and applications 2019翻译[通俗易懂]

    Academic social networks: Modeling, analysis, mining and applications 2019翻译[通俗易懂]Academicsocialnetworks:Modeling,analysis,miningandapplications摘要:在快速增长的学术大数据背景下,社交网络技术最近引起了学术界和工业界的广泛关注。学术社会网络的概念正是在学术大数据的背景下产生的,指的是由学术实体及其关系形成的复杂的学术网络。有大量的学术大数据处理方法来分析学术社交网络丰富的结构类型和相关信息。现在各种学术数据都很容易获取,这让我们更容易分析和研究学术社交网络。本研究调查了学术社交网络的背景、现状和趋势。我们首先

  • matlab 医学图像处理(matlab进行图像处理)

    对图像文件增加椒盐噪声,然后进行中值滤波Y=imread(‘D:\321.jpg’);%读入图像I=rgb2gray(Y);%转换成灰度图J=imnoise(I,‘salt&pepper’,0.02);%给图像添加椒盐噪声K=medfilt2(J);%对增加噪声后的图像进行中值滤波subplot(2,2,1);imshow(I);title(‘原图’);%显示图像,并…

  • docker容器端口映射到服务器_阿里云外网端口映射

    docker容器端口映射到服务器_阿里云外网端口映射本篇文章通过具体案例讲解了Docker容器服务访问的两大基本操作,包括基础的容器端口映射机制和容器互联机制。同时,Docker目前可以成熟地支持Linux系统自带的网络服务和功能,这既可以利用现有成熟的技术提供稳定支持,又可以实现快速的高性能转发。………

    2022年10月10日
  • Android–SQLite数据库实现增删改查

    Android–SQLite数据库实现增删改查SQLite–轻量级数据库一般常见于安卓客户端。用于存储一些重要数据,因其操作容易、使用简单的好处博得一大批迷妹。今天就来说一说sqlite一些简单的使用方法。一步一步开始做吧,我先创建个项目,主要是使用sqlite的代码。首先,我需要在项目初次运行时创建数据库并新建一张user表,用来存储username和password两个字段;…

  • 关于pdb文件

    关于pdb文件关于pdb文件当程序在VS上编译时,程序所依赖的所有动态链接库(dll文件)也会被编译,编译过程中每个dll都会产生一个pdb文件,又称为“符号文件”,是一个存储数据的信息文件,其包含dll库在编译过程的某些调试信息,例如程序中所用到的全局变量、局部变量、函数名以及他们的入口地址等。当使用VS调试程序时,会默认加载你的程序以及程序依赖的dll库产生的所有pdb文件,但是结…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号