Chap 7: Counting (Part 1)

Multiplication Principle (Product Rule):

DEFINITION

If each of m and n is a positive integer, a is an m-element set, and b is an n-element set, then |a × b| = m.n
or restated, |a × b| = |a||b|.

Example 1:

A person wants to go from station A to station C via station B. There are three routes from A to B and four routes from B to C. In how many ways can he travel from A to C?

           Solution: 

                               A –> B in 3 ways

              B –> C in 4 ways

              => A –> C in 3 × 4 = 12 ways

Example 2

              A college offers 7 courses in the morning and 5 in the evening. Find the possible number of choices with the student if he wants to study one course in the morning and one in the evening.

              Solution: 

              The student has seven choices from the morning courses out of which he can select one course in 7 ways.

              For the evening course, he has 5 choices out of which he can select one in 5 ways.

              Hence the total number of ways in which he can make the choice of one course in the morning and one in the evening =   7 × 5 = 35.

Addition Principle (Sum Rule):

DEFINITION

•       A task can be done either in one n1 ways or in one of n2 ways, where none of the set n1 ways is the same as any of the set of n2 ways, then there are n1+n2 ways to do the task.

•       For any joint two set of A and B,

            n(AᴠB) = n (A) + n(B) – n(AᴠB)

•       If A and B are disjointed,

           n(AᴠB) = n (A) + n(B)      

Example1

Suppose that we want to buy a computer from one of two makes A₁ and A₂ Suppose also that those makes have 12 and 18 different models, respectively. Then how many models are there altogether to choose from ?

Solution: Since we can choose one of 12 models of make A₁ or one of 18 of A₂, there are altogether 12 + 18 = 30 models to choose from.   

ADDITIONAL PRINCIPLE FOR DISJOINT EVENT

•      Let A₁ and A₂ be disjoint events, that is events having no common outcomes, with n₁ and n₂ possible outcomes, respectively. Then the total number of outcomes for the event "A₁ or A₂" is n₁ + n₂.

Example 1

•      Suppose there are 5 chicken dishes and 8 beef dishes. How many selections does a customer have ? 

•      Solution : In this case, an event is "selecting a dish of either kind". There are 5 outcomes for the chicken event and 8 outcomes for the beef event. According to the addition principle there are 5 + 8 = 13 possible selections.