Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Summary of permutations (arrangements where the order counts)• r-permutation from n different objects without repetition:• r-permutation from n different objects with repetition:1 if,)!1(1,0 if,1!)(,)!(!),(nnnnnnrrnnrnPrRnrnP ),(!!...!)!...(2121nnkkkkkk • - permutations of n different objects with limited repetition nkkk ...21How many numbers from 1, 1, 1, 2, 2, 3 can be constructed? 1k2k3k!2!3!6Ans:Combinations (selections without reference to the order)• r-combination from n different objects Example: 3-combinations from {a, b, c, d}!),(),( rrnCrnP 24!4)3,4( Pabc acd abd bcdacd adc adb bdcbcd dca bad cdbbdc dac bda cbdcab cad dab dcbcba cda dba dbc!3)3,4( C{a,b,c} {a,c,d} {a,b,d} {b,c,d}rnrrnnrrnPrnC!)!(!!),(),(r-combinations of n objects without repetition{a, b, c, d} 1 1 1 0 {a, b, c} 1 1 0 1 {a, b, d} 1 0 1 1 {a, c, d} 0 1 1 1 {b, c, d} The equivalence of 3-combinations from 4 objectsand permutations of 4 objects with 3 of the same typeCombinations with repetitions.Take, for instance, 4-combinations of {a,b}:{a, a, a, a}, {a, a, a, b}, {a, a, b, b}, {a, b, b, b}, {b, b, b, b}We can consider this problem as the arrangements of 4 identical objects and one separator |:{a, a, a, a} ****|{a, a, a, b} ***|*{a, a, b, b} **|**{a, b, b, b} *|***{b, b, b, b} |****!4!55-permutations of 5 objects if 4 of the them are identical:Combinations with repetitions.Donut shop has 5 types of donuts. In how many ways wecan select ten donuts? This problem can be represented as an equivalent arrangementof ten donuts into 5 boxes. All possible “distributions”Can be considered as “permutations” of a dozen of donuts and4 separators between boxes:One possible arrangement:We need to count the number of permutations of 10 donutsand 4 separators. So, we have 14 objects, 4 of which are identical and 10 are identical.14!10!4!= C (14, 4) From another side, any arrangement can be viewed as a selection of 4 numbers out of 14 (or 10 out of 14) 1 2 3 4 5 6 7 8 9 10 11 12 13 14The number of r-combinations of n objects that can be repeated (any number of times)!),1(),(rrrnPrnCRCan be considered as the number of arrangements of r identical objects and n-1 separators
View Full Document
Unlocking...