Fundamental Principles of Counting

Fundamental Principles of Counting

1.1 The Rules of Sum and Product

Our study of discrete and combinatorial mathematics beings with two basic principles of counting: the rules of sum and product. The statements and initial applications of these rules appear quite simple. In analyzing more complicated problems, one is often able to break down such problems into parts that can be solved using these basic Principles. We want to develop the ability to "decompose" such problems and piece together our partial solutions in order to arrive at the final answer. A good way to do this is to analyze and solve many diverse enumeration problems, Taking note of the principles being used. This is the approach we shall follow here.

Our first principle of counting can be stated as follows:

The Rule of Sum:

If a first task can be performed in m ways, while a second task can be performed in n ways, and the two tasks cannot be performed simultaneously, then performing either task can be accomplished in any of m + n ways.

Note that when we say that a particular occurrence, such as a first task, can come about in m ways, these m ways are assumed to be distinct, unless a statement is made to the contrary. This will be true throughout the entire text.

Example 1.1

A College library has 40 textbooks on sociology and 50 textbooks dealing with anthropology. By the rule of sum, a student at this college can select among 40 + 50 = 90 textbooks in order to learn more about one or the other of these two subjects.

Example 1.2

The rule can be extended beyond two tasks as long as no pair of tasks can occur simultaneously. For instance, a computer science instructor who has, say, seven different introductory books each on C++, Java and Perl can recommend any one of these 21 books to a student who is interested in learning a first programming language.

Example 1.3

The computer science instructor of Example 1.2 has two colleagues. One of three colleagues has three textbooks on the analysis of algorithms, and the other has five such textbooks. If n denotes the maximum number of different books on this topic that this instructor can borrow from them, then 5 ≤ n ≤ 8, for here both colleagues may own copies of the same textbook(s).

Example 1.4

Suppose a university representative is to be chosen either from 200 teaching or 300 non-teaching employees, and then there are 200 + 300 = 500 possible ways to choose this representative.

Extension of Sum Rule:

If tasks T1, T2,......., Tm can be done in n1,n2,......, nm ways respectively and no two of these tasks can be performed at the same time, then the number of ways to do one of these tasks is n1 + n2 + .... + nm.

Example 1.5

If a student can chose a project either 20 from mathematics or 35 from computer science or 15 from engineering, then the student can choose a project 20 + 35 + 15 = 70 ways.

The following example introduces our second principle of counting.

Example 1.6

In trying to reach a decision on plant expansion, an administrator assigns 12 of her employees to two committees. Committee A consists of five members and is to investigate possible favorable results from such an expansion. The other seven employees, committee B, will scrutinize possible unfavorable repercussions. Should the administrator decide to speak to just one committee member before making her decision, then by the rule of sum there are 12 employees she can call upon for input. However, to be a bit more unbiased, she decides to speak with a member of committee B on Tuesday, before reaching a decision. Using the following principle, we find that she can select two such employees to speak with in 5 X 7 = 35 ways.

The rule of Product:

If a procedure can be broken down into first and second stages, and if there are m possible outcomes for the first stage and if, for each of these outcomes, there are n possible outcomes for the second stage, then the total procedure can be carried out, in the designated order, in mn ways.

Example 1.7

The drama club of Central University is holding tryouts for a spring play. With six men and eight women auditioning for the leading male and female roles, by the rule of product the director can cast his leading couple in 6 X 8 = 48 ways.

Example 1.8

Here various extensions of the rule are illustrated by considering the manufacture of license plates consisting of two letters followed by four digits.

a) If no letter or digit can be repeated, there are 26 X 25 X 10 X 9 X 8 X 7 = 3,276,000 different possible plates.

b) With repetitions of letters and digits allowed, 26 X 26 X 10 X 10 X 10 X 10 =

6,760,000 different license plates are possible.

c) If repetitions are allowed, as in part (b), how many of the plates have only vowels

(A, E, I, O, U) and even digits? (0 is an even integer)

Example 1.9

In order to store data, a computer's main memory contains a large collection of circuits, each of which is capable of storing a bit -- that is, one of the binary digits 0 or 1. These storage circuits are arranged in units called (memory) cells. To identify the cells in a computer's main memory, each is assigned a unique name called its address. For some computer's, such as embedded microcontrollers (as found in the ignition system for an automobile), an address is represented by an ordered list of eight bits, collectively referred to as a byte. Using the rule of product, there are 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 28 = 256 such bytes. So we have 256 addresses that may be used for cells where certain information may be stored.

A kitchen appliance, such as a microwave oven, incorporates an embedded microcontroller. These "small computers" (such as the PICmicro microcontroller) contain thousands of memory cells and use two-byte addresses to identify these