Catalan numbers with applications

Like the intriguing Fibonacci and Lucas numbers, Catalan numbers are also ubiquitous. "They have the same delightful propensity for popping up unexpectedly, particularly in combinatorial problems," Martin Gardner wrote in Scientific American . "Indeed, the Catalan sequence is probably the most frequently encountered sequence that is still obscure enough to cause mathematicians lacking access to Sloane's Handbook of Integer Sequences to expend inordinate amounts of energy re-discovering formulas that were worked out long ago," he continued.As Gardner noted, many mathematicians may know the abc's of Catalan sequence, but not many are familiar with the myriad of their unexpected occurrences, applications, and properties; they crop up in chess boards, computer programming, and even train tracks. This book presents a clear and comprehensive introduction to one of the truly fascinating topics in mathematics. Catalan numbers are named after the Belgian mathematician Eugene Charles Catalan (1814-1894), who "discovered" them in 1838, though he was not the first person to discover them. The great Swiss mathematician Leonhard Euler (1707-1763) "discovered" them around 1756, but even before then and though his work was not known to the outside world, Chinese mathematician Antu Ming (1692?-1763) first discovered Catalan numbers about 1730.Catalan numbers can be used by teachers and professors to generate excitement among students for exploration and intellectual curiosity and to sharpen a variety of mathematical skills and tools, such as pattern recognition, conjecturing, proof-techniques, and problem-solving techniques. This book is not only intended for mathematicians but for a much larger audience, including high school students, math and science teachers, computer scientists, and those amateurs with a modicum of mathematical curiosity. An invaluable resource book, it contains an intriguing array of applications to computer science, abstract algebra, combinatorics, geometry, graph theory, chess, and World Series. Like the intriguing Fibonacci and Lucas numbers, Catalan numbers are also ubiquitous. "They have the same delightful propensity for popping up unexpectedly, particularly in combinatorial problems," Martin Gardner wrote in Scientific American . "Indeed, the Catalan sequence is probably the most frequently encountered sequence that is still obscure enough to cause mathematicians lacking access to Sloane's Handbook of Integer Sequences to expend inordinate amounts of energy re-discovering formulas that were worked out long ago," he continued. As Gardner noted, many mathematicians may know the abc's of Catalan sequence, but not many are familiar with the myriad of their unexpected occurrences, applications, and properties; they crop up in chess boards, computer programming, and even train tracks. This book presents a clear and comprehensive introduction to one of the truly fascinating topics in mathematics. Catalan numbers are named after the Belgian mathematician Eugene Charles Catalan (1814-1894), who "discovered" them in 1838, though he was not the first person to discover them. The great Swiss mathematician Leonhard Euler (1707-1763) "discovered" them around 1756, but even before then and though his work was not known to the outside world, Chinese mathematician Antu Ming (1692?-1763) first discovered Catalan numbers about 1730. Catalan numbers can be used by teachers and professors to generate excitement among students for exploration and intellectual curiosity and to sharpen a variety of mathematical skills and tools, such as pattern recognition, conjecturing, proof-techniques, and problem-solving techniques. This book is not only intended for mathematicians but for a much larger audience, including high school students, math and science teachers, computer scientists, and those amateurs with a modicum of mathematical curiosity. An invaluable resource book, it contains an intriguing array of applications to computer science, abstract algebra, combinatorics, geometry, graph theory, chess, and World Series. Cover......Page 1 Catalan Numbers with Applications......Page 4 Copyright......Page 5 Preface......Page 8 Contents......Page 12 List of Symbols......Page 14 1 Binomial Coefficients......Page 18 2 The Central Binomial Coefficient......Page 30 3 The Central Binomial Coefficient Revisited......Page 68 4 Binomial Coefficients Revisited......Page 106 5 Catalan Numbers......Page 120 6 The Ubiquity of Catalan Numbers I......Page 166 7 The Ubiquity of Catalan Numbers II......Page 208 8 Trees and Catalan Numbers......Page 244 9 Lattice Paths and Catalan Numbers......Page 276 10 Partitions and Catalan Numbers......Page 298 11 Algebra, Sports, and Catalan Numbers......Page 306 12 Pascal’s Triangle and Catalan Numbers......Page 330 13 Divisibility Properties......Page 346 14 A Catalan Triangle......Page 350 15 A Family of Binary Words......Page 364 16 Tribinomial Coefficients......Page 374 17 Generalized Catalan Numbers......Page 392 A.1 Bijections......Page 396 A.2 Fundamental Counting Principles......Page 397 A.3 Recursion......Page 398 A.4 Generating Functions......Page 399 A.5 Congruences......Page 400 A.6 Mathematical Induction......Page 401 A.7 Extended Binomial Coefficients......Page 402 A.8 Maclaurin’s Series......Page 403 A.9 A Definition of \binom{p/q}{r}......Page 404 Appendix B: The First 100 Catalan Numbers......Page 408 References......Page 412 Index of Mathematicians......Page 426 B......Page 428 C......Page 429 F......Page 431 K......Page 432 M......Page 433 P......Page 434 R......Page 435 T......Page 436 W......Page 438 Z......Page 439 "This comprehensive text presents a clear introduction to one of the truly fascinating topics in mathematics. Teachers and professors can use Catalan numbers to generate excitement among students for exploration, to spur their intellectual curiosity, and to sharpen a variety of mathematical skills and tools, such as pattern recognition, conjecturing, and proof- and problem-solving techniques. This book is intended not only for mathematicians but also for mathematics and science teachers, computer scientists, and those amateurs with a modicum of mathematical curiosity. An invaluable resource book, it contains an intriguing array of applications to computer science, abstract algebra, combinatorics, geometry, graph theory, and chess."--Jacket This book presents a clear and comprehensive introduction to one of the truly fascinating topics in mathematics: Catalan numbers. They crop up in chess, computer programming and even train tracks. In addition to lucid descriptions of the mathematics and history behind Catalan numbers, Koshy includes short biographies of the prominent mathematicians who have worked with the numbers This title presents a comprehensive introduction to Catalan numbers. They crop up in chess, computer programming and even train tracks. In addition to lucid descriptions of the mathematics and history behind Catalan numbers, the author includes short biographies of the prominent mathematicians who have worked with the numbers