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 an 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 an 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)!