Permutations with Repetition • Theorem 1 ○ The number of r-permutations of a set of n objects with repetition allowed is ○ GP(n,r) n^r • Proof ○ There are n ways to select an element of the set ○ for each of the r positions in the r-permutation when repetition is allowed ○ Hence, by the product rule there are n^r r-permutations with repetition. • Example ○ How many strings of length r can be formed from the uppercase letters of the English alphabet? ○ The number of such strings is 〖26〗^r ○ which is the number of r-permutations of a set with 26 elements • Example 2 ○ How many function are there f:A→B where |A|=k, and |B|=m? m^k Combinations with Repetition • Example ○ How many ways are there to select five bills from a box containing at least five of each of the following denominations: $1, $2, $5, $10, $20, $50, and $100? ○ Place the selected bills in the appropriate position of a cash box illustrated below: ○ Some possible ways of placing the five bills: ○ The number of ways to select five bills corresponds to ○ the number of ways to arrange six bars and five stars in a row. ○ This is the number of unordered selections of 5 objects from a set of 11. ○ Hence, there are § C(11,5)=11!/5!6!=462 ○ ways to choose five bills with seven types of bills • Theorem 2 ○ The number of r-combinations from a set with n elements when repetition of elements is allowed is ○ C(n+r−1,r)=C(n+r−1,n−1) • Proof ○ Each r-combination of a set with n elements with repetition allowed can be represented by a list of n – 1 bars and r stars. ○ The bars mark the n cells containing a star for each time the ith element of the set occurs in the combination. ○ The number of such lists is C(n+r−1,r) ○ because each list is a choice of the r positions to place the stars ○ from the total of n+r−1 positions to place the stars and the bars. ○ This is also equal to C(n+r−1,n−1) ○ which is the number of ways to place the n – 1 bars • Example 1 ○ How many solutions does the equation x_1+x_2+x_3=11 (x_1,x_2,x_3∈Z+ ) have ○ Each solution corresponds to a way to select 11 items from a set with 3 elements ○ x_1 elements of type one, x_2 of type two, and x_3 of type three. ○ By Theorem 2 it follows that the number of solution is ○ C(3+11−1,11)=C(13,11)=C(13,2)=(13⋅12)/(1⋅2)=78 • Example 2 ○ Suppose that a cookie shop has four different kinds of cookies. ○ How many different ways can six cookies be chosen? ○ The number of ways to choose six cookies is ○ the number of 6-combinations of a set with four elements. ○ By Theorem 2 the number of ways to choose six cookies from the four kinds is ○ C(9,6)=C(9,3)=(9⋅8⋅7)/(1⋅2⋅3)=84 Permutations and Combinations with and without Repetition
