Counting

Author(s): 
Koh, K.M. (Khee Meng) and Tay, Eng Guan.Koh, Khee Meng is Professor in the Department of Mathematics at the National University of Singapore. Tay, Eng Guam is Assistant Professor in the Mathematics and Mathematics Education Institute at Nanyang Technological University.
Publisher: 
World Scientific Publishing Co. Pte. Ltd. Singapore, River Edge, N. J. 2013. Second Edition, XII, 209 p. Illus., 23cm. Hardcover.
Year: 
2013
ISBN: 
978-981-4401-90-6 (Hardcover); 978-981-4401-91-3 (Softcover, pbk.)
Price (tentative): 
From 2l.30 € (18.00 GBP) (eBook) to 44.95€ (38.00GBP) (Hardcover).
Short description: 

The book begins with the basics of the combinatorial analysis and topics, as a branch of mathematics dealing with discretely structured problems. Its scope of study includes selections and arrangements of objects with established conditions, configurations, and designs of experimental schemes according to determined rules. In short, the counting problem is one of the basic problems in combinatorics, with applications in various branches of mathematics and other disciplines such as engineering, computer science, operational research and life sciences.

This book is a concise, interesting, self-contained, useful, clear, attractive introduction to basic in counting, thinking skills and techniques in general problem solving. It contains numerous exercises, and their solutions, and includes updates on new tools of combinatorics.

In this second edition new chapters are included: the Principle of Inclusion and Exclusion, The Pigeonhole Principle, Recurrence Relations, The Stirling and the Catalan Numbers, with interesting counting arguments, this is why a new edition, (the second edition), seemed appropriate. A good collection of examples and exercises, have also been added to covering a range of difficulties, and a recommended bibliography for further reading, answers to exercises, and index. The book is a beautiful systematic collection of examples and solved exercises, related to 20 different chapters on the basics of the combinatorial theory.

The book helps to give to readers, to all people who appreciate mathematics, to avid puzzle-solvers, to undergraduate students as well as teachers, an early start to learning problem, solving heuristics and ways of counting, and so on.

URL for publisher, author, or book: 
www.worldscientific.com
MSC main category: 
05 Combinatorics
MSC category: 
05AXX, 05CXX, 97KXX, 97MXX
Review: 

The book begins with the basics of the combinatorial analysis and topics, as a branch of mathematics dealing with discretely structured problems. Its scope of study includes selections and arrangements of objects with established conditions, configurations, and designs of experimental schemes according to determined rules. In short, the counting problem is one of the basic problems in combinatorics, with applications in various branches of mathematics and other disciplines such as engineering, computer science, operational research and life sciences.

The book Counting, is self-contained, good, admirably clear, and a stimulating and very well written. This concise introductory text-book is an early start to learning problem solving heuristics and ways of counting. It contains numerous exercises, and their solutions, and includes updates on new tools and techniques in practical combinatorial theory. Not many mathematical prerequisites are needed to read this book because the mathematical material is sufficiently closed.

The aim of the present book is intended not only as an introduction to basic counting techniques for upper secondary to undergraduate students, and teachers, but is a rich source of ideas to describe the main tools and techniques in practical combinatorial theory. For the reader is suitable solving some of the many proposed and solved exercises. ¡Good experience for share seriously the examples and exercises!

I feel sure that it will be of great use both to students of practical combinatorial theory, in particular graph theory, and mathematics, in general, and captivate to students, instructors, puzzle devotees, and teachers in high/secondary schools and colleges.

The book contains preface, table of contents, list de figures (pp. i-xii), and twenty chapters, and a recommended bibliography for further reading, answers to exercises, and index, in 209 p.

The first two chapters cover two basic principles, the addition and the multiplication, both principles are wide and commonly uses in counting. The first chapter, (p. 1-7), introduces the basic, definitions and notions, devoted to present the addition principle and illustrate how it is applied.

This chapter considered four examples and nine exercises, very quite easy. The proposed exercises are solved with their respective solutions, in one appendix on answers to exercises.

In the chapter two, on introduce the multiplication principle, (p. 9-16), with four detailed examples and six exercises, for stimulating to reader and the beginner, even the most requires very little work.

In the chapter three, (p.17-23), Subsets and arrangements, provides the concepts of combinations and permutations by considering as subsets and arrangements of a set of objects. This chapter analyzed how the multiplication principle, by incorporating the addition principle, enables us to solve more complicated problem, in particular four exercises are presented, and solved with their respective solutions.
The chapter four, Applications, (p. 25-33), is completely devoted to various applications of the concepts learnt and now gives some examples to illustrate how the concepts of r-permutations and r-combinations of an n-element set can be applied. On introduce the third basic principle for counting, the principle of complementation. Moreover, six examples and fourteen exercises are proposed.

