Shandong University Qilu Software College

Shandong University Qilu Software College
Discrete Mathematics Shandong University Qilu Software College 分类加法计数原理、分步乘法计数原理 2018/8/7

Chapter 3 Counting 2018/8/7

§3.1 The basics of counting (1)
3.1.1 Basic counting principles （1）The product rule Definition： Suppose that a procedure can be broken down into a sequence of two tasks.If there are n1 ways to do the first task and n2 ways to do the second task after the first task has been done,then there are n1n2 ways to do the procedure. 2018/8/7

… n1:ways to do T1 … n2:ways to do T2 … … … … … n1*n2: ways to do the procedure 2018/8/7

3.1.1 Basic counting principles （1）The product rule An extended version of the product rule： Suppose that a procedure is carried out by performing the tasks T1,T2,…,Tm in sequence. If task Ti can be done in ni ways after tasks T1,T2,…,and Ti-1 have been done,then there are n1n2…nm ways to carry out the procedure. 2018/8/7

3.1.1 Basic counting principles （2）The sum rule Definition： If a first task can be done in n1 ways and a second task in n2 ways,and if these tasks cannot be done at the same time, then there are n1+n2 ways to do one of these tasks. 2018/8/7

3.1.1 Basic counting principles （2）The sum rule An extended version of the sum rule： Suppose that the tasks T1,T2,…,Tm can be done in n1,n2,…,nm ways,respectively,and no two of this tasks can be done at the same time.Then the number of ways to do one of these tasks is n1+n2+…+nm . 2018/8/7

3.1.2 More complex counting problems 2018/8/7

Counting Internet Address IPv4
1 8 16 24 32 主机地址范围网络地址到 A类地址主机地址（24位）（7位）到 B类地址 10 网络地址（14位）主机地址（16位）主机地址到 C类地址 110 网络地址（21位）（8位）到 D类地址 1110 多目的广播地址（28位）到 E类地址 11110 保留用于实验和将来使用 2018/8/7

3.1.3 The inclusion-exclusion principle Let A1 and A2 be sets;there are |A1| ways to select an element from A1 and |A2| ways to select an element from A2,the number of ways to select from A1 or A2 is the sum of the number of ways to select an element from A1 and the number of ways to select from A2,minus the ways to select an element that is in both A1 and A2. 2018/8/7

3.1.3 The inclusion-exclusion principle 2018/8/7

3.1.4 Tree diagrams 2018/8/7

§3.2 The Pigeonhole principle (1)
3.2.1 Introduction The pigeonhole principle(dirichlet drawer principle)： If k+1 or more objects are placed into k boxes ,then there is at least one box containing two or more of the objects. The pigeonhole principle(dirichlet drawer principle)鸽巢原理（狄里克雷抽屉，狄利克雷）德国数学家。对数论、数学分析和数学物理有突出贡献，是解析数论的创始人之一。 2018/8/7

3.2.1 Introduction Corollary 1： A function f from a set with k+1 or more to a set with k elements is not one-to-one. 2018/8/7

3.2.2 The generalized Pigeonhole principle The generalized Pigeonhole principle(Corollary 2)： If N objects are placed into K boxes , then there is at least one box containing at least N/K objects. 2018/8/7

The generalized Pigeonhole principle
2018/8/7

3.2.3 Some elegant applications of the pigeonhole principle Theorem： Every sequence of n2+1 distinct real numbers contains a subsequence of length n+1 that is either strictly increasing or strictly decreasing. 2018/8/7

§3.2 The Pigeonhole principle
a1,a2,…an2+1 是n2+1个不同的实数对于数列中的每一个项ai 都关联一个有序对(ik, dk) 即任意ak ∈{a1,a2,…an2+1 } 定义函数f: ak → (ik, dk) 其中: ik从ak开始的最长递增子序列的长度 dk从ak开始的最长递减子序列的长度 (结论否定)假如没有长度为n+1的递增(减)序列那么ik和dk都是小于等于n的正整数 2018/8/7

由乘法法则知(ik, dk) 有n2种可能的有序对又由鸽巢原理,n2+1种可能的有序对中必有两个相等即存在as和at(as ≠ at s<t)使is =it 且ds =dt 如有as<at且is =it则把 as加到at开始的递增序列的前面,此时at开始的递增序列的长度为it+1(矛盾) (同样分析as>at) 2018/8/7

