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?