In the chapter five, the Bijection principle, (p. 35-47), on introduce the fourth basic principle for counting, named the bijection principle, and discuss some of its applications. On presented here three examples and nine interesting exercises for illustrating the mainly concepts.

The chapter six, distribution of balls into boxes, (p. 49-53), introduces a very useful perspective to which many counting problems can be converted to the distribution, for example balls into boxes. Moreover one example is discussed joint four exercises.

The following next three chapters flesh out the Bijection Principle with a number of applications and variations. In particular, the chapter seven, More Applications of Bijection Principle (p. 55-64), on analyzed with details, six examples and fifteen elaborated exercises.

The chapter eight, Distribution of distinct objects into distinct boxes, (p. 65-68), presented two examples and four exercises, related to the distribution problem, that is, the counting of ways of distributing objects into boxes. This is a basic model for many counting problems, because 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. The first case: objects identical and boxes distinct have been studied in chapters 6 and 7. The second case: objects distinct and boxes distinct on analyzed in this chapter. The third case: objects distinct and boxes identical will be discussed in chapter 18 as Stirling numbers of the second type, and finally the fourth case will not touched upon in this book.

The chapter nine, (p. 69-74) deals on other variations of the distribution problem in their cases one and two mentioned above. In this chapter on considered the ordering of objects in each box. Two examples and eight exercises are also presented.

From chapter ten to chapter twelve put this family of combinatorial numbers in the context of the binomial expansions and Pascal´s triangle. A great number of useful identities are proven and problems are posed where theses identities surprisingly appear.

The chapter ten, the binomial expansion, (p.75-78), deals with the binomial theorem and four simple identities involving binomial coefficients, derived easily equivalent formula for the combinatorial number. Moreover, on presented here four proposed exercises, and analyzed their solutions in the answers to exercises.

In the chapter eleven, (p. 79-85), on derived some more identities, involving binomial coefficients from the binomial expansion. These identities are useful in simplifying certain algebraic expressions. Three worked examples and five proposed exercises are presented here.

The chapter twelve, (p. 87-96), is completely devoted to the Pascal´s triangle. An interesting and worked example and eight elaborated exercises are done.

Chapter 13 and Chapter 14 cover the Principle of Inclusion and Exclusion, and its general statement. Many situations of counting are complicated by the possibility of double counting.

In chapter thirteen, the principle of inclusion and exclusion (p. 97-108), added as new in this second edition, express the cardinal of the union of two sets in terms of cardinal of each one regardless of both are disjoint. The resulting identity is a simplest form of a principle called the Principle of Inclusion and Exclusion, a powerful tool in enumeration. Four examples and ten proposed exercises illustrating, this important and surprisingly principle appear.

The chapter fourteen, (p. 109-119), corrected and added in this second edition, extends the principle of inclusion and exclusion to three finite sets, and then to four sets and in general to n≥ 2, finite sets, and if so, what identity would one get in general, for the general statement of the principle of inclusion and exclusion.

The Pigeonhole Principle is studied in chapter fifteen (p. 121-132), the principle not actually count the number ways for a particular situation, it is used to check the existence for a determined setting. The principle deals to transform the particular problem, partly into one of distributing a number of objects into a number of boxes. The principle is very interesting to prove the contra positive statement of any question, and so proves the principle. It also known as the Dirichlet Drawer Principle, used to prove some results in Number Theory. In this chapter on introduces the Ramsey number and the problem of n-coloring edges in complete graph, and so on, as an application of the Pigeonhole Principle. Six examples and nine proposed exercises, and a worked problem with proof illustrating this chapter. This chapter is included in this second edition.

The next four chapters, chapter 16 to chapter 19, also added in this second edition, are on recurrence relations, in a new defiant aspect about the techniques, tools and principles learnt.

The chapter sixteen, (p. 133-146), introduces the technique of using recurrence relations. These represent algebraically the situation where the solution of a counting problem of bigger size can be obtained from the solutions of the same problem but of smaller size one, and so that the original counting problem can be solved. On consider in this chapter, the sequence of Fibonacci numbers, the rabbit problem, the tower of Hanoi, the theory about the last largest prime number of Edouard Lucas, and so on. Two well worked examples and ten proposed exercises, illustrating this chapter

