Издательство Academic Press, 1972, -310 pp.
Combinatorics, or discrete mathematics, and its applications are becoming increasingly important. Polya has said that Combinatorics is an experimental science today just as analysis was decades ago. It is well that students encoun- encounter this branch of mathematics at an early level so that they may appreciate that Combinatorics has become a partner with traditional mathematics and with computer science. This book is written to provide an introductory course at the sophomore or junior level.
Because there is so much elementary Combinatorics it is not necessary to wait until the senior years to study the subject. Extensive prerequisites are not necessary. Some knowledge of permutations and combinations, mathematical induction, the binomial theorem, and set theory will allow the student to investigate a host of combinatorial problems and applications. Matrices and determinants are useful but are not prerequisites at the level of this book.
It is possible to- select topics which present to the student some quite challenging mathematics. Indeed, in offering him a kaleidoscope of interesting and easily understood topics, chosen to appeal to his imagination, it is often possible to point to some current related research. In addition, a beginning course in these areas can have considerable charm. Its charm does not come from a lack of discipline in the course but from the mathematics involved.
Much Combinatorics has arisen from games and puzzles. Giants such as Gauss, Euler, and Hamilton were interested in puzzles and J. L. Synge has said " The mind is at its best when at play." It is not inappropriate to exploit this point of view in an introductory combinatorics course, again, one hopes stimulating an increase in interest in Mathematics on the part of the student.
A formal definition of Combinatorics is difficult to formulate. Combina- Combinatorial problems occur in every branch of mathematics. Roughly speaking, Combinatorics is a study of the arrangements of elements into sets and deals with two general types of problems, enumeration and existence. Recent activity in Combinatorics has been stimulated by applications to other subjects. Thus it seemed logical to us to organize this book into three sections, Enumeration, Existence, and Applications. These three sections follow a chapter of introductory examples. Each of these sections has its own intro- introduction which the reader may consult for further information. The authors have provided more material than normally can be covered in a term course so that the instructor using the book will have considerable latitude in selecting his course content.
The book is primarily problem-oriented. Exercises appear at the end of each section. We believe that mathematics can be leaed only by doing mathematics and this involves the solution of a wide range of problems. In offering a course using this text we have found that formal lectures are not always necessary. We have experimented successfully with the group method.
The class has been divided into groups of five students, each group with a leader from among the five students. The groups have spent classroom hours primarily discussing theory and working problems, with supplementary lec- lectures from time to time, where deemed necessary. Graduate students have been available both in the classroom and outside at specified tutorial hours to help group leaders prepare for their next class discussion or to clear up un- unsolved problems. It is our hope that the students gain more understanding from this active involvement in the class structure.
In order that this book be readable and, we hope, of interest to and useable by a wide range of students, we have written with an approach some- somewhere between the intuitive and the rigorous, but much closer to the former. We have discussed theorems, for example, in a number of different ways. Some we have proved formally; more have been presented informally. Occasionally proofs are demonstrated by examples which give all the steps and reasoning necessary for a formal proof and the reader is asked to com- complete many of these in the Exercises. Some difficult theorems are stated without proof but with references given.
Combinatorics has become an important tool of the computer scientist. For this reason we have attempted to provide problems that could be of interest to the student of computer science. These problems can be omitted by students who do not have access to a computer without loss of comprehension in the rest of the course.
A course based on this book can be useful not only to the student of computer science and to the mathematics major but also to the student in liberal arts or social science, especially in economics and psychology where Combinatorics is beginning to play an important role. Finally, we hope that this book will be to many students what the title states, an introduction to Combinatorics, which will lead him to a desire to lea more about this fascinating subject.
Introductory Examples.
Enumeration.
permutations and Combinations.
The Inclusion-Exclusion Principle.
Linear Equations with Unit Coefficients.
Recurrence Relations.
Generating Functions.
Existence.
some Methods of Proof.
Geometry of the Plane.
Maps on a Sphere.
Coloring Problems.
Finite Structures.
Applications.
probability.
Ramifications of the Binomial Theorem.
More Generating Functions and Difference Equations.
Fibonacci Sequences.
Arrangements.
Answers to Selected Exercises.
Combinatorics, or discrete mathematics, and its applications are becoming increasingly important. Polya has said that Combinatorics is an experimental science today just as analysis was decades ago. It is well that students encoun- encounter this branch of mathematics at an early level so that they may appreciate that Combinatorics has become a partner with traditional mathematics and with computer science. This book is written to provide an introductory course at the sophomore or junior level.
Because there is so much elementary Combinatorics it is not necessary to wait until the senior years to study the subject. Extensive prerequisites are not necessary. Some knowledge of permutations and combinations, mathematical induction, the binomial theorem, and set theory will allow the student to investigate a host of combinatorial problems and applications. Matrices and determinants are useful but are not prerequisites at the level of this book.
It is possible to- select topics which present to the student some quite challenging mathematics. Indeed, in offering him a kaleidoscope of interesting and easily understood topics, chosen to appeal to his imagination, it is often possible to point to some current related research. In addition, a beginning course in these areas can have considerable charm. Its charm does not come from a lack of discipline in the course but from the mathematics involved.
Much Combinatorics has arisen from games and puzzles. Giants such as Gauss, Euler, and Hamilton were interested in puzzles and J. L. Synge has said " The mind is at its best when at play." It is not inappropriate to exploit this point of view in an introductory combinatorics course, again, one hopes stimulating an increase in interest in Mathematics on the part of the student.
A formal definition of Combinatorics is difficult to formulate. Combina- Combinatorial problems occur in every branch of mathematics. Roughly speaking, Combinatorics is a study of the arrangements of elements into sets and deals with two general types of problems, enumeration and existence. Recent activity in Combinatorics has been stimulated by applications to other subjects. Thus it seemed logical to us to organize this book into three sections, Enumeration, Existence, and Applications. These three sections follow a chapter of introductory examples. Each of these sections has its own intro- introduction which the reader may consult for further information. The authors have provided more material than normally can be covered in a term course so that the instructor using the book will have considerable latitude in selecting his course content.
The book is primarily problem-oriented. Exercises appear at the end of each section. We believe that mathematics can be leaed only by doing mathematics and this involves the solution of a wide range of problems. In offering a course using this text we have found that formal lectures are not always necessary. We have experimented successfully with the group method.
The class has been divided into groups of five students, each group with a leader from among the five students. The groups have spent classroom hours primarily discussing theory and working problems, with supplementary lec- lectures from time to time, where deemed necessary. Graduate students have been available both in the classroom and outside at specified tutorial hours to help group leaders prepare for their next class discussion or to clear up un- unsolved problems. It is our hope that the students gain more understanding from this active involvement in the class structure.
In order that this book be readable and, we hope, of interest to and useable by a wide range of students, we have written with an approach some- somewhere between the intuitive and the rigorous, but much closer to the former. We have discussed theorems, for example, in a number of different ways. Some we have proved formally; more have been presented informally. Occasionally proofs are demonstrated by examples which give all the steps and reasoning necessary for a formal proof and the reader is asked to com- complete many of these in the Exercises. Some difficult theorems are stated without proof but with references given.
Combinatorics has become an important tool of the computer scientist. For this reason we have attempted to provide problems that could be of interest to the student of computer science. These problems can be omitted by students who do not have access to a computer without loss of comprehension in the rest of the course.
A course based on this book can be useful not only to the student of computer science and to the mathematics major but also to the student in liberal arts or social science, especially in economics and psychology where Combinatorics is beginning to play an important role. Finally, we hope that this book will be to many students what the title states, an introduction to Combinatorics, which will lead him to a desire to lea more about this fascinating subject.
Introductory Examples.
Enumeration.
permutations and Combinations.
The Inclusion-Exclusion Principle.
Linear Equations with Unit Coefficients.
Recurrence Relations.
Generating Functions.
Existence.
some Methods of Proof.
Geometry of the Plane.
Maps on a Sphere.
Coloring Problems.
Finite Structures.
Applications.
probability.
Ramifications of the Binomial Theorem.
More Generating Functions and Difference Equations.
Fibonacci Sequences.
Arrangements.
Answers to Selected Exercises.