首页 > 其他分享 >组合

组合

时间:2023-07-01 18:01:10浏览次数:30  
标签:证明 frac 组合 sum times binom aligned

组合数

默认会组合数基础内容,二项式定理

广义组合数定义

\[\binom n m = \frac {n^{\underline m}} {m!} \]

\[n^{\underline m} = n \times(n - 1) \times (n - 2)\times...\times(n-m+1) \]

组合数常用公式及证明

这里的证明主要分为 3 种

1.用组合意义证明

2.用定义证明(拆成阶乘形式)

3.用前面的公式推导

不带求和

1.吸收公式(Absorption Identity):

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

定义证明:

\[\binom n k = \frac {n!}{(k-n)!\times k!} \]

\[\frac n k \binom {n - 1}{k - 1} = \frac n k \frac {(n - 1)!}{(n-k)!\times(k-1)!} = \frac {n!}{(k-n)!\times k!} \]

推广:

\[k\binom n k = n \binom {n-1}{k-1},(n - k)\binom n k = n \binom{n-1} k \]

均可用定义证明,不再赘述。

2.上指标反转(Negating the Upper Index):

\[\binom n k = (-1)^k \binom {k - n - 1}{k} \]

定义证明:

(这里运用组合数广义定义)

\[\binom {k - n - 1} k = \frac {(k - n - 1) ^ {\underline k}} {k!}\\ \begin{aligned} (k - n - 1) ^ {\underline k} &= (k - n - 1)\times(k - n - 2)\times...\times(-n)\\ &=(-1)^k \times n \times (n +(k - 1) - k) \times ...\times (n + 1 - k)\\ &=(-1)^k n ^{\underline k} \end{aligned} \]

把这个带入就可以了。

3.三项式系数恒等式:

\[\binom nm\binom mk = \binom nk \binom {n-k}{m-k} \]

组合意义证明:

从 \(n\) 个小球中选 \(m\) 个染成红色,再从 \(m\) 个红色小球中选 \(k\) 个染成蓝色。

从 \(n\) 个小球中选 \(k\) 个染成蓝色,再从 \(n - k\) 个无色小球中选 \(m - k\) 个染成红色。

两种方法得到的最终结果等价。

定义证明:

\[\binom nm\binom mk = \frac {n!}{m!\times(n-m)!} \times \frac{m!}{k!\times(m-k)!} = \frac {n!} {k!\times(n-m)!\times(m-k)!} \]

\[\binom nk\binom {n-k}{m-k} = \frac {n!}{k!\times(n-k)!} \times \frac{(n-k)!}{(n-m)!\times(m-k)!} = \frac {n!} {k!\times(n-m)!\times(m-k)!} \]

4.帕斯卡公式

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

组合意义证明

从 \(n\) 个小球中选 \(k\) 个,一定是最后一个小球不选然后从 \(n - 1\) 个里面选 \(k\) 个和最后一个小球要选然后从 \(n - 1\) 个里面选 \(k - 1\) 个的方案数加起来。

定义证明

\[\begin{aligned} \binom nk &= \binom {n - 1}{k - 1} + \binom {n - 1}{k}\\ \frac {n!} {k!\times(n-k)!} &= \frac {(n-1)!}{(n-k)!\times(k-1)!} + \frac {(n-1)!}{(n-k - 1)!\times(k)!}\\ \frac {n!} {k!\times(n-k)!} &= \frac {(n-1)!\times(k)!\times(n-1-k)! + (n-k)!\times(n-1)!\times(k-1)!} {(n-k)!\times(k-1)!\times k!\times(n-1-k)!}\\ {n!}&= \frac {(n-1)!\times[(k)!\times(n-1-k)! + (n-k)!\times(k-1)!]} {(k-1)!\times(n-1-k)!}\\ n &= \frac{k! \times (n-1-k)!} {(k-1)!\times(n-1-k)!} + \frac{(n-k)! \times (k-1)!} {(k-1)!\times(n-1-k)!}\\ n &= k + n - k\\ n &= n \end{aligned} \]

求和

接下来才是真正有用的东西

1.上指标求和(Summation on the Upper Index):

公式1

\[\sum_{k = 0}^n \binom km = \binom{n + 1} {m + 1}\\ \]

组合证明

有 \(m + 1\) 个球,选 \(n + 1\) 个,枚举最后一个选的位置在 \(k + 1\) 则前 \(k\) 个要选 \(n\) 个。

推导证明

根据4.帕斯卡公式

\[\begin{aligned} \binom {n + 1}{m + 1} &= \binom{n}{m}+\binom{n}{m + 1}\\ &=\binom{n}{m}+\binom{n-1}{m} + \binom{n-1}{m+1}\\ &=\binom{n}{m}+\binom{n-1}{m} + \binom{n-2}{m} + \binom{n-2}{m+1}\\ &=......\\ &=\sum_{k = 0}^n \binom km \end{aligned} \]

公式2

\[\sum_{k = 0}^m \binom {n+k}k = \binom {n + m + 1} m \]

推导证明

\[\begin{aligned} \sum_{k = 0}^m \binom {n+k}k &= \sum_{k = 0}^m \binom {n+k}n =\sum_{k = n}^{n + m} \binom kn\\ &=\sum_{k = 0}^{n + m} \binom kn - \sum_{k = 0}^{n-1} \binom kn\\ &=\binom {m + n + 1}{n + 1} - \binom{n}{n + 1}\\ &=\binom {m + n + 1}m \end{aligned} \]

