Fundamental Counting Principle (Theorem) of Multiplication

Counting Numbers

The numbers that we use to count things or objects. Natural Numbers are called counting numbers.

N = {1, 2, 3, ... ∞ }

Fundamental Counting Principle of Multiplication

If a total event can be sub-divided into two or more independent sub-events, then the number of ways in which the total event can be accomplished is given by the product of the number of ways in which each sub-event can be accomplished.

Number of ways in which the total event can be accomplished

= (Number of ways in which the 1st sub-event can be accomplished) × (Number of ways in which the 2nd sub-event can be accomplished) × (Number of ways in which the 3rd sub-event can be accomplished) × ...

⇒ nE = nSE1 × nSE2 × nSE3 × ....

Illustration 1 - Problem

In how many ways can a person travel from New Delhi to New York via London, when there are four routes from New Delhi to London and five routes from London to New York.

Illustration 1 - Solution

Considering the journey from a place to another as an event.

  • Total Event (E)

    Journey from New Delhi to New York

The total journey can be sub divided into two sub journeys as

  • 1st sub-event (SE1)

    Journey from New Delhi to London (4 routes)

  • 2nd sub-event (SE2)

    Journey from London to New York (5 routes)

The route to be taken in one part of the journey is not influenced by the route that has been (or has to be) taken in the other part of the journey.

⇒ The two journeys are not dependent on one another

⇒ The sub-events are independent.

The number of ways in which the journey

  • From New Delhi to London can be taken up = 4

    ⇒ nSE1 = 4

  • From London to New York can be taken up = 5

    ⇒ nSE2 = 5

The number of ways in which the total event of travelling from New Delhi to New York can be accomplished

= (Number of ways in which the 1st sub event of traveling from New Delhi to London can be accomplished) × (Number of ways in which the 2nd sub event of traveling from London to New York can be accomplished)

⇒ nE = nE1 × nSE2
= 4 × 5
= 20

Check

Let

A, B, C and D represent the four routes from New Delhi to London.

1, 2, 3, 4 and 5 be the numbers representing the routes from London to New York.

The possibilities can be summarised as

A1 A2 A3 A4 A5
B1 B2 B3 B4 B5
C1 C2 C3 C4 C5
D1 D2 D3 D4 D5

Each choice of the first can be combined with each of the five choices (every choice) of the second.

Illustration 2 - Problem

In how many ways can 3 blue, 2 red and 4 white balls be drawn from a bag containing 6 blue, 4 red and 7 white balls.

(Or)

What are the total number of choices for the event of drawing 3 blue, 2 red and 4 white balls from a bag containing 6 blue, 4 red and 7 white balls.

Illustration 2 - Solution

In the experiment of drawing 9 balls from the bag containing 6 blue, 4 red and 7 white balls .

Total number of balls

= 17 [6 blue + 4 red + 7 white]

Number of balls to be drawn

= 9 [3 blue + 2 red + 4 white]

Considering the act of drawing a set of colored balls as an event

  • Total Event (E)

    Drawing 9 balls from the total 17

By dividing the available balls into groups such that each group consists of balls of a color, the total act of drawing the 9 balls can be sub divided into three sub acts as

  • 1st sub-event (SE1)

    Drawing 3 blue balls from the available 6

  • 2nd sub-event (SE2)

    Drawing 2 red balls from the available 4

  • 2nd sub-event (SE3)

    Drawing 4 white balls from the available 4

Because the number of balls of each color to be picked are specific, the act of picking balls of a color is not influenced by the other acts of picking balls of other colors.

⇒ The three acts are not dependent on one another

⇒ The sub-events are independent.

The number of ways in which the 9 balls can be drawn such that 3 blue, 2 red and 4 white balls are drawn

= (Number of ways in which the 1st sub-event of drawing 3 blue balls from the available 6 can be accomplished) × (Number of ways in which the 2nd sub-event of drawing 2 red balls from the available 4 can be accomplished) × (Number of ways in which the 3rd sub-event of drawing 4 white balls from the available 7 can be accomplished)

⇒ nE = nSE1 × nSE2 × nSE3
= 6C3 × 4C2 × 7C4
=
6 × 5 × 4
3 × 2 × 1
×
4 × 3
2 × 1
×
7 × 6 × 5 × 4
4 × 3 × 2 × 1
= 20 × 6 × 35
= 4,200

Why Combinations and not Permutations?

Consider the event of drawing 2 red balls from the available 4.

Assume that the red balls are labeled r1, r2, r3, r4.

In finding the number of ways in which 2 red balls can be drawn from the available 4, we are only concerned with which 2 balls are being drawn. The possibilities would be
  • r1, r2
  • r1, r3
  • r1, r4
  • r2, r3
  • r2, r4
  • r3, r4

We are not concerned with the order in which the 2 balls are drawn.

Both these drawings would both be interpreted as drawing the two balls r1 and r2.

  • r1 first and r2 next (r1, r2) and
  • r2 first and r1 next (r2, r1)

This implies that the order in which the balls are being drawn is not considered in finding the number of possible choices. Because the order is not important and only the elements of the selection matters, we use combinations.

If the above two possibilities are to be viewed as being different, then we have to consider permutations for finding the number of possible choices.

Working Table

A working table in the format below would be useful in such calculations

Blue Red White Total
Available 6 4 7 17
To Choose 3 2 4 9
Choices 6C34C27C417C9