例:假如6人中任意2人都认识,或任意2人都不认识.证明在这6人组中或者3人彼此认识,或者3人互不认识. 解:设A是6人中的其中一人.则其他5人与A认识的组成一组,与A不认识的组成一组根据鸽巢原理其中一组中至少有3人假如该3人组是与A认识的,如3人中有2人认识则该2人与A组成3人认识组;如3人中没有2人认识,即3人彼此互不认识. 2018/8/7

假如该3人组是与A不认识的,如3人中有2人不认识,则该2人与A组成3人不认识组;如3人中没有2人不认识,即3人彼此互相认识. 2018/8/7

3.2.3 Some elegant applications of the pigeonhole principle 定义：假设p,q为正整数，p,q≧2 ,则存在最小正整数R(p,q),使得n ≧ R(p,q)时,或者有p人是彼此相识,或者有q人彼此不相识, 称R(p,q)为Ramsey数(拉姆齐数)。 Ramsey(1903~1930)是英国数理逻辑学家,他把抽屉原理加以推广， 2018/8/7

Ramsey Numbers R (p , q) = R (q , p) 2018/8/7

k6完全图,对他的边用红，黑两种颜色任意涂色，则必存在同色边的三角形。
2018/8/7

§3.3 Permutations and Combinations (1)
（1）r-permutation An ordered arrangement of r elements of a set is called an r-permutation.The number of r-permutations of a set with n elements is denoted by P(n,r). 2018/8/7

（1）r-permutation Theorem： The number of r-permutations of a set with n distinct elements is P(n,r) = n(n-1)(n-2)….(n-r+1). 2018/8/7

（2）Circle-permutation 2018/8/7

（3）r-permutation with repetition Theorem： The number of r-permutations of a set of n distinct objects with repetition allowed is nr. 2018/8/7

（1）r-combination An r-combination of elements of a set is an unordered selection of r elements from the set.Thus, an r-combination is simply a subset of the set with r elements. The number of r-combination of a set with n distinct elements is denoted by C(n,r). 2018/8/7

（1）r-combination Note that C(n,r) is also denoted by and is called a binomial coefficient. 2018/8/7

（1）r-combination Theorem： The number of r-combinations of a set with n elements,where n is a nonnegative integer and r is an integer with 0  r  n,equals 2018/8/7

（1）r-combination Corollary： Let n and r be nonnegative integers with r  n .Then C(n,r) = C(n,n-r). 2018/8/7

（2）Combinations with repetition Theorem： There are C(n+r-1,r) r-combinations from a set with n elements when repetition of elements is allowed. 2018/8/7

class A class B class C class D 15= solutions

§3.4 Binomial coefficients (1)
3.4.1 The binomial theorem 杨辉，中国南宋时期杰出的数学家和数学教育家。在13世纪中叶活动于苏杭一带，其著作甚多。他著名的数学书共五种二十一卷。著有《详解九章算法》十二卷（1261年）、《日用算法》二卷（1262年）、《乘除通变本末》三卷（1274年）、《田亩比类乘除算法》二卷（1275年）、《续古摘奇算法》二卷（1275年）。他在《续古摘奇算法》中介绍了各种形式的"纵横图"及有关的构造方法，同时"垛积术"是杨辉继沈括"隙积术"后，关于高阶等差级数的研究。杨辉在"纂类"中，将《九章算术》246个题目按解题方法由浅入深的顺序，重新分为乘除、分率、合率、互换、二衰分、叠积、盈不足、方程、勾股等九类。 17世纪的法国数学家帕斯卡PASCAL也提出来。 2018/8/7

3.4.1 The binomial theorem The binomial theorem：Let x and y be variables,and let n be a nonnegative integer.Then 2018/8/7

3.4.1 The binomial theorem 2018/8/7

3.4.1 The binomial theorem if y=1 then 2018/8/7

3.4.1 The binomial theorem Corollary 1：Let n be a nonnegative integer. Then Corollary 2：Let n be a positive integer.Then Corollary 3：Let n be a nonnegative integer. Then 2018/8/7

3.4.2 Pascal’s identity and triangle Pascal’s identity：Let n and k be positive integers with n  k .Then 2018/8/7

