组合数的各种性质和定理

组合数的各种性质和定理从m个物品里选出n个的方案数,记作CnmCmnC_m^n,即为组合数组合数有很多很多的性质和定理。。。注意由于本人沉迷玩梗无法自拔,如果看见您看不懂的梗请随意跳过。组合数通项公式Cnm=m!n!∗(m−n)!Cmn=m!n!∗(m−n)!C_m^n=\frac{m!}{n!*(m-n)!}证明:现在我们从m个不同的数里选出n个数组成一个排列,第一个位子上的数有m种取法,第二…

大家好,又见面了,我是你们的朋友全栈君。

从m个物品里选出n个的方案数,记作 Cnm C m n ,即为组合数
组合数有很多很多的性质和定理。。。
注意由于本人沉迷玩梗无法自拔,如果看见您看不懂的梗请随意跳过。

组合数通项公式

Cnm=m!n!(mn)! C m n = m ! n ! ∗ ( m − n ) !




证明:现在我们从m个不同的数里选出n个数组成一个排列,第一个位子上的数有m种取法,第二个位子上的有m-1种,第三个位子上有m-2种。。。共有

m!(mn)! m ! ( m − n ) !


然而,我们对于顺序没有要求,假设取出了n个数,第一个位子上有n种放法,第二个位子上有n-1种。。。所以我们刚才得到的哪个东西还要除一个

n! n !

组合数递推公式

Cnm=Cnm1+Cn1m1 C m n = C m − 1 n + C m − 1 n − 1




证明:从m个不同的数中取n个,第m个数如果取的话有

Cn1m1 C m − 1 n − 1
种取法,如果不取则有

Cnm1 C m − 1 n
种。

如果您是组合数新手,请牢记以上两个公式

性质1

Cnm=Cmnm C m n = C m m − n




证明:显然从m个物品里选n个和从m个物品里选m-n个丢掉的方案数是一样的。

性质2

Crm+r+1=i=0rCim+i C m + r + 1 r = ∑ i = 0 r C m + i i




证明:用组合数的递推公式。

首先

C0m=C0m+1=1 C m 0 = C m + 1 0 = 1




C0m+C1m+1+C2m+2+...+Crm+r C m 0 + C m + 1 1 + C m + 2 2 + . . . + C m + r r
=



C1m+C1m+1+C2m+2+...+Crm+r C m 1 + C m + 1 1 + C m + 2 2 + . . . + C m + r r
=



C1m+2+C2m+2+...+Crm+r C m + 2 1 + C m + 2 2 + . . . + C m + r r
=



Crm+r+1 C m + r + 1 r

性质3

CnmCrn=CrmCnrmr C m n ∗ C n r = C m r ∗ C m − r n − r




证明:用组合数的通项公式



CnmCrn= C m n ∗ C n r =




m!n!(mn)!n!r!(nr)!= m ! n ! ( m − n ) ! ∗ n ! r ! ( n − r ) ! =




m!r!(mr)!(mr)!(mn)!(nr)!= m ! r ! ( m − r ) ! ∗ ( m − r ) ! ( m − n ) ! ( n − r ) ! =




CrmCnrmr C m r ∗ C m − r n − r

性质4(二项式定理)

i=0mCim=2m ∑ i = 0 m C m i = 2 m




证明:显然

Cim C m i
代表一个m位二进制数有i个0的情况下的数量,那么这个和就是m位二进制数的数量了。

推广一下这个二项式定理:


i=0mCimxi=(x+1)m ∑ i = 0 m C m i ∗ x i = ( x + 1 ) m



这个又怎么证明呢?先把

(x+1)m ( x + 1 ) m
写成

(x+1)(x+1)(x+1)... ( x + 1 ) ( x + 1 ) ( x + 1 ) . . .
的格式,然后每一项很精妙啊,比如说i次方项,选的

i i



x


x


是从哪个括号里来呢?有

Cim C m i
种方案吧,所以

xi x i
项的系数是

Cim C m i


这就是杨辉三角的应用(可以自行百度)

性质5

C0mC1m+C2m...±Cmm=0 C m 0 − C m 1 + C m 2 − . . . ± C m m = 0




证明:假如m是奇数的花,由性质1可知正确。

