北航课件-现代工程数学第1、2、3讲(39页).ppt

减法原理 设 A 是有限集合 U 的子集， A 的补集 则 A 的元素个数 | A| 由以下公式给出： 除法原理 如果有限集 S 被分成包含同样多个元素的 k 部分，那么部分的数目 k 由以下公式给出： 相等原理 如果在集合 A 和 B 之间存在一一对应， 则 | A | = | B | 。 例 n 元集 S = {1, …, n} 的子集个数等于由 0 和 1 组成的长度为 n 的串的个数。 证明 可在 S 的子集的集合与由 0 和 1 组成的长度为 n 的串的集合之间建立一一对应如下：让 S 的每个子集 A 对应串 a1…an ，其中对于每个 i?S ， 例 确定 10! 的正整数因子数 10! = 2 ? 3 ? … ? 10 = 28 ? 34 ? 52 ? 7 m | 10! iff m = 2i ? 3j ? 5k ? 7l , 其中 0 ? i ? 8, 0 ? j ? 4, 0 ? k ? 2, 0 ? l ? 1 10! 的正整数因子数 = |{(i, j, k, l): 0 ? i ? 8, 0 ? j ? 4, 0 ? k ? 2, 0 ? l ? 1}| = 9 ? 5 ? 3 ? 2 = 270 恰有一位数字是 5 的 10,000 的正整数有多少个？ 解法1 其中有一个一位数：5。 在二位数中，若十位为 5，则个位有 9 种取法；若个位为 5，则十位有 8 种取法（不能取 0）。 共有 9 + 8 = 17 个二位数。 在三位数中，若百位为 5，则十位和个位各有 9 种取法；若十（个）位为 5，则百位有 8 种取法（不能取 0） ，个（十）位有 9 种取法。共有 9 ? 9 + 2 ? 8 ? 9 = 225 个三位数。 在四位数中，若千位为 5，则百位、十位、个位各有 9 种取法；若百（十、个）位为 5，则千位有 8 种取法（不能取 0），其余各位各有 9 种取法。共有 9 ? 9 ? 9 + 3 ? 8 ? 9 ? 9 = 2,673 个四位数。 总共有 1 + 17 + 225 + 2,673 = 2,916 个数。 解法2 将每个数都看作四位数，例如，将 1 看作 0001，某位数字是 5，其余位有 9 种选择，数字 5可以在个、十、百、千位，所以，满足条件的数总共有 4 ? 9 ? 9 ? 9 = 2,916 个。 3.2 集合的排列 集合 S 的 r-排列是长度为 r 的 S 中不同元素的序列。包含集合 S 的每个元素的排列称为S 的全排列。 如 {a, b, c}的 2-排列有 6 个：ab, ba, ac, ca, bc, cb。 n 元集的 r-排列的数目记为 P(n, r)。 若 r n，则 P(n, r) = 0。 P(n, 0) = 1（空序列）， P(n, 1) = n。 排列数的计算公式 定理3.2.1 若 r ? n，则 证明 第 1 个元素有 n 种选择，第 2 个元素有n ? 1 种选择，…。 n 元集的全排列数为 n!。 各位非 0、互异、数字 5 和 6 不相邻的 7 位数有多少个？ 解法1 不出现 5 和 6 的满足条件的 7 位数是集合 A ={1, 2, 3, 4, 7, 8, 9} 的全排列，有 P(7, 7) 个。 以下用□代表不是 5 和 6 的数字，用〇代表数字 5 或 6。 考虑只出现 5，不出现 6 的数。从 A 中取出 6 个数字排好，再在 7 个位置之一插入 5，有 7 ? P(7, 6) 个。 〇 □ 〇 □ 〇 □ 〇 □ 〇 □ 〇 □ 〇 出现 6 不出现 5 的数也有 7 ? P(7, 6) 个。 考虑 5 和 6 都出现的情况。 第 1 位是 5。将不是 6 的 5 位排好，将 6 插入 5 个位置之一，有 5 ? P(7, 5) 个。 5 □ 〇 □ 〇 □ 〇 □ 〇 □ 〇 最后位是 5，有 5 ? P(7, 5) 个。 5 在中间位置。将不是 5 和 6 的 5 位排好， 将 5 插入 4 个位置之一，将 6 插入 5 个位置之一，有 4 ? 5 ? P(7, 5) 个。 〇 □ 5 □ 〇 □ 〇 □ 〇 □ 〇 〇 □ 〇 □ 〇 □ 〇 □ 〇 □ 〇 各位不是0、互异、数字 5 和 6 不相邻的 7 位数有 36 ? 7 ! ? 6 ? 7 ! = 30 ? 7 ! 个。 解法 2 循环排列 普通排列更恰当些应叫做线性排列。把 r 个元素排成一个圆称为循环 r-排列，或 r-圆排列。每个循环 r-排列对应 r 个不同的线性 r-排列。例如，左边的循环 4-排列对应 4 个线性 4-排列：1234，2341，3412，4123 1 2 3