第 3 行运用了上指标求和的公式1 ,\(\binom n {n + 1} = 0\)

2.范德蒙德卷积

\[\sum_{k = 0}^{k<=n}\binom r k\binom s {n - k} = \binom {r + s}{n} \]

组合证明

有 \(r + s\) 个小球选 \(n\) 个小球,枚举在前 \(r\) 个中选 \(k\) 个,在后 \(s\) 个中选 \(n-k\) 个。

推导证明

\[\begin{aligned} \sum_{k=0}^{n+m}\binom{n+m}kx^k&= (x + 1)^{n + m}\\ &=(x + 1)^n(x + 1)^m\\ &=\sum_{r=0}^n \binom nr x^r + \sum_{r=0}^m \binom ms x^s\\ &=\sum_{k=0}^{n+m}\sum_{r=0}^k\binom{n}{k}\binom{m}{k-r}x^k \end{aligned} \\ \Rightarrow \binom{n+m}k = \sum_{r=0}^k\binom{n}{k}\binom{m}{k-r} \]

3.交错和

标签:证明,frac,组合,sum,times,binom,aligned
From: https://www.cnblogs.com/hfjh/p/17519646.html

相关文章

  • 代码随想录算法训练营第二十一天| 216.组合总和III 17.电话号码的字母组合
    216.组合总和III  思路:很像上一个组合类型的题目,唯一不同的就是自己写一个sum代码:1voidconvertBST_cur(TreeNode*root,vector<TreeNode*>&nodes)2{3if(!root)return;4if(root->left)convertBST_cur(root->left,nodes);5nodes.push_bac......
  • Arrangement排列•Combination组合•Counting计数•Binomial Theorem二项式定理
    符号C-Combination组合数[1]A-Arrangement(旧教材为P-Permutation)N-Number元素的总个数(自然数集合).M-参与选择的元素个数(M不大于N,两者都是自然数集合).!-Factorial阶乘.Arrangement排列与Combination组合:注意:n,m都是自然数,且m<=n,下同.排列的定义:从n......
  • 企业架构师权威认证—TOGAF® 认证组合中文考试正式上线!
    @所有架构从业人员TOGAF®认证组合中文版考试正式上线啦!  TheOpenGroup亚太区负责人高美华女士进行发布 千呼万唤始出来—TOGAF®认证组合中文版考试正式上线!一直翘首以待中文版考试的朋友们可以开始报名预约啦! 2023年6月29日,在TheOpenGroup主办的「架构·可持续未来峰会......
  • 深入浅出设计模式 - 组合模式
    博主介绍:✌博主从事应用安全和大数据领域,有8年研发经验,5年面试官经验,Java技术专家✌Java知识图谱点击链接:体系化学习Java(Java面试专题)......
  • AI 和 DevOps:实现高效软件交付的完美组合
    AI时代,DevOps与AI共价结合。AI由业务需求驱动,提高软件质量,而DevOps则从整体提升系统功能。DevOps团队可以使用AI来进行测试、开发、监控、增强和系统发布。AI能够有效地增强DevOps驱动流程,从开发人员的业务实用性和支持的角度来看,评估AI在DevOps中的重要性是十分......
  • 面向对象(三大特征、继承下的查找、super、组合)
    面向对象有三大特征:封装、继承和多态继承继承其实和封装差不多,就是新建的类称为是子类或派生类,多个子类继承同一个类,这个类教父类或基类1.为什么要继承类解决什么问题:解决的是对象与对象之间代码冗余问题继承解决什么问题:解决的是类与类之间的代码冗余问题2.怎样继......
  • 动态规划-背包问题-完全背包问题:leetcode 377. 组合总和 Ⅳ
    1.题目读题给你一个由不同整数组成的数组nums,和一个目标整数target。请你从nums中找出并返回总和为target的元素组合的个数。题目数据保证答案符合32位整数范围。 示例1:输入:nums=[1,2,3],target=4输出:7解释:所有可能的组合为:(1,1,1,1)(1,1,2)(1,2,......
  • Coloring Tree (牛客多校) (BFS序列妙用+ f(n)-f(n+1)+ 组合数学)
    题目大意:给一个树,然后有k种颜色可以给树上色权值是2个相同颜色节点的最短距离问让权值为D的方案数 题解:首先要让2个节点为D,怎么处理呢?利用f(D)-f(D+1)即可因为问的是2个相同颜色点的最短距离,因此直接bfs用一个bfs序列然后在bfs一下,因为之前co......
  • 如何明辨组合、聚合、继承
    提问如何明辨组合、聚合、继承回答组合:功能组合;功能作为类的属性,必须依附类存在;继承:血脉继承;在严格的血脉关系,变化少的场景下使用;聚合:一个独立个体,是另一个独立个体的属性,......
  • 单继承、多继承下的属性查找、super关键字、多态与多态性、组合
    单继承下的属性查找单继承:一个类只能继承一个类。classC():passclassB(C):passclassA(B):#单继承pass单继承下的属性查找顺序:先从对象本身的名称空间中查找------>产生这个对象的类中去查找 ------>继承的父类中去查找#查找属性classFoo():......