## Basic Principles of Counting

### Subjects to be Learned

• multiplication principle of counting

### Contents

Suppose that we want to buy a computer from one of two makes A1 and A2 Suppose also that those makes have 12 and 18 different models, respectively. Then how many models are there altogether to choose from ?
Since we can choose one of 12 models of make A1 or one of 18 of A2, there are altogether 12 + 18 = 30 models to choose from.
This is the Addition Principle of Counting. Choosing one from given models of either make is called an event and the choices for either event are called the outcomes of the event. Thus the event "selecting one from make A1", for example, has 12 outcomes. In general it is stated as follows:

Let A1 and A2 be disjoint events, that is events having no common outcomes, with n1 and n2 possible outcomes, respectively. Then the total number of outcomes for the event "A1 or A2" is n1 + n2.

Note that the events must be disjoint, that is they must not have common outcomes for this principle to be applicable.

Example: Suppose there are 5 chicken dishes and 8 beef dishes. How many selections does a customer have ?
In this case, an event is "selecting a dish of either kind". There are 5 oucomes for the chicken event and 8 outcomes for the beef event. According to the addition principle there are 5 + 8 = 13 possible selections.

This addition principle can be generalized for more than two events.

Let A1, A2, ... Ak be disjoint events with n1, n2, ... nk possible outcomes, respectively. Then the total number of outcomes for the event "A1 or A2 or ... or Ak" is n1 + n2 + ... + nk.

### Multiplication Principle

Consider the following problem of purchasing a computer: A manufacturer A offers five different CPU clock rates, four different sizes of RAMs and three different capacities of disks among others. The question is how many different choices of computer there are assuming that everything else is the same for simplicity.
First, there are five possible clock rates. Then for each selection of clock rate one can choose one of four RAM sizes giving 5 * 4 different combinations of clock rate and RAM size. Then for each of those 20 combinations there are three different disk capacities. Thus there are 5 * 4 * 3 = 60 different combinations of configurations altogether. This is the Multiplication Principle of Counting. As in the case of the Addition Principle, selecting one of five (four or three) choices is called an event, and a specific clock rate (RAM size or disk capacity) is called the outcome of the event. In general the Multiplication Principle of Counting is stated as follows:

Multiplication Principle:

Let A1 and A2 be events with n1 and n2 possible outcomes, respectively. Then the total number of outcomes for the sequence of the two events is n1 * n2.

General Multiplication Principle:

Let A1, A2, ... Ak be events with n1, n2, ... nk possible outcomes, respectively. Then the total number of outcomes for the sequence of these k events is n1 * n2 * ... * nk.

Example 1: Suppose that there are three major auto routes from Washington DC to Chicago, and five from Chicago to Los Angeles. Then there are 3 * 5 = 15 major routes from Washington DC to Los Angeles.

Example 2: Suppose that four upper case letters are used for labels. Then 26 * 26 * 26 * 26 = 456,976 different labels are possible.
Suppose that no letters can be duplicated in a label. Then the first letter of a label can be selected from all twenty six letters. The second letter, however, must be selected from twenty five letters because one letter has been selected for the first position and that letter can not be used for the second position. Similarly the third letter is now selected from the remaining twenty four letters and the fourth from twenty three letters. Thus altogether 26 * 25* 24* 23 = 358,800 possible labels exist.

Example 3: The number of subsets of a finite set can be computed using the Multiplication Principle.
Let n be the size of a set A. A subset of A can be constructed by selecting elements of A. That is, for a subset, say B, of A, each element of A is either selected or not selected into B. In this case selecting or not selecting an element is an event. Thus there are n events and each event has two possible outcomes. Applying the Multiplication Principle one can see that there are 2n subsets of A.

### Test Your Understanding of Induction

Indicate which of the following statements are correct and which are not.
Click Yes or No, then Submit. There is one set of questions.

Back to Schedule