假如m是偶数的花,这个里面的花,用一下递推公式,然后显然

C0m1=C0m=1 C m − 1 0 = C m 0 = 1
并且

Cm1m1=Cmm=1 C m − 1 m − 1 = C m m = 1
,则:



C0mC1m+C2m...+Cmm= C m 0 − C m 1 + C m 2 − . . . + C m m =




C0m1C0m1C1m1+C1m1+C2m1...+Cm1m1=0 C m − 1 0 − C m − 1 0 − C m − 1 1 + C m − 1 1 + C m − 1 2 − . . . + C m − 1 m − 1 = 0

性质6

C0m+C2m+C4m...=C1m+C3m+C5m+...=2m1 C m 0 + C m 2 + C m 4 . . . = C m 1 + C m 3 + C m 5 + . . . = 2 m − 1




证明:这个根据性质4和性质5可知正确。

性质7

Crm+n=C0mCrn+C1mCr1n++CrmC0n C m + n r = C m 0 ∗ C n r + C m 1 ∗ C n r − 1 + … + C m r ∗ C n 0




证明:很简单,考虑我选出的r个物品在前m个物品有几个,在后n个物品里有几个即可。

特别的:

Cnm+n=C0mC0n+C1mC1n++CmmCmn C m + n n = C m 0 ∗ C n 0 + C m 1 ∗ C n 1 + … + C m m ∗ C n m



这个是根据性质1变形得到的。

性质8

nCnm=mCn1m1 n ∗ C m n = m ∗ C m − 1 n − 1




证明:运用通项公式



nCnm= n ∗ C m n =




nm!n!(mn)!= n ∗ m ! n ! ( m − n ) ! =




m!(n1)!(mn)!= m ! ( n − 1 ) ! ( m − n ) ! =




m(m1)!(n1)!(mn)!=mCn1m1 m ∗ ( m − 1 ) ! ( n − 1 ) ! ( m − n ) ! = m ∗ C m − 1 n − 1

性质9

i=1nCini=n2n1 ∑ i = 1 n C n i ∗ i = n ∗ 2 n − 1




证明:用通项公式



ni=1Cini=n2n1= ∑ i = 1 n C n i ∗ i = n ∗ 2 n − 1 =




ni=1n!(i1)!(ni)!= ∑ i = 1 n n ! ( i − 1 ) ! ( n − i ) ! =




(ni=1(n1)!(i1)!(ni)!)n= ( ∑ i = 1 n ( n − 1 ) ! ( i − 1 ) ! ( n − i ) ! ) ∗ n =




(n1i=0Cin)n= ( ∑ i = 0 n − 1 C n i ) ∗ n =


现在看性质4。



n2n1 n ∗ 2 n − 1

性质10

i=1nCini2=n(n+1)2n2 ∑ i = 1 n C n i ∗ i 2 = n ∗ ( n + 1 ) ∗ 2 n − 2




证明

和上一个性质有些类似。



ni=1Cini2= ∑ i = 1 n C n i ∗ i 2 =


用和上面差不多的方法得到:



(n1i=0Cin1(i+1))n= ( ∑ i = 0 n − 1 C n − 1 i ∗ ( i + 1 ) ) ∗ n =




(n1i=0Cin1i+n1i=0Cin1)n= ( ∑ i = 0 n − 1 C n − 1 i ∗ i + ∑ i = 0 n − 1 C n − 1 i ) ∗ n =


用性质9和性质4可以得到:



(2n2(n1)+2n1)n= ( 2 n − 2 ∗ ( n − 1 ) + 2 n − 1 ) ∗ n =


很明显

2n1=22n2 2 n − 1 = 2 ∗ 2 n − 2


所以原式=

2n2(n+1)n 2 n − 2 ∗ ( n + 1 ) ∗ n

性质11

i=0n(Cin)2=Cn2n ∑ i = 0 n ( C n i ) 2 = C 2 n n




证明:boshi说,他的门前有两棵树,
一棵是枣树,另一棵也是枣树,每棵树上有n个枣子,每个枣子都有一个不同的神奇的膜法符号。现在boshi从两棵树上一共打下了n个枣子,那么一共有多少种方案?是

