離散數(shù)學(xué)課件(英文版)Counting精選課件

1、離散數(shù)學(xué)課件(英文版)Counting精選課件離散數(shù)學(xué)課件(英文版)Counting精選課件CountingCountable SetPermutations and combinationsPigeonhole PrincipleRecurrence RelationsCountingCountable SetCountable Set A set A is countable if and only if we can arrange all of its elements in a linear list in a definite order.“Definite” means that

2、 we can specify the first, second, third element, and so on.If the list ended and with the nth element as its last element, it is finite.If the list goes on forever, it is infinite.Countable Set A set A is countProof of CountabilityThe set of all integers is countable.We can arrange all integer in a

3、 linear list as follows:0,-1,1,-2,2,-3,3,. that is: positive k is the (2k+1)th element, and negative k is the 2kth element in the list.Is the set of rational numbers countable?Proof of CountabilityThe set oSet of Ordered PairsThe set of all objects with the form is countable, where i,j are nonnegati

4、ve integers. ., , , , , , , .So, the set of rational numbers is countable.Set of Ordered PairsThe set ofReal Number Set Is Not CountableThe proof by contradiction proceeds as follows: (1) Assume that the interval (0,1) is countably infinite. (2) We may then enumerate the numbers in this interval as

5、a sequence, r1, r2, r3, . (3) Assume, for example, that the decimal expansions of the beginning of the sequence are as follows. r1 = 0 . 0 1 0 5 1 1 0 . r2 = 0 . 4 1 3 2 0 4 3 . r3 = 0 . 8 2 4 5 0 2 6 . r4 = 0 . 2 3 3 0 1 2 6 . r5 = 0 . 4 1 0 7 2 4 6 . r6 = 0 . 9 9 3 7 8 3 8 . r7 = 0 . 0 1 0 5 1 3 0

6、 . Real Number Set Is Not CountabReal Number Set Is Not CountableThe digits we will consider are indicated in redFrom these digits we define the digits of x as follows. if the nth digit of rn is 0 then the nth digit of x is 1 if the nth digit of rn is not 0 then the nth digit of x is 0 For the examp

7、le above this will result in the following decimal expansion. x = 0 . 1 0 0 1 0 0 1 . Is x one of r1,r2,?So: (0,1) is not a countable setReal Number Set Is Not Countab集合的等勢(shì)關(guān)系等勢(shì)關(guān)系的定義：如果存在從集合A到集合B的雙射，則稱集合A與B等勢(shì)。集合A與B等勢(shì)記為：AB, 否則ABAB意味著：A，B中的元素可以“一一對(duì)應(yīng)”。要證明AB，找出任意一個(gè)從A到B的雙射即可?！暗葎?shì)”的集合就被認(rèn)為是“一樣大”集合的等勢(shì)關(guān)系等勢(shì)關(guān)系的定

8、義：可列集(無窮可數(shù)集)與自然數(shù)集等勢(shì)的集合稱為可列集直觀上說：集合的元素可以按確定的順序線性排列，所謂“確定的”順序是指對(duì)序列中任一元素，可以說出：它“前”、“后”元素是什么。整數(shù)集(包括負(fù)數(shù))與自然數(shù)集等勢(shì)0, -1, 1, -2, 2, -3, 3, -4, .可列集(無窮可數(shù)集)與自然數(shù)集等勢(shì)的集合稱為可列集證明無限集等勢(shì)的例子(0,1)與整個(gè)實(shí)數(shù)集等勢(shì)雙射：f : (0,1)R : f (x) =tg(x- )對(duì)任意不相等的實(shí)數(shù)a,b(ab), 0,1與a,b等勢(shì)雙射： f : 0,1a,b: f (x) =(b-a)x+a(這實(shí)際上意味著：任意長(zhǎng)的線段與任意短的線段等勢(shì))證明無限集

