Discrete Mathematics - Counting Theory

Discrete Mathematics - Counting Theory

In daily lives, many a times one needs to find out the number of all possible outcomes for a series of events. For instance, in how many ways can a panel of judges comprising of 6 men and 4 women be chosen from among 50 men and 38 women? How many different 10 lettered PAN numbers can be generated such that the first five letters are capital alphabets, the next four are digits and the last is again a capital letter. For solving these problems, mathematical theory of counting are used. Counting mainly encompasses fundamental counting rule, the permutation rule, and the combination rule.

The Rules of Sum and Product

The Rule of Sum and Rule of Product are used to decompose difficult counting problems into simple problems.

· The Rule of Sum − If a sequence of tasks $T_{1}, T_{2}, \dots, T_{m}$ can be done in $w_{1}, w_{2}, \dots w_{m}$ ways respectively (the condition is that no tasks can be performed simultaneously), then the number of ways to do one of these tasks is $w_{1} + w_{2} +$ ⋯+wm. If we consider two tasks A and B which are disjoint (i.e. $A \cap B =$ ∅), then mathematically $| A$ ∪B|=|A|+|B|

· The Rule of Product − If a sequence of tasks $T_{1}, T_{2}, \dots, T_{m}$ can be done in $w_{1}, w_{2}, \dots w_{m}$ ways respectively and every task arrives after the occurrence of the previous task, then there are $w_{1} \times w_{2} \times$ ⋯×wm ways to perform the tasks. Mathematically, if a task B arrives after a task A, then $| A \times B | = | A | \times | B |$

Example

Question − A boy lives at X and wants to go to School at Z. From his home X he has to first reach Y and then Y to Z. He may go X to Y by either 3 bus routes or 2 train routes. From there, he can either choose 4 bus routes or 5 train routes to reach Z. How many ways are there to go from X to Z?

Solution − From X to Y, he can go in $3 + 2 = 5$ ways (Rule of Sum). Thereafter, he can go Y to Z in $4 + 5 = 9$ ways (Rule of Sum). Hence from X to Z he can go in $5 \times 9 = 45$ ways (Rule of Product).