counting Method

Counting Methods
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.
Since in most cases it not feasible to list all the outcomes, we use the following techniques to COUNT them when listing them:

The Fundamental Counting Principle
- 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 1
A student can choose a computer project from one of three lists. The three lists contain 23, 15,and 19 possible projects, respectively. No projectis 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.

Example 2
A freshman has selected four courses and needs one more course for the next term. There are 15 courses in English, 10 in French, and 6 in German she is eligible to take. In how many ways can she choose the fifth course?

Solution: Let E be the task of selecting a course in English, F the task of selecting a course in French, and G that of selecting a course in German. These tasks can be done in 15, 10, and 6 ways, respectively,and are mutually exclusive, so, by the addition principle, the fifth course can be selected in |E| + |F| + |G| = 15 + 10 + 6 = 31 ways.


Suppose a task T is made up of two subtasks, subtask T1 followed by sub
task T2. If subtask T1 can be done in m1 ways and subtask T2 in m2 different ways for each way subtask T1can be done, then taske T can be done in m1* m2 ways.
Example 1
Find the number of two-letter words that begin with avowel — a, e, i, o, or u.
Solution: The task of forming a two-letter word consists of two subtasks T1 and T2: T1 consists of selecting the first letter and T2 selecting the second letter, as in the following Figure.






=130

Example 2
If a coin is tossed and the number cube is rolled simultaneously then the tree diagram can be the following:

Solution:we see that the total number of possibilities is 2 ?6
= 12.
The number of ways in which a series of successive things can occur is found by multiplying the number of ways in which each thing can occur.

Example 3
A new company with just two employees, Sanch and Patel, rents a floor of a building with 12 offices. How many ways are there to assign different offices to these two employees?
Solution: the procedure of assigning offices to these two employees consists of assigning an office to Sanchez, which can be done in 12 ways, then assigning an office to Patel different from the office assigned to Sanchez, which can be done in 11 ways. By the product rule, there are 12 ? 11 = 132 ways to assign offices to these two employees.
Example 4
How many different bit strings of length seven are there?

Solution: Each of the seven bits can be chosen in two ways, because each bit is either 0 or 1. Therefore, the product rule

7
shows there are a total of 2 = 128 different bit strings of
length seven.

Example 5
How many different license plates are available if each plate contains a sequence of three letters followed by three digits?
Solution: There are 26 choices for each of the three letters and ten choices for each of the three digits. Hence, by the product rule there are a total of 26 ?26 ? 26 ? 10 ? 10 ? 10 = 17,576,000 possible license plates.




Example 6
Telephone numbers in the United States begin with three- digit area codes followed by seven-digit local telephone numbers. Area codes and local telephone numbers cannot begin with 0 or 1. How many different telephone numbers are possible?
Solution : This situation involves making choices with ten groups of items. Here are the choices for each of the ten groups of items:
Area Code Local Telephone Number 8 10 10 8 10 10 10 10 10 10
The total number of different telephone numbers is:

8 · 10 · 10 · 8 · 10 · 10 · 10 · 10 · 10 · 10 = 6,400,000,000

Example 7:
An eight?bit word is called a byte. Find the number of bytes with their second bit 0 or the third bit 1 ?

The answer is 27 + 7 = 128 + 128 = 256.
Inclusion –Exlusion Principal
Up to this point we have only considered disjoint sets when applying addition counting principle. Suppose that that the set S and T are not disjoint and we wish to find | | . when we add number of elements in S to the number in T we count the number of elements in twice. Therefore we must subtraction the numbers of elements in .
Theorem
Let S and T be sets the number of element can be selected from S or T is equal to | | | | | |
Example:
How many bit strings of length eight either start with a 1 bit or end with the two bits 00?




128 + 64 ? 32 = l60

Example:
Suppose that in a group of 100 students ,60 take math ,75 take History ,and 45 take both .How many take mathematics or History?
Solution: let M be the set of student that take math ,and H be the student take History .
| | | | | | | |



=90