Cn2n C 2 n n
,也是第一棵树上打下i个枣子,从第二棵树上打下(n-i)棵枣子的方案,根据乘法原理乘起来,又因为

Cin=Cnin C n i = C n n − i
,所以得到上一个式子。

卢卡斯定理

简单的说就是求 Cnm%p C m n % p 的时候可以化作 Cnm=Cn/pm/pCn%pm%p C m n = C m / p n / p ∗ C m % p n % p ,那么只要递归 Cn/pm/p C m / p n / p 即可。
证明我蠢我不会自己想

后记

啊啊啊搞了一下午终于证完了累死了。。。感觉自己和组合数的感情有了明显的提升(才怪)。。。
在文章的最后%一发数王。。。
%%%%%%%%%数王您太强了%%%%%%%%%%%
数王说以上所有定理都可以用那个那个那个证,虽然我不知道那个是哪个,但是反正好强啊%%%%%%%%
好吧以上都是不正经内容,正经内容是:
在做题的时候大家可能不一定都会遇到这些性质,但是在手动证明完这些性质后对于组合数变形的问题就会有更深一层的理解,总之,组合数性质可以用一下方法推出:
1.情景假设法(假设boshi从枣树选枣子的方案。。。
2.隔板法(boshi把枣子放成一排,通过在枣子间添加隔板来分组。。。
3.通向公式法
4.递推公式法
以上。

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

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

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

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

(0)


相关推荐

  • 前端对接口是什么意思_接口返回json格式

    前端对接口是什么意思_接口返回json格式什么是JSON?

    2022年10月12日
  • CloudSim资源调度「建议收藏」

    CloudSim资源调度「建议收藏」    本菜鸡的毕业设计选择的就是面向数据中心能耗优化的粒子群算法的设计与实现,别问我为啥选这个,我也不知道,在网上查询了很多之后发现也就GitHub上面就4个项目,好像也就第四能用。然后就是YouTube上面有一个印度小哥的视频,做了一个高大上的界面,用的InternetTopologyZoo做了一个界面,非常酷眩,然而没有源代码,全程是成果展示,心痛的要死。但是仅仅是云任务调度,而这…

    2022年10月13日
  • pycharm不会自动补全括号_pycharm代码提示

    pycharm不会自动补全括号_pycharm代码提示安装pycharm后,输入代码后,没有补全提示首先检查是否关闭了代码提示,如下图,将红框中“PowerSaveMode”前的勾去掉第二步,如果在输入某些代码时还是没有补全提醒,可能是配置好python环境则点击file->settings->projectInterpreter,如下图选择安装的python输入代码就会有提示了…

  • spring整合log4j_spring连接数据库的配置

    spring整合log4j_spring连接数据库的配置常用日志框架log4j、log4j2(log4j的升级版,最常用的)、logback(spring boot默认)、Jboss-logging…等slf4 是日志接口规范,代码对接slf4,实现和具体日志框架解耦,无需修改编码即可切换日志框架。修改pom依赖<dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-st

  • cmd进入目录后怎样运行exe_命令提示符怎样进入文件所在目录

    cmd进入目录后怎样运行exe_命令提示符怎样进入文件所在目录如何用Windows命令提示符(cmd.exe)进入指定目录如何用Windows命令提示符(cmd.exe)进入指定目录提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章目录如何用Windows命令提示符(cmd.exe)进入指定目录前言一、Windows命令提示符是什么?二、使用步骤1.打开命令提示符总结新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPa

    2022年10月15日
  • Vue2.0的三种常用传值方式、父传子、子传父、非父子组件传值

    Vue2.0的三种常用传值方式、父传子、子传父、非父子组件传值Vue2.0传值方式:在Vue的框架开发的项目过程中,经常会用到组件来管理不同的功能,有一些公共的组件会被提取出来。这时必然会产生一些疑问和需求?比如一个组件调用另一个组件作为自己的子组件,那么我们如何进行给子组件进行传值呢?如果是电商网站系统的开发,还会涉及到购物车的选项,这时候就会涉及到非父子组件传值的情况。当然你也可以用Vuex状态管理工具来实现,这部分我们后续会单独介绍。先给大家介绍Vue常见的三种传值方式

发表回复

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

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