9、等勢(shì)的例子(0,1)與整個(gè)實(shí)數(shù)集等勢(shì)Some interesting words全體多于部分？無窮概念下：不是必然成立的公理伽利略：長(zhǎng)線段不比短線段有更多點(diǎn)無限！再?zèng)]有其它的問題如此深刻地打動(dòng)過人類的心靈。希爾伯特 ??？客滿啦？沒關(guān)系，我讓現(xiàn)在住在 k 號(hào)房間的客人移到 k+1號(hào)。你就住進(jìn)第1號(hào)房間吧！客 滿Some interesting words全體多于部分？啊PermutationsTheorem1,2:Multiplication principleExample:Let A be a set. |A|=n. how many subsets does A have?p(A) = 2

10、n. Why?加法原則一件事情有兩種做法，第一種做法有n種方式，第二種做法有m種方式，則完成這件事情共有mn種方法定義標(biāo)識(shí)符：由字符開頭的8位字符數(shù)字串或者一位字符。共有多少個(gè)合法標(biāo)識(shí)符？含數(shù)字1的小于10000的正整數(shù)個(gè)數(shù)PermutationsTheorem1,2:Permutations Problem 1:How many different sequences, each of length r, can be formed from A, if elements may be repeated?nrIf repetition is not permitted?n(n-1)(n-r+

11、1)Theorem 3Theorem 4: nPrPermutations Problem 1:Permutationsnumber of permutations of n objects taken r at a time (no repetition)nPrpermutation of A: when n = rn! Permutationsnumber of permutatExamples:從52張撲克牌中發(fā)5張牌，如果考慮發(fā)牌次序，共有多少種牌型？How many “words” of three distinct letters can be formed from the le

12、tters of “MAST”?How many “words” of three letters can be formed from the letters of “MAST”?How many “words” of three distinct letters can be formed from the letters of “MASS”?How many distinct “words” of three letters can be formed from the letters of “MASS”?Examples:從52張撲克牌中發(fā)5張牌，如果考慮發(fā)牌次序Permutation

13、sProblem:How many distinguishable permutations of the letters in the word “BANANA” are there?Permutations with limited repeat6!*N1N2 is same as *N2N1*A1A2A3 is same as * A3A2A1So: 6!/(2! *3!)Theorem 5How many distinct “words” of three letters can be formed from the letters of “MASS”?4P3/2!Permutatio

14、nsProblem:園排列從n個(gè)不同元素中，取r個(gè)不重復(fù)的元素排成一個(gè)圓圈，有nPr/r種排列方法園排列從n個(gè)不同元素中，取r個(gè)不重復(fù)的元素排成一個(gè)圓圈，有nCombinationsProblem:Let A be set with n elements, and 1=r permutationOrder does not matter =combinationExamples:Password:Pigeonhole PrincipleIf n pigeons are assigned to m pigeonholes, and mn, then at least one pigeonhole

15、 contains two or more pigeons.Proof by contradiction: Suppose each pigeonhole contains at most 1 pigeon. Then at most m pigeons have been assigned. Since m0, there are (n-m) pigeons have not been assigned. Its a contradiction. Pigeonhole PrincipleIf n pigeoExamplesShow that if any five numbers from

16、1 to 8 are chosen, then two of them will add to 9The key:What is pigeonhole and what is pigeon?If any 11 numbers are chosen from the set 1,2,20, then one of them will be a multiple of anotherExamplesShow that if any five Not Too Far ApartProblem: We have a region bounded by a regular hexagon whose s

17、ides are of length 1 unit. Show that if any seven points are chosen in this region, then two of them must be no farther apart than 1 unit.The region can be divided into six equilateral triangles, then among 7 points randomly chosen in this region must be two located within one triangle.Not Too Far A

18、partProblem: We hShaking Hands at a GatheringSituation: at a gathering of n people, everyone shook hands with at least one person, and no one shook hands more than once with the same person.Problem: show that there must have been at least two of them who had the same number of handshaking.Solution:P

