Counting

The following sections are included:

• Preface

• Contents

In the process of solving a counting problem, there are two very simple but basic principles that we always apply. They are called the Addition Principle and the Multiplication Principle. In this chapter, we shall introduce the former and illustrate how it is applied…

Mr. Tan is now in town X and ready to leave for town Z by car. But before he can reach town Z, he has to pass through town Y. There are 4 roads (labeled 1, 2, 3, 4) linking X and Y, and 3 roads (labeled as a, b, c) linking Y and Z as shown in Figure 2.1. How many ways are there for him to drive from X to Z?…

There are 25 students in the class. How many ways are there to choose 5 of them to form a committee? If among the chosen five, one is to be the chairperson, one the secretary and one the treasurer, in how many ways can this be arranged? In this chapter, our attention will be focused on the counting problems of the above types. We shall see how (MP) is used to solve such problems, and how (MP), by incorporating (AP), enables us to solve more complicated problems…

Having introduced the concepts of r-permutations and r-combinations of an n-element set, and having derived the formulae for and , we shall now give some examples to illustrate how these can be applied…

We have introduced three basic principles for counting, namely, the (AP), the (MP) and the (CP). In this chapter, we shall introduce another basic principle for counting which we call the Bijection Principle, and discuss some of its applications…

Figure 6.1 shows three distinct boxes into which seven identical (indistinguishable) balls are to be distributed. Three different ways of distribution are shown in Figure 6.2. (Note that the two vertical bars at the two ends are removed.)…

We shall give additional examples in this chapter to show more applications of (BP)…

We have seen from the various examples given in Chapters 6 and 7 that the distribution problem, which deals with the counting of ways of distributing objects into boxes, is a basic model for many counting problems. In distribution problems, objects can be identical or distinct, and boxes too can be identical or distinct. Thus, there are, in general, four cases to be considered, namely…

Two cases of the distribution problem were discussed in the preceding chapters. In this chapter, we shall study some of their variations…

In Chapter 3, we introduced a family of numbers which were denoted by or . Given integers n and r with 0 ≤ r ≤ n, the number is defined as the number of r-element subsets of the set N_n = {1, 2,…, n}. That is, is the number of ways of selecting r distinct objects from a set of n distinct objects. We also derived the following formula for :

We gave four simple identities involving binomial coefficients, namely (10.2)–(10.5), in Chapter 10. In this chapter, we shall derive some more identities involving binomial coefficients from (BT). These identities, while interesting in their own right, are also useful in simplifying certain algebraic expressions…

In Chapter 10, we established the Binomial Theorem (BT) which states that for all nonnegative integers n,

One commercially available ten-button lock may be opened by depressing — in any order — the correct five buttons. The sample shown below has {1,2,3,6,9} as its combination. Suppose that these locks are redesigned so that sets of as many as nine buttons or as few as one button could serve as combinations. How many additional combinations would this allow?…

The following sections are included:

• Books Recommended for Further Reading

• Answers to Exercises

• Index