4.1.2 Pigeonhole principle: Strong Form 今 Theoren4.2:Letq1,q2…, gn be positive integers. If q1+q2+.+qn-n+l objects are put into n boxes, then either the first box contains at least qi objects, or the second box contains at least q2 objects, .., or the nth box contains at least qn objects. 今 Proof: Suppose that we distribute 91+q2+.+qn-n+l objects among n boxes
4.1.2 Pigeonhole principle:Strong Form ❖ Theorem 4.2: Let q1 ,q2 ,…,qn be positive integers. If q1+q2+…+qn -n+1 objects are put into n boxes, then either the first box contains at least q1 objects, or the second box contains at least q2 objects, … , or the nth box contains at least qn objects. ❖ Proof:Suppose that we distribute q1+q2+…+qn -n+1 objects among n boxes
)If n(r-1)+l objects are put into n boxes, then at least one of the boxes contains r or more of the objects. Equivalently, (2)If the average of n non-negative integers mi, mose.,m is greater than r-1: (m,+m2+.+mm/n>r-1, then at least one of the integers is greater than or equal to r 今 Proof:(1)q1=q2=…=qn=r q1+q2+.+qn-n+l=rn-n+=(r-1)n+l, then at least one of the boxes contains r or more of the objects (2)(m1+m2+…+mn)>(r-1)n, 今(m1+m2+…+mn)≥(r-1n+1
❖ (1)If n(r-1)+1 objects are put into n boxes, then at least one of the boxes contains r or more of the objects. Equivalently, ❖ (2)If the average of n non-negative integers m1 ,m2 ,…,mn is greater than r-1: (m1+m2+…+mn )/n>r-1, then at least one of the integers is greater than or equal to r. ❖ Proof:(1)q1=q2=…=qn=r ❖ q1+q2+…+qn -n+1=rn-n+1=(r-1)n+1, then at least one of the boxes contains r or more of the objects。 ❖ (2)(m1+m2+…+mn )>(r-1)n， ❖ (m1+m2+…+mn )≥(r-1)n +1
Example 6: Two disks, one smalle her than the other, are each divided into 200 congruent sectors. In the larger disk 100 of the sectors are chosen arbitrarily and painted red; the other 100 of the sectors are painted blue. In the smaller disk each sector is painted either red or blue with no stipulation on the number of red and blue sectors. The small disk is then placed on the larger disk so that their centers coincide. Show that it is possible to align the two disks so that the number of sectors of the small disk whose color matches the corresponding sector of the large disk is at least 100 &o if the large disk is fixed in place g there are 200 possible positions for the small disk such that each sector of the small disk is contained in a sector of the large disk g color matches the corresponding 令20000/200=100>100-1 Position with at least 100 color matches
❖ Example 6:Two disks, one smaller than the other, are each divided into 200 congruent sectors. In the larger disk 100 of the sectors are chosen arbitrarily and painted red; the other 100 of the sectors are painted blue. In the smaller disk each sector is painted either red or blue with no stipulation on the number of red and blue sectors. The small disk is then placed on the larger disk so that their centers coincide. Show that it is possible to align the two disks so that the number of sectors of the small disk whose color matches the corresponding sector of the large disk is at least 100. ❖ if the large disk is fixed in place ❖ there are 200 possible positions for the small disk such that each sector of the small disk is contained in a sector of the large disk. ❖ color matches the corresponding ❖ 20000/200=100>100-1 ❖ Position with at least 100 color matches
4.2 Permutations of sets 842.1 Basic counting principles Theorem 4.3(Addition principle): IfA, A2, .. A are disjoint sets, then the number of elements in the union of these sets is the sum of the numbers of elements in them 令|A1UA20…∪An=A1+A2+.+n
4.2 Permutations of sets ❖4.2.1 Basic counting principles ❖ Theorem 4.3(Addition principle): If A1 , A2 , … , An are disjoint sets, then the number of elements in the union of these sets is the sum of the numbers of elements in them. ❖ | A1∪A2∪…∪An |=|A1 |+|A2 |+…+|An |
4. Examplel: A student wishes to take either a mathematics course or biology course, but not both. If there are 4 mathematics course and 2 biology course for which the student has the necessary prerequisites, then the student can choose a course to take in 4+2=6 ways 4 Theorem 4.mUltiplication principle): Let A and B be two finite sets. Let AFp and Bg, then A×B|=p×q
❖ Example1: A student wishes to take either a mathematics course or biology course, but not both. If there are 4 mathematics course and 2 biology course for which the student has the necessary prerequisites, then the student can choose a course to take in 4+2=6 ways. ❖ Theorem 4.4(Multiplication principle): Let A and B be two finite sets. Let |A|=p and |B|=q, then |A×B|=p×q
&o Example2: A student wishes to take a mathematics course and a biology course. If there are 4 mathematics course and 2 biology course for which the student has the necessary prerequisites, then the student can choose courses to take in 4X2=8 wavs
❖ Example2: A student wishes to take a mathematics course and a biology course. If there are 4 mathematics course and 2 biology course for which the student has the necessary prerequisites, then the student can choose courses to take in 4×2=8 ways
4.2.2 Permutations of sets &o An ordered arrangement of r elements of an n-element set Is called a r-permutation. o We denote by p(n, r) the number of r permutations of an n-element set Ifr>n, then p(n, r)=0. An n-permutation of an n-element set s is called a permutation ofs. A permutation of a set s is a listing of the elements of s in some order
4.2.2 Permutations of sets ❖ An ordered arrangement of r elements of an n-element set is called a r-permutation. ❖ We denote by p(n,r) the number of rpermutations of an n-element set. If r>n, then p(n,r)=0. An n-permutation of an n-element set S is called a permutation of S. A permutation of a set S is a listing of the elements of S in some order
Theorem 4.5: For n and r positive integers with rsn, 令p(n,r)=n(n-1)(n-r+1 4. Proof: In constructing an r-permutation of an n element set, we can choose the first item in n ways the second item in n-l ways whatever choice of the first item,.., and the rth item in n-(r-1) ways whatever choice of the first r-l items. By the multiplication principle the r items can be chosen in n(n-1)….(n-r+1)ways. ☆ We define n!b n !=n(n 1).2°1 o with the convention that 0:=l.Thus p(n, r=n /(n-r)
❖ Theorem 4.5: For n and r positive integers with rn, ❖ p(n,r)=n(n-1)…(n-r+1) ❖ Proof:In constructing an r-permutation of an nelement set, we can choose the first item in n ways, the second item in n-1 ways whatever choice of the first item,… , and the rth item in n-(r-1) ways whatever choice of the first r-1 items. By the multiplication principle the r items can be chosen in n(n-1)…(n-r+1) ways. ❖ We define n! by ❖ n!= n(n-1)…2•1 ❖ with the convention that 0!=1.Thus p(n,r)=n!/(n-r)!
Example: What is the number of ways to order the 26 letters of the alphabet so that no two of the vowels a,e,i,o, and u occur consecutively?(元音字母 中任意两个都不得相继出现) .8 Solution: The first task is to decide how to order the consonants among themselves. 21 4 Our second task is put the vowels in these places. 令p(22,5)=22/17! o By the multiplication principle, the numble of with no two vowels consecutive is 21 x22 /17/et ordered arrangements of the letters of the alphabe
❖ Example:What is the number of ways to order the 26 letters of the alphabet so that no two of the vowels a,e,i,o,and u occur consecutively?(元音字母 中任意两个都不得相继出现) ❖ Solution:The first task is to decide how to order the consonants among themselves. ❖ 21! ❖ Our second task is put the vowels in these places. ❖ p(22,5)=22!/17! ❖ By the multiplication principle, the numble of ordered arrangements of the letters of the alphabet with no two vowels consecutive is 21!22!/17!
Example: What is the number of ways to order the 26 letters of the alphabet so that it contains exactly seven letters between a and b? a b,P(24,7) b.a,P(24,7) o between a and b 2P(24, 7) 今P(18,18)=18 今2P(24,7)18 ☆ linar permutation . o circular permutation
❖ Example: What is the number of ways to order the 26 letters of the alphabet so that it contains exactly seven letters between a and b? ❖ a…….b，P(24,7) ❖ b…….a，P(24,7) ❖ between a and b 2P(24,7) ❖ P(18,18)=18!. ❖ 2P(24,7)18! ❖ linar permutation ❖ circular permutation