Counting Techniques

Combinatorics is a fascinating branch of discrete mathematics, which deals with the art of counting. Very often we ask the question, In how many ways can a certain task be done? Usually combinatorics comes to our rescue. In most cases, listing the possibilities and counting them is the least desirable way of finding the answer to such a problem. Often we are not interested in enumerating the possibilities, but rather would like to know the total number of ways the task can be done.

Counting Techniques (Cont.)

Since in most cases it not feasible to list all the outcomes, we use the following techniques to COUNT them when listing them:

Fundamental Counting Rule
Permutations
Combinations

Addition Principle

Let A and B be two mutually exclusive tasks. Suppose task A can be done in m ways and task B in n ways. Then task A or task B can take place in m + n ways. ?

Example

A student can choose a computer project from one of three lists. The three lists contain 23, 15, and 19 possible projects, respectively. No project is on more than one list. How many possible projects are there to choose from?
Solution: The student can choose a project by selecting a project from the first list, the second list, or the third list. Because no project is on more than one list, by the sum rule there are 23 + 15 + 19 = 57 ways to choose a project.