3.4.3 Some other identities of the binomial coefficients Vandermonde’s identity： Let m,n and r be nonnegative integers with r not exceeding either m or n,Then 范德蒙得 2018/8/7

3.4.3 Some other identities of the binomial coefficients Corollary 4：If n is a nonnegative integer,then 2018/8/7

3.4.3 Some other identities of the binomial coefficients Theorem：Let n and r be nonnegative integers with r  n .Then 2018/8/7

§3.5 Generalized permutation (1) and combinations
3.3.1 Permutations with repetition Theorem： The number of r-permutations of a set of n distinct objects with repetition allowed is nr. 2018/8/7

3.3.1 combinations with repetition Theorem： There are C(n+r-1,r) r-combinations from a set with n elements when repetition of elements is allowed. 2018/8/7

3.3.1 combinations with repetition 1 n个无区别的小球放入m个有区别的箱子里的方案数？相当于从m类物体中允许重复的选取n个物体的方案数： C(m+n-1,n)、 C(m+n-1,m-1) 2 生活中的什么情况下可以使用该模型。选男女代表等 3 (x+y+z)4展开式有多少项？ C(3+4-1,4),C(3+4-1,3-1) 那(x+y+z)n 展开式有多少项？ C(3+n-1,3-1) 4 x1+x2+x3=11/n 其中x1≥0,x2≥0,x3≥0 正整数解的个数？

3 solutions class A 三类水果每类先选取一个（第一步），剩余的 4-3个中做允许重复的选择（第二步） class B
1*C( ,4-3) 或者1*C( ,3-1) m类物体允许重复的选取n个且每类必须至少选择一个 C(n-m+m-1,n-m)=C(n-1,n-m)=C(n-1,m-1) class C class D 3 solutions

3.3.2 Permutations with indistinguishable objects Theorem：The number of different permutations of n objects,where there are n1 indistinguishable objects of type 1, n2 indistinguishable objects of type 2,…,nk indistinguishable objects of type k,is Indistinguishable 不加区分的 2018/8/7

... 任意排列 n 个 ... ... ... 重复方案 n1个 n2个 n3个 2018/8/7

3.3.2 Distributing objects into boxes Theorem： The number of ways to distribute n distinguishable objects into k distinguishable boxes so that ni objects are placed into box i (i=1,2,..,k),equals 2018/8/7

3.3.2 Distributing objects into boxes n个球 m个盒子是否允许空盒计数方案备注有区别允许空盒全排列无区别 C(m+n-1,n) m个有区别的元素,取n个作允许重复的组合不允许空盒 C(n-1,m-1) (1)选取m个球每盒一个 (2)n-m有区别的球放入m个有区别盒子中,允许某盒不放 C(n-m+m-1,n-m)=C(n-1,m-1) 一本书的6本复印件放入4个相同的箱子中 n-m个无区别物体允许为空的放入无区分m盒子 2018/8/7

3.3.2 Distributing objects into boxes n个球 m个盒子是否允许空盒计数方案备注有区别不允许空盒映上函数的个数无区别允许空盒 (集合的划分) 4人分配完全相同的3间办公室 Stirling数 2018/8/7

§3.6 Generating permutations
and combinations Overleap 2018/8/7

Chapter 4 Advanced counting techniques 2018/8/7

§4.1 Recurrence relations (1)
4.1.1 The concept of recurrence relations Defination： A recurrence relation for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence,namely,a0,a1,.., an-1,for all integers n with n  n0,where n0 is a nonnegative integer.A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation. 2018/8/7

§4.1 Recurrence relations (2)
4.1.2 Modeling with recurrence relations Example 1：Compound Interest Example 2：Fibonacci Numbers Example 3：The Tower Hanoi Example 4：Bit Strings Example 5：Codeword Enumeration 2018/8/7

Rabbits and Fibonacci Numbers
at least two months old less than two months old month old pairs young total 1 2 3 4 5 6 8

The Tower Hanoi (1, 1, 1) A, B, C (1,1,1) → (3,3,3) (1,2,2) → (3,2,2)
(3,2,2) → (3,3,3) (1,1,1) → (1,2,2) (1,1,1) → (1,1,3) (1,1,3) → (1,2,3) (1,2,3) → (1,2,2) (3,2,2) → (3,2,1) (3,2,1) → (3,3,1) (3,3,1) → (3,3,3) 2018/8/7

