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?