[音乐]
[音乐] [音乐]
各位大家好,本次
讲解组合计数导引,我们讲解单射函数以及一般函数的计数 首先我们考虑第一个问题。
我们现在用 26 个英文 字符组成长度为 5
的字符串,我们想问,这样的字符串一共有多少个? 我们看两个例子。
abcde,以及 sssdd 都是两个长度为 5
的字符串,它都符合我们的要求 我们把问题 1 的要求做一个小的修改,也就是问题
2 我们说如果我们进一步要求,这个长的字符串中的所有
字符都不,彼此互不相同,也就是不能出现重复的字符的话 我们问,这样的字符串又有多少?我们看还是同样这两个
例子,第一个例子,abcde,它符合所有的字符都彼此不同 而第二个例子中,我们说
s 重复出现了三次,d 重复出现了两次 所以它不符合第二个问题的要求。
显而易见地 满足第二个问题要求的字符串少于第一个问题的字符串 我们看一下问题 1 的解。
我们用图中的 L1、 L2、 L3、 L4、 L5 分别表示
5 长的字符串的每一个位置 下面这个圆框中是所有的 26
个可能的英文字符 我们说,L1 首先有多少个可能的选择?
L1 可以取 a,可以取b,它也可以取 c、 d,或者是取 x、 y、
z 中的任何一个,换句话说,L1 有 26 种选择 类似的 L2、 L3、 L4
都有 26 种选择 L5 也有 26 种选择。
总之 我们说,问题 1 的解,其实就是五个 26 相乘,也就是
26 的五次方 那么我们看问题 2 呢,问题 2
现在的要求是所有的字符彼此不相同 我们还是从 L1 开始分析。
L1 可以取 a,可以取 b,可以取 c,可以取 x、 y、 z 中的任何一个。
我们不妨假设它取了 取了 b,但是 L1 的可能我们说是一共是有 26 种可能。
但是一旦当它取好了 b 之后 我们再选 L2 的时候,我们说,它可以从余下的
25 个字符中选,它可以选 a,可以选 c 可以去选 x、 y、
z,但是它的可选的范围只有 25 种 类似的我们可以分析
L3 的可选范围 L3,我们刚才假设,L2 假设它
选了是 z,那么 L3 现在只能选 除开 b 和 z 的其他的
24 个字符 所以 L3 有四个,24
个选择 类似的,L4、 L5 我们都能够得出它们有多少个可能的选择
总计呢我们说,关于第二个问题,一共有 26×
25×24×23×22 个个位不同的这样的 5 长的字符串。
我们把问题 1 做一个推广,问题 1 从直观上来讲,我们就是要找一个定长的序列,一个有限长的序列
对每一位的选择呢,没有什么额外的要求,它可以是重复的
这个问题抽象到数学中,它表现为一个集合,大写的 N 的大小为小 n
集合大 M 的大小为小 m,并且我们知道 n 大于等于 0,小 m
也大于等于 1 我们问,从集合大 N 到集合大 M 所有可能的函数的个数?
而我们这里的命题 1 告诉我们,这个问题一共有 mⁿ 个可能的选择
下面我们想证明这个命题 这里用到一个非常常用的证明方法,是数学归纳法
我们对什么做归纳,我们对原始的定义域,也就是大 N
的大小做归纳 首先,我们说,当小 n 为 0
的时候 这个时候我们说,既然定义域为空的话,那么
f 函数 满足这样一个要求的小 f 函数只有一个,就是空函数。
那么小 f 是唯一的 这个时候 mⁿ 正好为 1,也就是说命题成立
接着我们假设当小 n=k 的时候,结论成立 那么我们接下来需要验证的是,当小
n 比原来,比 k 的时候 定义域中多入了一个值,它的结论仍然成立
我们这个时候怎么样证明呢? 我们取 k+1
大的这个定义域中的一个特殊的一个符号 或者是特殊的一个元素小 a,我们把 小
f 函数理解成如下两部分的组合 首先我们说,因为
f 是一个函数,所以说它对定义域 中的每一个值都有一个赋值,那么我们现在把小
a 选出来 我们首先选好小 f(a) 的定义域
那么小 f(a) 的选择有多少种可能? 很显然,在这种情况下,小
f(a) 一共是有 M 种可能 下面的图中,我们用一个点,从 a 点指向了它所对应的函数下的值
那么我们接着考虑,这个函数,它除开定义域除开小 a 的部分,也就是
大 N 减掉小 a 这个元素这一部分,我们考虑余下的这部分函数
那么它的值域,又是怎么样一个选择呢? 我们说,现在小
f' 这一部分,它的值域仍然是整个大 M 集合 那么但是现在小
f' 有什么好的性质?小 f' 的规模只有 k-1
也就是说我们这个时候可以使用归纳假设,f' 一共有 m 的 n-1
次方种可能 我们说小 f 函数是 a 和 f' 这两部分组成
所以说,小 f 函数一共有 m 再乘以 m 的 n-1 等于 mⁿ
种可能 那么刚才我们就证明了从一个 n
大的定义域,到一个 m 大的一个值域的话,那么所有可能的函数一共是
mⁿ 种 那么我们考虑第二个问题,第二个问题的本质是说,我们取一个定长的串
但是我们现在要求串中的每一个元素都互不相同,那么有多少种可能?
这个问题我们同样把它抽象为一个 函数问题。
我们问的是一个,一个大小为小 n 的集合大 N,到一个大小为小
m 的集合大 M 它们可能的单射函数,也就是不同的输入我们必须要有不同的输出
单射函数有多少种可能?命题 2 告诉我们,这样的
单射函数一共有 m 乘以 m-1,一直乘到 m-n+1
种 而证明的方法跟刚才是类似的,我们仍然是用数学归纳法
首先当 n=0,也就是基础的情况。
n=0 的时候,我们说 f,小 f 函数只有一种,是空函数 这个时候公式是成立的。
第二个我们是归纳假设步,我们 假设小 n=k,也就是定义域的大小为
k 的时候结论成立 那么我们看,当定义域中增加了一个元素,小 n =k+1
的时候,怎么样做呢? 跟刚才非常类似,我们仍然从定义域中选出一个特殊的元素小
a 我们首先看小 f 函数在 a 上它有多少种可能的取值
跟刚才一样的,f(a) 一共是有小 m
种可能,它可以是整个 大 M 集合中的任何一个地方。
但是与刚才的证明不同的在于 当我们考虑小
f 函数除开 在 a 的输入部分之外的情况的时候,也就是
f' 我们说,f' 现在的值域,它的范围是多少?
注意到因为小 a 已经把 f(a) 这个值给取到了
所以说,我们知道,又由于我们一开始的要求是单射函数,也就是不同的输入必须对应不- 同的输出
所以说,小 f' 部分的值域部分,就只有除开了那个
f(a) 的这一小块 换句话说,这个时候它的值域只有
m-1 这样一个大小 那么我们用归纳假设
我们说,归纳假设现在定义域的大小是 n-1,值域的大小是 m-1,那么
f' 一共是有 m-1 乘以 m-2 一直乘到 m-n+1 种可能
那么最后把小 f 函数在 a 上 的取值,以及在
f' 上的取值综合起来,就是小 f 的所有可能 那么一共是 m 乘以 m-1
乘以 m-2 一直乘到 m-n+1 这么多种可能。
由此我们就证明了第二个定理 也就是不允许重复的排列,或者是
叫做单射函数的计数问题。
总结一下本 次课我们主要讲了两个,第一个是
函数的计数问题,第二个是单射函数的计数问题,谢谢大家
[音乐]