Fibonacci and Catalan Numbers An Introduction

by Grimaldi, Ralph

• ISBN13: 9780470631577
• ISBN10: 0470631570
• Edition: 1st
• Format: Hardcover
• Copyright: 2012-03-13
• Publisher: Wiley

Summary

In this one-of-a-kind book, Ralph Grimaldi uses his extensive experience from the classroom and as a leader of mini-courses to present an accessible, single resource on the topics of Fibonacci Numbers and Catalan Numbers . The book first embarks on a complete treatment of Fibonacci numbers. Starting with a historical background on the topic, the author goes on to present the properties of Fibonacci numbers, a slew of introductory-level examples, and in-depth discussion of related topics including compositions and palindromes; tiling and Fibonacci numbers; solving linear recurrence relations; graph theory; Lucas numbers; and alternate Fibonacci numbers. The second half of the book explores Catalan numbers, and the author builds a complete foundation to the topic using a historical background and introductory examples, along with coverage of partial orders, total orders, topological sorting, graph theory, rooted ordered binary trees, pattern avoidance, and the Narayana numbers. Coverage of both topics are accompanied by interesting, real-world examples from areas such as sports, botany, and computer science. Each section concludes with detailed exercise sets that can also serve as extended examples of the presented material along with selected solutions. An Instructors Manual featuring complete solutions is available upon written request, and extensive reference sections outline resources for further study of the discussed topics.

Author Biography

RALPH P. GRIMALDI, PhD, is Professor of Mathematics at Rose-Hulman Institute of Technology. With more than forty years of experience in academia, Dr. Grimaldi has published numerous articles in discrete mathematics, combinatorics, and graph theory. Over the past twenty years, he has developed and led mini-courses and workshops examining the Fibonacci and the Catalan numbers.

Table of Contents

Preface	p. xi
The Fibonacci Number
Historical Background	p. 3
The Problem of the Rabbits	p. 5
The Recursive Definition	p. 7
Properties of the Fibonacci Numbers	p. 8
Some Introductory Examples	p. 13
Compositions and Palindromes	p. 23
Tilings: Divisibility Properties of the Fibonacci Numbers	p. 33
Chess Pieces on Chessboards	p. 40
Optics, Botany, and the Fibonacci Numbers	p. 46
Solving Linear Recurrence Relations: The Binet Form for Fn	p. 51
More on ¿ and ß: Applications in Trigonometry, Physics, Continued Fractions, Probability, the Associative Law, and Computer Science	p. 65
Examples from Graph Theory: An Introduction to the Lucas Numbers	p. 79
The Lucas Numbers: Further Properties and Examples	p. 100
Matrices, The Inverse Tangent Function, and an Infinite Sum	p. 113
The gcd Property for the Fibonacci Numbers	p. 121
Alternate Fibonacci Numbers	p. 126
One Final Example?	p. 140
The Catalan Numbers
Historical Background	p. 147
A First Example: A Formula for the Catalan Numbers	p. 150
Some Further Initial Examples	p. 159
Dyck Paths, Peaks, and Valleys	p. 169
Young Tableaux, Compositions, and Vertices and Arcs	p. 183
Triangulating the Interior of a Convex Polygon	p. 192
Some Examples from Graph Theory	p. 195
Partial Orders, Total Orders, and Topological Sorting	p. 205
Sequences and a Generating Tree	p. 211
Maximal Cliques, a Computer Science Example, and the Tennis Ball Problem	p. 219
The Catalan Numbers at Sporting Events	p. 226
A Recurrence Relation for the Catalan Numbers	p. 231
Triangulating the Interior of a Convex Polygon for the Second Time	p. 236
Rooted Ordered Binary Trees, Pattern Avoidance, and Data Structures	p. 238
Staircases, Arrangements of Coins, The Handshaking Problem, and Noncrossing Partitions	p. 250
The Narayana Numbers	p. 268
Related Number Sequences: The Motzkin Numbers, The Fine Numbers, and The Schroder Numbers	p. 282
Generalized Catalan Numbers	p. 290
One Final Example?	p. 296
Solutions for the Odd-Numbered Exercises	p. 301
Index	p. 355
Table of Contents provided by Ingram. All Rights Reserved.