THEORY AND PROBLEMS OF

COMBINATORICS

including concepts of GRAPH THEORY

V.K.Balakrishnan

Preface

At an introductory level, combinatorics is usually considered as a branch of discrete mathematics in which the main problem is that of counting the number of ways of arranging or choosing objects from a finite set according to some simple specified rules. Thus the crux of the problem, at the beginning stage at least, is mainly that of enumeration. But if the prescribed rules and constraints become complicated the question to ask naturally is whether an arrangement satisfying the given requirements exists in the first place; if so, in the subsequent analysis one investigates the methods of constructing such arrangements. In some cases these arrangements also have to meet certain optimality criteria, in which case we seek an optimal solution of the problem. A typical statement in some of these optimal situations will assert that the minimum for one kind of a selection will correspond to the maximum for another kind, yielding a "max-min theorem." Thus in a wider sense, combinatorics deals with the enumeration, existence, analysis, and optimization of discrete structures.

Combinatorial mathematics has a variety of applications. It is utilized in several physical and social sciences, for example, chemistry, computer science, operations research, and statistics. Consequently, there has recently been a rapid growth in the depth and breadth of the field of combinatorics. The subject is becoming an increasingly important component of the curriculum both at the graduate and undergraduate levels at universities and colleges in the United States and abroad.

In this book I have attempted to present the important concepts of contemporary combinatorics in a sequence of four chapters. I hope that students will find this book useful for a course in combinatorics or discrete mathematics either as the main text or as a supplementary text. It is designed for students with a wide range of maturity and can also serve as a useful and convenient reference book for many professionals in industry, research, and academe.

In each chapter the basic ideas are developed in the first few pages by giving definitions and statements of theorems to familiarize the reader with concepts that will be fully exploited in the selection of solved problems that follow the text. These problems are grouped by topic and are presented in increasing order of maturity and sophistication. A beginning student may therefore stop at any point and proceed to the next chapter without losing the continuity of the development of the material. The collection of solved problems is the unifying feature of the book.

Unlike other branches of mathematics, in combinatorics the solutions of problems play a special role because in many instances a problem may need an ad hoc argument based on some kind of special insight; that is, it may not be possible to solve it by applying results of known theorems alone. I present a variety of problems covering various branches of the subject. Students are encouraged to try to solve a problem without looking at the solution. The thrill is in solving the problem independently, and the reward is invariably heightened if the student can solve the problem by a different (and possibly more elegant) method. I have used these problems as assignments and projects in my courses on combinatorics and discrete mathematics during the past few years, and the contributions and encouragements of my students-too numerous to mention individually-are gratefully acknowledged.

|Up|

71535427