Induction and recursion
大数据科学系/大连东软信息学院
Copyright By PowCoder代写 加微信 powcoder
Section 3.1
计数原则: 乘积法则
乘积法则: 假设一个过程可以被分解成两个任务。 如果完成第一个任务有n1 种方式，在完成第一个任务后，有n2 种方式完成第二个任务，那么完成这个过程有 n1∙n2种方式。
例: 7个学生有多少种排队方式?
例: 如果每个车牌由3个英文字母后跟3个数字的序列构成，那么有多少种不同的有效车牌?
解: 根据乘积法则,
总共有26 ∙ 26 ∙ 26 ∙ 10 ∙ 10 ∙ 10 = 17,576,000 个可能的车牌。
乘积法则——计数函数
从一个m 元集到一个 n 元集存在多少个函数?
解: 对于定义域中m 个元素中的每个元素都要选择陪域中n 个元素中的一个元素对应。由乘积法则，得到：
存在 n ∙ n ∙ ∙ ∙ n = nm 个从m元集到n元集的函数。
存在n(n−1) (n−2)∙∙∙(n−m +1)个一对一函数。
从 1000 到 9999 的 整数 中 :
① 含有5的数有多少个 ;
1> 千位 : 千位数 不能 取 0 和 5 , 只能取值 8 种情况 ;
2> 百位 : 百位数 不能 取 5, 有 9种 取值情况 ;
3> 十位 : 百位数 不能 取 5, 有 9种 取值情况 ;
4> 个位 : 百位数 不能 取 5, 有 9 种 取值情况 ;
根据乘法原则 : 不含5的个数位为 8 × 9 × 9 × 9 = 5832
含有 5 的个数为 : 9000 − 5832 = 3168;
乘积法则——计数函数
100位乒乓球选手通过淘汰赛，最后产生一名冠军，问需要经过多少场比赛？
解：第一轮，分50对比赛，结束后留下50名胜利者
第二轮，分25对比赛，结束留下25名胜利者
第三轮，分12组，其中一人直接参加第四轮比赛。
第四轮，开始时13名选手，分6组比赛，一人直接进入第五轮
第五轮，有7人，分3组，同样有一人直接进入第六轮
第六轮，有4人，分两组，其中胜利者参加最后的决赛。
总比赛数：50+25+12+6+3+2+1 = 99
乘积法则——计数有穷集的子集
如果 A1, A2, … , Am 是有穷集。
在笛卡儿积 A1 ⨉ A2 ⨉ ∙∙∙ ⨉ Am 中任选一个元素的任务是通过在 A1中选一个元素, 在A2中选一个元素, …, 在Am中选一个元素。
由乘积法则, 得到: 笛卡儿积中的元素数
|A1 ⨉ A2 ⨉ ∙∙∙ ⨉ Am |= |A1| ∙ |A2| ∙ ∙∙∙ ∙ |Am|.
长度为n的0，1符号串的数目为2n
假定a=a1a2…an，ai∈[0，1]，i=1，2，…，n，根据乘法法则可得0,1符号串的个数为：
k值为n1n2 · · · nm
计数原则: 求和法则
求和法则: 如果完成第一项任务有n1 种方式，完成第二项任务有n2 种方式，并且这些任务不能同时执行，那么完成第一或第二项任务有n1 + n2 种方式。
计数原则: 求和法则
例: 假定要在某学院选一位教师或学生作为校委会的代表。如果该学院有37名教师和83名学生，那么这个代表有多少种不同的选择？
解: 完成第一项任务，选一名教师可以有37种方式。完成第二项任务，选一名学生有83种方式。
由求和法则，得到 37 + 83 = 120种可能的方式来挑选代表。
求和法则可以用集合表述：
|A ∪ B|= |A| + |B| 只要A 和 B 是不相交的
|A1 ∪ A2 ∪ ∙∙∙ ∪ Am |= |A1| + |A2| + ∙∙∙ + |Am|
当 Ai ∩ Aj = ∅ ，对所有的i, j
k值为n1+n2+ · · · +nm
例: 假定某编程语言的标识符命名规则是，由至多三位构成，首字符是字母，其余部分可以是字母或数字。
26 + 26 ∙ 36 + 26 ∙ 36 ∙ 36= 34658
二个字符 26 ∙ 36
三个字符 26 ∙ 36 ∙ 36
设 A , B , C 是 3 个城市，从 A 到 B 有 3 条路 , 从 B 到 C 有 2 条路 , 从 A 到 C 有 4 条路 。
问 从 A 到 C 有多少种不同的方式 ?
例: 假设密码为6至8位的字符构成，其中每个字符必须是大写字母或数字。每个密码必须至少包含1位数字，有多少种可能的密码？
解 设 P 为统计的密码的数目, P6, P7, 和 P8 是长度为 6, 7, 和 8 的密码的数目
由求和原则 P = P6 + P7 +P8.
我们发现P6, P7 和 P8是由字母和数字组成的指定长度的密码的数目减去只有字母组成的密码的数目:
P6 = 366 − 266 =2,176,782,336 − 308,915,776 =1,867,866,560.
P7 = 367 − 267 = 78,364,164,096 − 8,031,810,176 = 70,332,353,920.
P8 = 368 − 268 = 2,821,109,907,456 − 208,827,064,576 =2,612,282,842,880.
于是, P = P6 + P7 +P8 = 2,684,483,063,360.
计数原则: 容斥原理
减法法则: 如果一个任务或者可以通过n1 种方法执行或者可以通过 n2 种另一类方法执行，那么执行这个任务的方法数是 n1 + n2 减去两类方法中执行这个任务都相同的方法。
减法法则也称为容斥原理:
减法法则——计数问题
例: 有多少种以1 开头或者以00为结尾的8位串?
以 1 开头的8位串数目: 27 = 128
以 00 为结尾的8位串数目: 26 = 64
既以 1 开头又以 00为结尾
的8位串的数目 : 25 = 32
于是，由减法法则得128 + 64 − 32 = 160.
计数原则: 容斥原理
一个离散数学教学班包含25个计算机科学专业的学生、13个数学专业的学生和8个同时主修数学和计算机科学两个专业的学生。如果每个学生或主修数学专业，或者主修计算机科学专业，或者同时主修这两个专业，那么班里有多少个学生？
计数原则: 容斥原理
例：某公司收到350份应聘者简历，其中220主修了计算机专业，147人主修了商务管理专业，有51人既修了计算机也修了商务管理专业，那么有多少人没有修计算机也没有修商务管理专业？
350-316 = 34个申请人既没有主修计算机专业又没有主修商务专业。
计数原则: 容斥原理
计数原则: 容斥原理
计数原则: 容斥原理
1232个学生选了西班牙语课，879个学生选了法语课，114个学生选了俄语课。103个学生选了西班牙语和法语课，23个学生选了西班牙语和俄语课，14个学生选了法语和俄语课。如果2092个学生至少在西班牙语、法语和俄语课中选1门，则有多少学生选了所有这3门课？
计数原则: 容斥原理
1232个学生选了西班牙语课，879个学生选了法语课，114个学生选了俄语课。103个学生选了西班牙语和法语课，23个学生选了西班牙语和俄语课，14个学生选了法语和俄语课。如果2092个学生至少在西班牙语、法语和俄语课中选1门，则有多少学生选了所有这3门课？
解：|S| = 1232, |F| = 879, |R| = 114, |S∩F| = 103, |S∩R| = 23, |F∩R| = 14, 和|S∪F∪R| = 2092.
使用|S∪F∪R| = |S|+ |F|+ |R| − |S∩F| − |S∩R| − |F∩R| + |S∩F∩R|,
得到 2092 = 1232 + 879 + 114 −103 −23 −14 + |S∩F∩R|.
∴ |S∩F∩R| = 7.
计数原则: 除法法则
除法法则: 如果一个任务能由一个可以用n 种方式完成的过程实现，而对于每种完成任务的方式w，在n 种方式中恰好有 d 种与之对应，那么完成这个任务的方法数为 n/d 。
用集合的方式描述除法法则: 如果一个有限集A 是n个有d 个元素的互斥集合的并集，那么 n = |A|/d.
用函数的方式描述: 如果 f 是从A 到 B的函数, 其中A和B都是有限集, 对于任意的 y ∈ B 恰好有d 个 x ∈ A 满足f(x) = y, 那么 |B| = |A|/d.
计数原则: 除法法则
例: 4个人坐在一个圆桌边，有多少种坐法? 如果每个人左右相邻的人都相同就认为是同一种坐法。
解: 按顺时针方向将桌子周围的座位从1数至4。
座位1有4种选择坐人的方法，座位2有3种选择坐人的方法，座位3有2种选择坐人的方法，座位4有1种选择坐人的方法，这样4！=24种方法将4个人安排到圆桌旁边。
然而，座位1可选的4种方法中会产生相同的安排，因为我们仅将一个人的左边或者右边相邻的人不一样才视为两种不同的安排，所以由除法法则，将4人安排到一个圆桌旁的不同方法数是24/4 = 6种。
树图: 可以使用树图解决计数问题, 其中树中的每个分支都表示一种可能的选择，用树叶表示可能的结果。
例: 假设“我爱离散数学” T恤衫有5种不同的尺寸: S,M,L,XL, 和 XXL。XL有红色、绿色和黑色，XXL有绿色和黑色，其他规格的均有4个不同的颜色(白色, 红色, 绿色, 黑色)。如果每种规格和颜色的T恤衫至少有一件，那么一个零售商必须存多少不同的T恤衫?
零售商必须库存17件不同的T恤衫。
Section 3.2
有20 只鸽子要飞往19个鸽巢休息, 其中至少有1个鸽巢里最少栖息着2只鸽子。
鸽巢原理: 如果 k 是正整数，有 k + 1 个物体放入到k 个盒子, 那么至少有一个盒子包含了2个或更多的物体。
证明: 反证法。 假定k 个盒子中没有一个盒子包含的物体多余1个。那么物体总数至多是k，这与至少 k + 1个物体矛盾。
推论 1: 一个从有 k + 1 甚至更多的元素的集合到k 个元素集合的函数 f 不是一对一函数。
设函数 f 陪域中的每一个元素 y 都有一个盒子。
定义域中满足f(x) = y 的 x 被放进 y 的盒子中。
因为定义域有 k + 1 个或更多元素，而陪域仅有 k 个盒子,所以由鸽巢原理可知这些盒子中有一个包含了2个或更多定义域中的x元素。
因此, f 不是一对一函数。
例1: 在一组 367 人中已定至少有2个人有相同的生日, 这是由于只有366个可能的生日。
例2：27个英文单词中一定至少有2个单词以同一个字母开始。
例3：如果考试的分数从0到100，班上必须有多少名学生，才能保证在期末考试中至少有2名学生得到相同的分数？
广义鸽巢原理: 如果 N 个物体被放进 k 个盒子中, 那么至少有一个盒子中包含了⌈N/k⌉ 个物体。
证明: 反证法. 假设没有一个盒子中包含了比 ⌈N/k⌉ − 1 多的物体。那么至少有一个盒子包含了至少
这里用到不等式⌈N/k⌉ < ⌈N/k⌉ + 1 。这与总共N个物体相矛盾。 例: 100 人中至少有⌈100/12⌉ = 9 出生在同一个月。 例: a) 从一副标准的52张牌中必须选多少张牌才能保证选出的牌中至少有3张牌时同样的花色? b) 必须选出多少张牌才能保证选出的牌中至少有3张红心? 解: a) 假定盒子数为4。 一个盒子中至少包含⌈N/4⌉ 张牌。如果⌈N/4⌉ ≥3，至少选了3张同种花色的牌。最小的整数N 满足at ⌈N/4⌉ ≥3 是 N = 2 ∙ 4 + 1 = 9。 b) 一副牌中有13 张红心和 39 张非红心牌。因此，如果我们选择41 张牌, 最坏情况是有39 张非红心和2 张红心。因此， 当我们选择42 张牌, 至少有3张红心。 (注意，这里没有使用广义鸽巢原理)。 一个大学有38个不同的时间段来安排课程，如果有677门不同的课程，那么需要多少个不同的教室？ Section 3.3 定义:一组不同对象的排列是这些对象的有序排列。对一组r元素有序的排列称为r-排列。 例如: 令 S = {1,2,3}。 有序排列3,1,2 是S的一个排列。 有序排列 3,2 是S 的一个2-排列。 一个n 元集的r-排列记为 P(n,r)。 S = {1,2,3}的2-排列 有1,2; 1,3; 2,1; 2,3; 3,1; 和 3,2。因此, P(3,2) = 6。 定理 1: 如果 n 和r是任意的正整数，1 ≤ r ≤ n, 那么具有n个不同元素的集合的r排列是 P(n, r) = n(n − 1)(n − 2) ∙∙∙ (n − r + 1) 证明: 使用乘积规则。 从n个元素中选择第一个元素的方式有n种。选择第二个元素的方式有n − 1 种, …选择第r个元素有(n − ( r − 1)) 种。 注意P(n,0) = 1, 因为恰好有1个方法排列0个元素。 推论 1: 如果n 和 r 是整数，且1 ≤ r ≤ n, 那么 例: 在进入竞赛的100个不同的人中有多少种方法选出一个一等奖得主、一个二等奖得主、一个三等奖得住? P(100,3) = 100 ∙ 99 ∙ 98 = 970,200 例: 假设一个推销员要访问8个不同的城市，他的访问必须从某个指定的城市开始，但对其它7个城市的访问可以按照任意的次序进行。当访问这些城市时，这个推销员可以有多少种可能的次序? 解: 第一个城市是确定的，其它7个城市是任意的顺序7个元素的排列数为: 7! = 7 ∙ 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 5040 例: 在字母ABCDEFGH 中有多少种排列包含字符串ABC ? 解: 通过找六个对象的排列解决这个问题, ABC, D, E, F, G, 和 H. 6! = 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 720 定义: 集合元素的一个 r-组合 是从这个集合无序选取的r 元素。因此一个r-组合是 这个集合的一个r 元素的子集。 具有n 个不同元素的集合的r-组合 数记为C(n, r)。注意C(n, r) 也记作 并且称为二项式系数。 例: 令 S 是集合{a, b, c, d}。那么 {a, c, d} 是 S的一个 3-组合，等同于 {d, c, a}，因为次序是不考虑的。 C(4,2) = 6， 因为{a, b, c, d} 的2-组合 有六个{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, 和 {c, d}。 定理 2: 设n为正整数，r是满足 n ≥ r ≥ 0的整数， n元素集合的r-组合等于 证明： 通过乘积规则P(n, r) = C(n,r) ∙ P(r,r)。因此, 解: 因此次序不受限制，所以不同的选择方法数共有: 选出47 张牌的方法 例: 从一副52 张牌中选出5张，共有多少种不同方法? 选出47张牌，又有多少种方法? 因此, C(n, r) = C(n, n − r). 推论 2: 令 n 和 r 是非负整数，且r ≤ n，那么C(n, r) = C(n, n − r)。 例: 有多少种方式从10个选手中选择5人参加比赛？ 例:一组30人被培训作为宇航员去完成登陆火星任务，有多少种方式选出6个人的小组来完成这个任务? /docProps/thumbnail.jpeg 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com