§4.2 Solving Recurrence Relations (1)
Linear homogeneous recurrence relation of degree k Definition： A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form an = c1an-1 + c2an-2 +…+ ckan-k where c1,c2,…,ck are real numbers , and ck  0. 2018/8/7

Solving linear homogeneous recurrence relation with constant coefficients Linear homogeneous recurrence relation with constant coefficients : Characteristic equation: 2018/8/7

Solving linear homogeneous recurrence relation with constant coefficients （1）distinct root Theorem 1：Let c1 and c2 be real numbers. Suppose that r2-c1r-c2=0 has two distinct roots r1 and r2. Then the sequence {an} is a solution of the recurrence relation an=c1an-1+c2an-2 if and only if an=b1r1n+b2r2n for n=0,1,2, …,where b1 and b2 are constants. 2018/8/7

=c1(b1r1n-1+b2r2n-1 )+c2(b1r1n-2+b2r2n-2)
（1）distinct root Show that：r12-c1r1-c2=0 , r22-c1r2-c2=0 c1an-1+c2an-2 =c1(b1r1n-1+b2r2n-1 )+c2(b1r1n-2+b2r2n-2) =b1r1n-2(c1 r1+c2) +b2r2n-2(c1 r2+c2) = b1r1n-2r12 +b2r2n-2r22 = b1r1n+b2r2n =an 2018/8/7

r2-c1r-c2=0, r2-r-2=0 r1=2, r2=-1 an=b1r1n+b2r2n =b12n+b2(-1)n
（1）distinct root Exam： an=an-1+2an-2,a0=2,a1=7 r2-c1r-c2=0, r2-r-2=0 r1=2, r2=-1 an=b1r1n+b2r2n =b12n+b2(-1)n a0=2 = b120+b2(-1)0 a1=7 = b121+b2(-1)1 b1=3, b2=-1 an=b12n+b2(-1)n =3*2n + (-1)*(-1)n 2018/8/7

Solving linear homogeneous recurrence relation with constant coefficients （1）distinct root Theorem 2：Let c1,c2,…,ck be real numbers. Suppose that the characteristic equation rk-c1rk-1-…-ck=0 has k distinct roots r1,r2,…,rk.Then a sequence {an} is a solution of the recurrence relation an=c1an-1+c2an-2+…+ckan-k if and only if an=b1r1n+b2r2n+…+bkrkn, for n=0,1,2,…, where b1,b2,…,bk are constants. 2018/8/7

Solving linear homogeneous recurrence relation with constant coefficients （2） Multiple root Theorem 3：Let c1 and c2 be real numbers wth c20. Suppose that r2-c1r-c2=0 has only one root r0.A sequence {an} is a solution of the recurrence relation an=c1an-1+c2an-2 if and only if an=b1r0n+b2nr0n for n=0,1,2,…, where b1 and b2 are constants. 2018/8/7

r2-c1r-c2=0, r2-6r-9=0 r=3 an=b1r0n+b2nr0n =b13n+b23*3n
（2） Multiple root Exam： an=6an-1+9an-2,a0=1,a1=6 r2-c1r-c2=0, r2-6r-9=0 r=3 an=b1r0n+b2nr0n =b13n+b23*3n a0=1 = b130+b23*30 a1=6 = b131+b23*31 b1=1, b2=1 an=3n+n*3n 2018/8/7

Theorem 4：Let c1,c2,…,ck be real numbers. Suppose that the characteristic equation rk-c1rk-1-…-ck=0 has t distinct roots r1,r2,…,rt with multiplicities m1,m2,…,mt , respectively ,so that mi  1 for i=1,2,…,t and m1+m2+…+mt = k. Then a sequence {an} is a solution of the recurrence relation an=c1an-1+c2an-2+…+ckan-k if and only if an = (b1,0+b1,1n+…+b1,m1-1nm1-1)r1n +(b2,0+b2,1n+…+b2,m2-1nm2-1)r2n +…+(bt,0+bt,1n+…+bt,mt-1nmt-1)rtn for n=0,1,2,3,…, where bi,j are constants for 1 i  t and 0  j  mi-1. 2018/8/7