Chapter seventeen to chapter nineteen study three series of numbers which are derived from special recurrence relations. These are the Stirling numbers of the firs kind, the Stirling numbers of the second kind, and Catalan numbers.

In the chapter seventeen, (p. 147-157), devoted completely to the study of the Stirling numbers of the first kind, that is, the coefficient of xk in the expansion of the polynomial in x of degree m, [x]m = {x(x-1)(x-2)…(x-(m-1))}, where 0≤k≤m. This coefficient is designed by s (m, k), because depends on both m and k, and it is called the Stirling number of the first kind, which is purely algebraic in nature. The chapter studied the combinatorial interpretation of the Stirling number of first kind and the corresponding relation for the number of ways of arranging m distinct objects around k identical circles with at least one object at each circle, denoted by s* (m,k), the absolute value of the real number s(m,k). The sequence of numbers s (m, 1), s (m, 2), s (m, m) alternate in sign with s (m, 1) positive when and only when m is odd. These give the mainly combinatorial argument and explain the nature of Stirling numbers. Five interesting exercises, illustrating this chapter

The chapter eighteen, (p. 159-166), introduces the other sequence of Stirling number of the second kind. The Stirling number of the second kind, denoted by S(n,k) and given two positive integers n and k, with k≤n, is defined as the number of ways of dividing n distinct objects into k(nonempty) groups, that is, the number of ways of partitioning an n-element set into k nonempty subsets. The chapter is dedicated to these numbers and their combinatorial interpretations. Moreover, five exercises are proposed.

In the chapter nineteen, (p. 167-178), introduces the Catalan numbers, that just been obtained as the number of shortest routes f(n) from O(0,0) to A(n,n) which do not cross the diagonal y=x in the rectangular coordinate system is given by f(n) = Cn2n/(n+1), combinatorial number 2n over n. The numbers 1, 2, 5, 14, 42, 132, 429 …, Cn2n/ (n+1), ..., are called Catalan numbers after the Belgium Mathematician Eugene Catalan. In particular, the 1-1 correspondences among the routes, the ways of parenthesising x1. x2 … .xn , and the binary sequences, are examples of the Catalan numbers.

It is interesting some more general problem, known as the Ballot Problem as an extension of some problems involves Catalan numbers; the Euler´s Polygon Division Problem; the solution to how many ways are there to pair, 2n (n≥ 1) distinct fixed points on the circumference of a circle using n nonintersecting chords, an others similar problems considered in the specialized literature. Six interesting exercises are proposed in this chapter.

The chapter twenty, miscellaneous problems, (p. 179-195), closes the book with a collection of sixty interesting problems in which the approaches to solving them appear as applications of one or more concepts learnt in all the earlier chapters. The exercises and problems are designed to aid understanding. Some are quite easy, a few are quite difficult, and the other for works adequately. All problems are solved in answers to exercises.

Books recommended for further reading, (p. 197). There is an explicit recommended bibliography with nine references of basic books.

Answers to Exercises, (p. 199-208). There are worked solutions, to quite all of them.

Index (p. 209), of relevant subjects considered.

In this second edition new chapters are included: the Principle of Inclusion and Exclusion, The Pigeonhole Principle, Recurrence Relations, The Stirling and the Catalan Numbers, with interesting counting arguments, this is why a new edition seemed appropriate. A good collection of examples and exercises, have also been added to covering a range of difficulties, and a recommended bibliography for further reading, answers to exercises, and index. The book is a beautiful systematic collection of examples and solved exercises, related to different 20 chapters on the basics of the combinatorial theory.

This book is a concise, interesting, self-contained, useful, clear, attractive introduction to basic in counting, thinking skills and techniques in general problem solving. It contains numerous exercises, and their solutions, and includes updates on new tools of practical combinatorial theory.

Definitely, practical combinatorial theory is considered difficult by students, and by this the book make more accessible with the numerous interesting exercises and applications, to captivate the attention towards an book that helps to give to readers, to all people who appreciate mathematics, to avid puzzle-solvers, to undergraduate students as well as teachers, an early start to learning problem, solving heuristics and ways of counting, and so on.

Reviewer: 
Francisco José Cano Sevilla
Affiliation: 
Profesor Universidad Complutense

Comments

Post new comment

The content of this field is kept private and will not be shown publicly.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.

More information about formatting options

CAPTCHA
This question is for testing whether you are a human visitor and to prevent automated spam submissions.
Image CAPTCHA
Copy the characters (respecting upper/lower case) from the image.
satunnaisuus