19、igeon: the n participantsPigeonhole: different number between 1 and n-1.Shaking Hands at a GatheringSiExtended Pigeonhole PrincipleIf n pigeons are assigned to m pigeonholes, then one of the pigeonholes must contain at least (n-1)/m+1 pigeons.Proof by contradiction If each pigeonhole contains no mor

20、e than (n-1)/m , then there are at most m (n-1)/m n-1 pigeons at all. Its a contradiction. Extended Pigeonhole PrincipleIPigeonhole by birthdayProblem1: there are 43 students in our class. How many students at least were born in the same weekday?Solution: Hint: In eight people, there are 2 people at

21、 least were born in same weekday.7Pigeonhole by birthdayProblem1Knowing Each Other or NotPigeonhole 1: those knowing APigeonhole 2：those not knowing AProblem: show that among any 6 persons, there are 3 who know each other, or there are 3 who dont know any two others.knowing each othernot knowing eac

22、h otherAThere must be at least 3 elements which fall into one of the two pigeonhole.DCBKnowing Each Other or NotPigeoRecurrence relationsExamples:4,7,10,13,16,1,1,2,3,5,8,13,21,34, (a)0, 1, 2, 2, 6, 5,12,10, 20, 17, 30, 26, Problem:Recurrence relation: the recursive formulae.g: fn = fn-1+fn-2, f1=f2

23、=1 for (a)f1=f2=1: initial conditionRecurrence relationsExamples:ExampleLet A=0,1. Cn: the number of strings of length n in A* that do not contain adjacent 0sC1=?; C2=?;C3=?Cn=? Cn=Cn-1+ Cn-2ExampleLet A=0,1. Cn: the nuFinding an explicit formula: Find an explicit formula for these sequences?Backtra

24、ckingE.g. 1:an = an-1+3, a1 = 2 =recurrence relationan = 2+3(n-1) = explicit formulaE.g. 2bn = 2bn-1+1, b1 = 7bn = 2n+2-1Finding an explicit formula: FThinking Recursively: Problem 1Towers of HanoiHow many moves are need to move all the disks to the third peg by moving only one at a time and never p

25、lacing a disk on top of a smaller one.T(1) = 1T(n) = 2T(n-1) +1Thinking Recursively: Problem Solution of Towers of HanoiT(n) = 2T(n-1) + 12T(n-1) = 4T(n-2) + 24T(n-2) = 8T(n-3) + 4.2n-2T(2) = 2n-1T(1) + 2n-2T(n) = 2n-1Solution of Towers of HanoiT(nThinking Recursively: Problem 2Cutting the planeHow

26、many sections can be generated at most by n straight lines with infinite length. Line nIntersecting all n-1 existing lines to get as most sections as possible L(0) = 1L(n) = L(n-1) +nThinking Recursively: Problem Solution of Cutting the PlaneL(n) = L(n-1)+n = L(n-2)+(n-1)+n = L(n-3)+(n-2)+(n-1)+n =

27、= L(0)+1+2+(n-2)+(n-1)+nL(n) = n(n+1)/2 + 1Solution of Cutting the PlaneLThinking Recursively: Problem 3Josephuss problemFind the position to live, or die!191034578261910345782611J(10,2) = 5;J(13,2) = 7;Thinking Recursively: Problem Thinking Recursively: Problem 3 (cont.)Josephuss problemGiven n peo

28、ple, mth man will be executed.Find the position to live, or die! Just J(n,m)When m =2: J(1) =1J(2n) = 2J(n)-1J(2n+1) = 2J(n)+1J(2m+l) =2l+1Thinking Recursively: Problem Linear Homogeneous Relationis called linear homogeneous relation of degree k.YesNoLinear Homogeneous Relationis Characteristic EquationFor a linear homogeneous recurrence relation of degree k the polynomial of degree k is called its characteristic equation.The cha