Homework SourseHow can you devise a strategy to solve problems using enumer
How can you devise a strategy to solve problems using enumeration methods, permutations, combinations, along with the sum rule and product rule?
Solution
Basics of Counting
People may think that counting is easy, and certainly sometimes it is. But some of the aspects of counting are not simple, especially counting a large number of elements. In this case, we need to use some mathematical skills to find out the answer.
Consider counting the number of elements in a list, where each element has an index beginning with some integer m and ending with some integer n, and m < n. Then there are n - m + 1 elements in the list, from m to n inclusive. For example, if the first index is 0, and the last indexed element is 99, then you have 99 - 0 + 1 = 100 elements. This method also works for counting a certain number of elements from only part of the list (for example, the number of elements between index nos. 12 and 43.)
There are two basic counting principles:
the first step can be performed in n1 ways;
the second step can be performed in n2 ways (ignoring how the first step was performed), . . .; and
the kth step can be performed in nk ways.
Then the whole operation can be performed in n1 * n2 * ........... * nk ways.
| Sum Rule | Suppose that an operation can be performed by either of two different procedures, with m possible outcomes for the first procedure and n possible outcomes for the second. If the two sets of possible outcomes are disjoint, then the number of possible outcomes for the operation is m + n. |
| Product Rule | Suppose that an operation consists of k steps and: the first step can be performed in n1 ways; the second step can be performed in n2 ways (ignoring how the first step was performed), . . .; and the kth step can be performed in nk ways. Then the whole operation can be performed in n1 * n2 * ........... * nk ways. |
