概率论基础学习笔记(一):组合分析

第一章:组合分析

作为概率论的基础, 本章具有非常重要的作用, 但是本章中的大部分内容我们在高中时期都已经接触过, 这里仅仅只是快速罗列一些基础的定义和定理, 只对其中某些比较重要或者有意思的稍微探讨一下

定义 关于计数的数学理论通常称为组合分析(combinatorial analysis)

计数基本法则 假设有两个试验, 其中试验种可能的结果, 对应于试验的每一个结果, 试验种可能的结果, 则这两个试验一共有种可能的结果.

定理1.1 随意排列个不同的元素, 一共有


种不同的排列方式

推论1.2 对于个元素, 如果其中个元素彼此相同, 另个元素彼此相同, , 个也彼此相同, 那么一共有


种不同的排列方式

定理1.3个元素中取出个组成一组, 一共有


个不同的组

记号与术语 对于, 我们定义如下:


这样就表示从个元素种一次取出个可能的组合数.

PS: 按照惯例, 定义, 因此. 当或者时, 我们也认为.

工具 下面的这个组合恒等式在很多地方非常有用处

上面的恒等式可以利用利用定义很轻松的证明. 不过这个恒等式从组合的角度来看还是有一定意义的. 一方面, 从个元素种取个元素有种方法. 另一方面如果考虑这个元素种有一个元素, 则从中取出个有两种情况, 一种是含有这个元素, 共有种取法(从剩下的个元素中取个, 另一种情况是不含有这个元素,共有种取法(从剩下的个元素中取个).从而上面的等式成立.

二项式定理

二项式可以利用数学归纳法经过一定量的计算证明, 不过这里要说一下从组合的角度去证明这个定理的方法

考虑乘积


它展开后一共将包含个求和项, 其中每一项都是个因子的乘积, 而且其每一项都包含因子, .但是不可能两个都同时包含. 而至于到底有多少项包含, 相当于从个元素种取出个元素构成一组的取法(一旦取出了则剩下的一定是)的数目, 因此一共有个这样的项. 如果令, 可以看出

工具 二项式定理给了我们一个很有意思的结论, 如果令, 则有


推论1.4个不同的元素分成组, 每组分别有个元素, 其中 一共有


种分法.

PS: 得到这个结论可以有两种思路, 分别如下:

第一种 对于个元素, 第一组元素共有种选取方法, 选定第一组后, 第二组共有种方法, 依次类推, 第组有种方法, 从而根据推广的计数基本法则, 将个元素分成组可能存在


种分法.

第二种 如果我们把第一组中的个元素中的每一个都记为, 第二组的个元素中的每一个都记为, 以此类推, 第组的个元素中的每一个都记为, 则现在一共有个数字, 则这个数字对应的每一种排列实际上都对应了一种分法(例如对于中的一个排列相当于对应这把分到第一组, 分到第二组, 分到第三组), 则问题转化为对于个元素其中个彼此相同, 个彼此相同, , 个彼此相同共有多少种排列方式, 也就是前面推论1.2的内容, 也就是


记号 如果, 则定义


因此表示把个不同的元素分成大小分别为个不同的组合的组合数.

多项式定理


上式中的求和符号是对满足的所有非负整数向量求和.

PS:

也叫多项式系数(multinomial coefficient).

另外这个定理可以采取前面对二项式定理证明中累的方式来证明, 这里就不多说了.

方程整数解的个数

经过上面关于排列和组合的讨论后我们来讨论一下方程整数解的个数的问题, 作为一个简单的对前面的理论的应用.

考虑一个方程


那么有多少个非负整数向量满足上面的方程?

为了解决这个问题, 我们来考虑排成一行, 那么他们一共有个间隔, 则从这个间隔中选出个间隔, 那么每一种选法实际上都对应了这个方程的一种正整数解的情况. 例如若, 用表示选区的间隔, 其中一种选取方法如下


这种选取方法实际上是对应了这组解. 那么前面提到的方程的正整数解的个数实际上就相当于从个间隔里选区个的选取方法. 于是我们的到如下命题:

命题 共有个不同的正整数向量满足


而注意到对于上式中如果我们令我们可以得到


则上面的方程有个解. 而对于每一个解, 其正好对应于方程


的解, 也就是说的非负整数解的数目就等前面的正整数解的数目. 从而我们可得如下命题

命题 共有个不同的非负整数向量满足


从而问题解决.

PS: 其实这里的思路就是高中介绍的"插空法"的思路, 如果把插空的过程看作是动态的实际上也可以直接求得答案. 这里就不多说了

评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注