4.4 Permutations and combinations of multisets Multisets A multiset is a set in which an item may appear more than once. Sets and multisets are quite similar: both support the basic set operations of union, intersection, and difference item a; n; n1a1,n 2 a 2 a k ak Example: a, a, a, a, b, b,c) {4°a,2b,l° a 2…,00°a °a
4.4 Permutations and Combinations of multisets ▪ Multisets :A multiset is a set in which an item may appear more than once. . ▪ Sets and multisets are quite similar: both support the basic set operations of union, intersection, and difference. ▪ item ai ni， ▪ {n1 •a1 ,n2 •a2 ,…,nk •ak } ▪ Example：{a,a,a,a,b,b,c} ▪ {4•a,2•b,1•c} ▪ {•a1 ,•a2 ,…,•ak }
4.4 Permutations and combinations of multisets 4.4.1 Permutations of multisets If s is a multiset, a r-permutation of s is an ordered arrangement of r of the objects of s. If the total number of objects of s is n, then a n-permutation of S will also be called a permutation of s For example, if S=2.a, 1.b, 3.c, then aacb acbc cacc are 4-permutations of s abcca is a permutation of s The multiset s has no 7-permutations since >2+1+3=6. the number of obiects of s
4.4 Permutations and Combinations of multisets ▪ 4.4.1 Permutations of multisets ▪ If S is a multiset, a r-permutation of S is an ordered arrangement of r of the objects of S. If the total number of objects of S is n，then a n-permutation of S will also be called a permutation of S. ▪ For example, if S={2•a,1•b,3•c}, then ▪ aacb acbc cacc are 4-permutations of S, ▪ “abccac” is a permutation of S. ▪ The multiset S has no 7-permutations since 7>2+1+3=6, the number of objects of S
Theorem 4.10: Let s be a multiset with objects of k different types where each has an infinite repetition number. Then the number of r-permutations of s is Proof: In constructing a r-permutation of s, we can choose the first item can be an object of any one of the k types. Similarly the second item to be an object of any one of the k types, and so on Since all repetition numbers of s are infinite the number of different choices for any item is always k and does not depend on the choices of any previous Items By the multiplication principle, the r items can be chose in k ways
▪ Theorem 4.10: Let S be a multiset with objects of k different types where each has an infinite repetition number. Then the number of r-permutations of S is k r . ▪ Proof: In constructing a r-permutation of S, ▪ we can choose the first item can be an object of any one of the k types. ▪ Similarly the second item to be an object of any one of the k types, and so on. ▪ Since all repetition numbers of S are infinite, the number of different choices for any item is always k and does not depend on the choices of any previous items. ▪ By the multiplication principle, the r items can be chose in kr ways
Corollary4.4:LetS-{n1°a1,n2°a2y…,n1°at} andn;≥ r for each i=1,2,…,n, then the number of r-permutations of s is kr
▪ Corollary 4.4: Let S={n1 •a1 ,n2 •a2 ,…,nk •ak }， and ni r for each i=1,2,…,n，then the number of r-permutations of S is kr
Theorem 4.11: Let multiset S={n°a1,n2a2y…,nk·at},and n=n+n2+.+nk s. Then the number of permutations of s equals n! /(n In2.ngo) Proof: We can think of it this way. There are n places, and we want to put exactly one of the objects of s in each of the places. Since there are n au,s in s. we must choose a subset of n, places from the set of n places. C(n, n1) We next decided which places are to be occupied by the a2
▪ Theorem 4.11: Let multiset S={n1 •a1 ,n2 •a2 ,…,nk •ak }, and n=n1+n2+…+nk=|S|. Then the number of permutations of S equals n!/(n1 !n2 !…nk !)。 ▪ Proof: We can think of it this way. There are n places, and we want to put exactly one of the objects of S in each of the places. ▪ Since there are n1 a1 ’s in S, we must choose a subset of n1 places from the set of n places. ▪ C(n,n1 ) ▪ We next decided which places are to be occupied by the a2 ’
Example What is the number of permutations of the letters in the word Mississippi?
▪ Example What is the number of permutations of the letters in the word Mississippi?
LetS={n1°a1n2°a2y…,nkal},and n=n+n2+.+nk=s, then the number n of r permutations of s equals r>n (2n!(n1!n2…n") t-n (3)k n:≥ r for each i=12n (4)Ifr<n, there is, in general, no simple formula for the number of r-permutations of Nonetheless a solution can be obtained by the technique of generating functions, and we discuss this in 4.6
▪ Let S={n1 •a1 ,n2 •a2 ,…,nk •ak }, and n=n1+n2+…+nk=|S|，then the number N of rpermutations of S equals ▪ (1)0 r>n ▪ (2)n!/(n1 !n2 !…nk !) r=n ▪ (3)kr ni r for each i=1,2,…,n ▪ (4)If r<n, there is, in general, no simple formula for the number of r-permutations of S. ▪ Nonetheless a solution can be obtained by the technique of generating functions, and we discuss this in 4.6
4. 4.2 Combinations of multisets If s is a multiset. a r-combination of s is an unordered selection of r of the objects of s Thus an r-combination of s is a submultiset of s. If s has n objects then there is only one n-combination of s, namely, s itself. If s contains objects of k different types, then there are k 1-combinations of s Example If S={2°a,l·b,3·e}, then the3- combinations of s are {2°a,1°b},{2a,1c},{1°a,l·b,l°c}, {l°a,2c},{lb,2c},仔3°c}
▪ 4.4.2 Combinations of multisets ▪ If S is a multiset, a r-combination of S is an unordered selection of r of the objects of S. ▪ Thus an r-combination of S is a submultiset of S. If S has n objects，then there is only one n-combination of S, namely, S itself. ▪ If S contains objects of k different types, then there are k 1-combinations of S. ▪ Example If S={2•a,1•b,3•c}, then the 3-combinations of S are ▪ {2•a,1•b},{2•a,1•c}, {1•a,1•b,1•c}, {1•a,2•c},{1•b,2•c},{3•c}
Theorem 4.12: Lets=looa1oo'a2,., oo ak. Then the number of r-combinations of s equals c(ktr-lg r) Proof. ( lThe number of r-combinations of s equals the number of solutions of the equation Ex,=r where x1,x2,., Xk are non-negative integers (2)We show that the number of these solutions equals the number of permutations of the multiset={(k-1)·0,r·1}
▪ Theorem 4.12: Let S ={·a1 ,·a2 ,…, ·ak }. Then the number of r-combinations of S equals C(k+r-1,r)。 ▪ Proof. (1)The number of r-combinations of S equals the number of solutions of the equation ▪ where x1 ,x2 ,…,xk are non-negative integers x r k i i = =1 (2)We show that the number of these solutions equals the number of permutations of the multiset T={(k-1)·0,r·1}
Corollary4.5:Lets={n;°a1n2°a2,…,nka13}, and n > r for each i=1.2 Then the number of r-combinations of s is C(k+r-1 r) Example Suppose that a cookie shop has seven different kinds of cookies. How many dififerent ways can twelve cookies be chosen?
▪ Corollary 4.5: Let S={n1 •a1 ,n2 •a2 ,…,nk •ak }， and ni r for each i=1,2,…,n. Then the number of r-combinations of S is C(k+r-1,r). ▪ Example Suppose that a cookie shop has seven different kinds of cookies. How many different ways can twelve cookies be chosen?