Khee Meng Koh - Counting

Preface

Combinatorics is a branch of mathematics dealing with discretely structured problems. Its scope of study includes selections and arrangements of objects with prescribed conditions, configurations involving a set of nodes interconnected by edges (called graphs), and designs of experimental schemes according to specified rules. Combinatorial problems and their applications can be found not only in various branches of mathematics, but also in other disciplines such as engineering, computer science, operational research, management sciences and the life sciences. Since computers require discrete formulation of problems, combinatorial techniques have become essential and powerful tools for engineers and applied scientists, in particular, in the area of designing and analyzing algorithms for various problems which range from designing the itineraries for a shipping company to sequencing the human genome in the life sciences.

The counting problem, which seeks to find out how many arrangements there are in a particular situation, is one of the basic problems in combinatorics. Counting is used in forensic science to calculate the probability that a sample of biological evidence found at the crime scene matches that of a particular accused person. In Chemistry, Cayley used graphs to count the number of isomers of saturated hydrocarbons, while Harary and Read counted the number of certain organic compounds built up from benzene rings by representing them as configurations of hexagons joined together along a common edge. In Genetics, by counting all possibilities for a DNA chain made up of the four bases, scientists arrive at an astoundingly large number and so are able to understand the tremendous possible variation in genetic makeup. Counting has been used as well to study the primary and secondary structures of RNA.

The second edition of Counting brings together the of Counting: Supplementary Chapters and Solutions Manual. The book is intended as an introduction to basic counting techniques for upper secondary to undergraduate students, and teachers. We believe that it would also be of interest to those who appreciate mathematics and to avid puzzle-solvers.

The variety of problems and applications in this book is not only useful for building up an aptitude in counting but is a rich source for honing basic skills and techniques in general problem-solving. Many of the problems evade routine and, as a desired result, force the reader to think hard in his attempts to solve them. In fact, the diligent reader will often discover more than one way of solving a particular problem, which is indeed an important awareness in problem-solving. This book thus helps to provide students an early start to learning problem-solving heuristics and thinking skills.

The first two chapters cover two basic principles, namely, the Addition Principle and the Multiplication Principle. Both principles are commonly used in counting, even by those who would never count themselves as students of mathematics! However, these principles have equally likely been misunderstood and misused. These chapters help to avoid this by stating clearly the conditions under which the principles can be applied. provides various applications of the concepts learnt.

Many apparently complex counting problems can be solved with just a change of perspective. introduces a very useful perspective to which many counting problems can be converted to, i.e. the distribution of balls into boxes. The next three chapters flesh out the Bijection Principle and the distribution perspective with a number of applications and variations.