Linear nonhomogeneous recurrence relations with constant coefficients A linear nonhomogeneous recurrence relation with constant coefficients is a recurrence relation of the form an=c1an-1+c2an-2+…+ckan-k+F(n) where c1,c2,…ck are real numbers and F(n) is a function not identically zero depending only on n. The recurrence relaton an=c1an-1+c2an-2+…+ckan-k , is called the associated homogeneous recurrence relation . 2018/8/7

Linear nonhomogeneous recurrence relations with constant coefficients Theorem 1： If {an(p)} is a particular solution of the nonhomogeneous linear recurrence relation with constant coefficients an=c1an-1+c2an-2+…+ckan-k+F(n), then every solution is of the form {an(p)+ an(h)},where {an(h)} is a solution of the associated homogeneous recurrence relation an=c1an-1+c2an-2+…+ckan-k. 2018/8/7

Theorem 2： Suppose that {an} satisfies the linear nonhomogeneous recurrence relation an= c1an-1 + c2an-2 + …+ ckan-k + F(n), where c1,c2,…ck are real numbers and F(n)=(btnt+bt-1nt-1+…+b1n+b0)sn, where b0,b1,…,bt and s are real numbers. When s is not a root of the characteristic equation of the associated linear homogeneous relation,there is a particular solution of the form (ptnt+pt-1nt-1+…+p1n+p0)sn. When s is a root of this characteristic equation and its multiplicity is m,there is a particular solution of the form nm(ptnt+pt-1nt-1+…+p1n+p0)sn. 2018/8/7

§4.3 Divide-and-Conquer Algorithms and Recurrence relations (1)
Overleap 2018/8/7

§4.4 Generating Functions (1)
4.4.1 The concept of generating functions （1）Ordinary generating function Definition： The generating function for the sequence a0,a1,…,ak,…of real numbers is the infinite series 2018/8/7

4.4.1 The concept of generating functions （2）Exponential generating function Definition： The exponential generating function for the sequence a0,a1,…,ak,…of real numbers is the infinite series 2018/8/7

Useful facts about power series （1）The foundational operation of generating function Theorem 1： 2018/8/7

Useful facts about power series （2） The extended binomial theorem Definition： Let  be a real number and let k be a nonnegative integer.Then the extended binomial coefficient C(,k) is defined by 2018/8/7

2018/8/7

Useful facts about power series （2） The extended binomial theorem The extended binomial theorem： Let x be a real number with |x| < 1 and let  be a real number.Then 2018/8/7

and Find the generating functions for : 2018/8/7

Useful Generating functions p219 TABLE 1 2018/8/7

Counting problems and generating functions show :

Example1:find the number of solutions of x1+x2+x3=11 x1 ≥ 0; x2 ≥ 0; x3 ≥ 0 C(3+11-1,11)=78

Example1:find the number of solutions of x1 ≥ 1; x2 ≥ 2; x3 ≥ 3 x1+x2+x3=11 C( ,11-6)=21

Example1:find the number of solutions of x1+x2+x3=11 5≥x1 ≥2; 6≥ x2 ≥3; 7≥ x3 ≥4

Example1:find the number of solutions of x1+2x2+3x3=11 x1 ≥0; x2 ≥0; x3 ≥0

Example1:find the number of solutions of Example1:find the number of solutions of x1+2x2=15 x1 ≥0; x2 ≥0

Example2:Using generating functions to find the number of solutions of r-combinations from a set with n elements when repetition of elements is allowed

Example3:Using generating functions to find the number of ways to select r objects of n different kinds if we must select at least one object of each kind.

Example4:Using generating functions to determine the number of ways to insert tokens worth ＄1, ＄2 and ＄5 into a vending machine to pay for an item that costs r dollars in two cases. 2018/8/7

Using generating functions to solve recurrence relations Example5:Using generating functions to solve the follow recurrence relations. CODEWORD problem an=8an-1+10n-1 a0=1, a1=9 2018/8/7

Solution1: an=8an-1+10n-1 a0=1 ,a1=9 an=8an-1 r-8=0 r=8

2018/8/7

Solution2:

Solution3: See p 2018/8/7

Proving identities via generating functions SEE P224 example18 2018/8/7

