12.3 Outline
- Distinguish permutations and combinations
- License plate problem
- Which method?
12.3 Essential Ideas
Fundamental Counting Principle
If one task can be performed in m ways, and if, after that task is completed, a second task can be performed in n ways, then the total number of ways of ways for both tasks is found by multiplication: mn. Repetitions are allowed.
Permutations
A permutation of r elements selected from a set of n elements is an ordered arrangement of those r elements selected without repetitions. The order of selection is important.
Combinations
A combination of r elements selected from a set of n elements is an subset of r elements selected without repetitions. The order of selection is not important.
Counting Formulas
Factorial: n!= n(n − 1)(n − 2)(n − 3) …(3)(2)(1).
Count-down formula: n! =n(n − 1)!
Permutation formula: The number of ways of selecting r elements from a set with cardinality n in which the order of section is important is n!/(n −r)!
Combination formula: The number of ways of selecting r elements from a set with cardinality n in which the order of selection is not important is n!/r!(n −r)!.
Number of distinguishable permutations: If n objects are partitioned so that there are n1 of one kind, n2 of another, and n3 of still a third kind (so that n1 + n2 + n3 = n), then the number of ways that the n objects can be selected is n! divided by the product of (n1)!(n2)!(n3)!.