离散数学是计算机专业基础课程之一。本课程重点讲解离散对象的计数问题、图论问题、网络流问题等计算机科学中的重要基本知识。本课程将为后续如数据结构、算法设计、复杂性理论提供必要的基础，课程内容在人工智能、机器学习、网络设计与分析等前沿领域有重要应用。课程重点培养学生逻辑思维能力及解决问题的能力。
组合计数导引：（单射）函数计数
Loading...
Do curso por Shanghai Jiao Tong University
离散数学
14 ratings
Conheça os instrutores
Long Huan 龙环助理研究员
计算机系
[音乐]
[音乐] [音乐]
各位大家好，本次
讲解组合计数导引，我们讲解单射函数以及一般函数的计数 首先我们考虑第一个问题。
我们现在用 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 这么多种可能。
由此我们就证明了第二个定理 也就是不允许重复的排列，或者是
叫做单射函数的计数问题。
总结一下本 次课我们主要讲了两个，第一个是
函数的计数问题，第二个是单射函数的计数问题，谢谢大家
[音乐]
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
