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

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

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

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

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

种不同的排列方式

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

种不同的排列方式

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

个不同的组

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

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

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

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

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

二项式定理

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

考虑乘积

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

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

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

种分法.

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

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

种分法.

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

记号 如果 , 则定义

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

多项式定理

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

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

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

方程整数解的个数

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

考虑一个方程

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

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

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

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

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

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

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

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

从而问题解决.

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