§4.5 Inclusion-exclusion (1)
The principle of inclusion-exclusion is useful in counting problems with the union or intersection of two finite sets . [DeMorgan law] domain U，complement sets ,then

solution：(a) if ,then we see and as (1) 2018/8/7

We conclude from（1）and（2）
if so (2) We conclude from（1）and（2） 2018/8/7

DeMogan定理的推广：设 proving：证(a). N=2时定理已证。设定理对n是正确的，即假定：

正确即定理对n+1也是正确的。

最简单的计数问题是求有限集合A和B的并的元素数目。显然有
(1) 即具有性质A或B的元素的个数等于具

有性质A和B的元素个数。 U B A 2018/8/7

证若A∩B=φ，则 | A∪B |= |A| + |B| | A |＝| A ∩( B∪B) | ＝| (A∩B)∪(A∩B)|
| A∪B |＝|(A∩( B∪B))∪(B∩(A∪A))| ＝|(A∩B)∪(A∩B)∪(B∩A)∪(B∩A)| ＝| A∩B| + |A∩B | + | B∩A| ( 3 ) 2018/8/7

∴| A∪B |＝| A | + | B |－| A∩B |
( 3 ) －( 1 ) －( 2 ) 得 | A∪B |－| A |－| B | ＝| A∩B| + |A∩B | + | B∩A| －( | A∩B | + | A∩B | ) －( | B∩A | + | B∩A | ) ＝－ | A∩B | ∴| A∪B |＝| A | + | B |－| A∩B | 2018/8/7

theorem： (2) 2018/8/7

2018/8/7

A B C 2018/8/7

Exam: 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修
数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理、化学的22人。同时修三门的3人。问这学校共有多少学生？ 2018/8/7

令：M 为修数学的学生集合； P 为修物理的学生集合； C 为修化学的学生集合； 2018/8/7

即学校学生数为336人。 2018/8/7

同理可推出：利用数学归纳法可得一般的定理： 2018/8/7

(4) The principle of inclusion-exclusion：
Let A1,A2,…,An be finite sets.Then (4) 2018/8/7

§4.6 Applications Inclusion-exclusion (1)
Let Ai be the subset containing the elements that have property Pi, the number of elements with all the properties P1,P2,P3…Pk will be denoted by N(P1P2P3…Pk ) 2018/8/7

§4.6 Applications Inclusion-exclusion (2)
If the number of elements with none of the properties P1,P2,P3…Pk is denoted by N(P’1P’2P’3…P’k ) and the number of elements in set is denoted by N,then From the inclusion-exclusion principle,we see that: 2018/8/7

The Form of Applications Inclusion-exclusion
2018/8/7

Another Form 2018/8/7

Exam1:求从1到500的整数中能被3或5 除尽的数的个数。 solution:令A为从1到500的整数中被3除
尽的数的集合，B为被5除尽的数的集合 2018/8/7

被3或5除尽的数的个数为 2018/8/7

exam2: 求a,b,c,d,e,f六个字母的全排列
中不允许出现ace和df图象的排列数。 solution：设A为ace作为一个元素出现的排列集，B为 df作为一个元素出现的排列集，为同时出现ace、df的排列数。 2018/8/7

根据容斥原理，不出现ace和df的排列数为：
=6!- (5!+4!)+3!=582 2018/8/7

Exam3: 求由a,b,c,d四个字母构成的n位符号串中，a,b,c,d至少出现一次的符号串数目。
solution：令A、B、C分别为n位符号串中不出现a，b，c符号的集合。由于n位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允许出现a的n位符号串的个数应是 2018/8/7

a，b，c至少出现一次的n位符号串集合即为 2018/8/7

因，故不超过120的合数必然是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。
exam4。求不超过120的素数个数。因，故不超过120的合数必然是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。设为不超过120的数的倍数集， =2，3，5，7。 2018/8/7

2018/8/7

注意：27并非就是不超过120的素数个数，因为这里排除了2，3，5，7四个数，又包含了1这个非素数。2，
3，5，7本身是素数。故所求的不超过 120的素数个数为： =30 2018/8/7

Applications of inclusion-exclusion
Counting the number of primes--- The Sieve of Eratosthenes(伊拉脱森筛) 2018/8/7

exam5。用26个英文字母作不允许重复的全排列，要求排除dog，god，gum，depth，thing字样的出现，求满足这些条件的排列数。
solution：所有排列中，令： 2018/8/7

2018/8/7

出现dog字样的排列，相当于把dog作为一个单元参加排列，故类似有：由于god,dog不可能在一个排列中同时出现，故：类似：
2018/8/7

由于gum,dog可以在dogum字样中同时出现，故有：
类似有god和depth可以在godepth字样中同时出现，故 god和thing可以在thingod字样中同时出现，从而 2018/8/7

2018/8/7

由于god、depth、thing不可以同时出现，故有：
其余多于3个集合的交集都为空集。 2018/8/7

故满足要求的排列数为： 2018/8/7

The number of onto functions Example: How many onto functions are there from a set with six element to a set with three elements? codomain B={b1,b2,b3} ,let P1,P2,P3 be the properties that b1,b2 and b3 are not in the range of the function. N(P’1 P’2 P’3)=N- (N(P1)+N( P2)+N( P3)) + (N(P1P2)+N( P3P3)+N( P2P3)) - N(P1P2P3) 2018/8/7

The number of onto functions: N=36 N(Pi) is the number of functions that do not have bi in their range. N(Pi) =26; N(PiPj)=16 ; N(P1P2P3)=0 N(P1’ P2’ P3’)=N- (N(P1)+N( P2)+N( P3)) + (N(P1P2)+N( P3P3)+N( P2P3)) - N(P1P2P3)=36- ( )+( )-0= 36- C(3,1)26+C(3,2)16-0=540

Theorem： Let m and n be positive integers with m  n.Then, there are onto functions from a set with m elements to a set with n elements. (m n) ≥ 2018/8/7

exam:How many ways are there to assign five different jobs to four different employees if every employee is assigned at least one job? Labeled objects to labeled boxes not empty 2018/8/7

§4.6 Applications of inclusion-exclusion
Derangements 错排问题/错位排列 instance： A derangement is a permutation of objects that leaves no object in its original position. The Hatcheck Problem 2018/8/7

Consider: The Hatcheck Problem Given
Derangements Consider: The Hatcheck Problem Given An employee checks hats from n customers However, he forgets to tag them When customers check out their hats, they are given one at random Question What is the probability that no one will get their hat back?

Derangements The hat-check problem can be modeled using derangements: permutations of objects such that no element is in its original position - Example: is a derangement of but is not derangement The number of derangements of a set with n elements is Thus, the answer to the hatcheck problem is Note that Thus, the probability of the hatcheck problem converges

§4.6 Applications of inclusion-exclusion
Derangements 错排问题/错位排列 Theorem： The number of derangements of a set with n elements is 2018/8/7

n个元素依次给以标号1，2，…，n。 N个元素的全排列中，求每个元素都不在自己原来位置上的排列数。设为数在第位上的全体排列，
设为数在第位上的全体排列， =1，2，…，n。因数字不能动，因而有： 2018/8/7

元素i不在自己原来位置上的排列数 2018/8/7

m个元素在自己原来位置上的排列数. 2018/8/7

每个元素都不在原来位置的排列数为 2018/8/7

Exam1:数1，2，…，9的全排列中，求偶数在原来位置上，其余都不在原来位置的错排数目。 solu：实际上是1，3，5，7，9五个数
的错排问题，总数为： 2018/8/7

分别表示A,C,E,G在原来位置上的排列，则错排数为：
Exam2: 在8个字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四个字母不在原来上的错排数目。 8个字母的全排列中，令分别表示A,C,E,G在原来位置上的排列，则错排数为： 2018/8/7

2018/8/7

Exam3:求8个字母A,B,C,D,E,F,G,H的全排列中只有4个不在原来位置的排列数。
solu：8个字母中只有4个不在原来位置上，其余4个字母保持不动，相当于4个元素的错排，其数目为 2018/8/7

故8个字母的全排列中有4个不在原来位置上的排列数应为：C(8,4)·D4 =C(8,4)·9=630
2018/8/7

Shandong University Qilu Software College

Similar presentations

Presentation on theme: "Shandong University Qilu Software College"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

Shandong University Qilu Software College

Similar presentations

Presentation on theme: "Shandong University Qilu Software College"— Presentation transcript:

Similar presentations

About project

反馈