Fibonacci and Catalan Numbers E-Book

Ralph Grimaldi

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 531

Veröffentlichungsjahr: 2012

Beschreibung

Discover the properties and real-world applications of the Fibonacci and the Catalan numbers With clear explanations and easy-to-follow examples, Fibonacci and Catalan Numbers: An Introduction offers a fascinating overview of these topics that is accessible to a broad range of readers. Beginning with a historical development of each topic, the book guides readers through the essential properties of the Fibonacci numbers, offering many introductory-level examples. The author explains the relationship of the Fibonacci numbers to compositions and palindromes, tilings, graph theory, and the Lucas numbers. The book proceeds to explore the Catalan numbers, with the author drawing from their history to provide a solid foundation of the underlying properties. The relationship of the Catalan numbers to various concepts is then presented in examples dealing with partial orders, total orders, topological sorting, graph theory, rooted-ordered binary trees, pattern avoidance, and the Narayana numbers. The book features various aids and insights that allow readers to develop a complete understanding of the presented topics, including: * Real-world examples that demonstrate the application of the Fibonacci and the Catalan numbers to such fields as sports, botany, chemistry, physics, and computer science * More than 300 exercises that enable readers to explore many of the presented examples in greater depth * Illustrations that clarify and simplify the concepts Fibonacci and Catalan Numbers is an excellent book for courses on discrete mathematics, combinatorics, and number theory, especially at the undergraduate level. Undergraduates will find the book to be an excellent source for independent study, as well as a source of topics for research. Further, a great deal of the material can also be used for enrichment in high school courses.

Leseprobe

Contents

Cover

Title Page

Copyright

Dedication

Preface

Part One: The Fibonacci Numbers

Chapter 1: Historical Background

Chapter 2: The Problem of the Rabbits

Chapter 3: The Recursive Definition

Chapter 4: Properties of the Fibonacci Numbers

Chapter 5: Some Introductory Examples

Chapter 6: Compositions and Palindromes

Chapter 7: Tilings: Divisibility Properties of the Fibonacci Numbers

Chapter 8: Chess Pieces on Chessboards

Chapter 9: Optics, Botany, and the Fibonacci Numbers

Exercise for Chapter 9

Chapter 10: Solving Linear Recurrence Relations: The Binet Form for Fn

Chapter 11: More on α and β: Applications in Trigonometry, Physics, Continued Fractions, Probability, the Associative Law, and Computer Science

Chapter 12: Examples from Graph Theory: An Introduction to the Lucas Numbers

Chapter 13: The Lucas Numbers: Further Properties and Examples

Chapter 14: Matrices, The Inverse Tangent Function, and an Infinite Sum113

Chapter 15: The gcd Property for the Fibonacci Numbers

Chapter 16: Alternate Fibonacci Numbers

Chapter 17: One Final Example?

References

Part Two: The Catalan Numbers

Chapter 18: Historical Background

Chapter 19: A First Example: A Formula for the Catalan Numbers

Chapter 20: Some Further Initial Examples

Chapter 21: Dyck Paths, Peaks, and Valleys

Chapter 22: Young Tableaux, Compositions, and Vertices and Arcs

Chapter 23: Triangulating the Interior of a Convex Polygon

Chapter 24: Some Examples from Graph Theory

Chapter 25: Partial Orders, Total Orders, and Topological Sorting

Chapter 26: Sequences and a Generating Tree

Chapter 27: Maximal Cliques, a Computer Science Example, and the Tennis Ball Problem

Chapter 28: The Catalan Numbers at Sporting Events

Chapter 29: A Recurrence Relation for the Catalan Numbers

Chapter 30: Triangulating the Interior of a Convex Polygon for the Second Time

Chapter 31: Rooted Ordered Binary Trees, Pattern Avoidance, and Data Structures

Chapter 32: Staircases, Arrangements of Coins, The Handshaking Problem, and Noncrossing Partitions

Chapter 33: The Narayana Numbers

Chapter 34: Related Number Sequences: The Motzkin Numbers, The Fine Numbers, and The Schröder Numbers

Chapter 35: Generalized Catalan Numbers

Chapter 36: One Final Example?

References

Solutions for the Odd-Numbered Exercises

Part One: The Fibonacci Numbers

Part Two: The Catalan Numbers

Index

Copyright © 2012 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New Jersey Published simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Grimaldi, Ralph P.

Fibonacci and catalan numbers: an introduction / Ralph P. Grimaldi.

p. cm.

Includes bibliographical references and index.

ISBN 978-0-470-63157-7

1. Fibonacci numbers. 2. Recurrent sequences (Mathematics) 3. Catalan numbers

(Mathematics) 4. Combinatorial analysis. I. Title.

QA241.G725 2012

512.7'2–dc23

2011043338

Dedicated to the Memory of

Josephine and Joseph

and

Mildred and John

and

Madge

Preface

In January of 1992, I presented a minicourse at the joint national mathematics meetings held that year in Baltimore, Maryland. The minicourse had been approved by a committee of the Mathematical Association of America—the mission of that committee being the evaluation of proposed minicourses. In this case, the minicourse was especially promoted by Professor Fred Hoffman of Florida Atlantic University. Presented in two two-hour sessions, the first session of the minicourse touched upon examples, properties, and applications of the sequence of Fibonacci numbers. The second part investigated comparable ideas for the sequence of Catalan numbers. The audience was comprised primarily of college and university mathematics professors, along with a substantial number of graduate students and undergraduate students, as well as some mathematics teachers from high schools in the Baltimore and Washington, D.C. areas.

Since its first presentation, the coverage in this minicourse has expanded over the past 19 years, as I delivered the material nine additional times at later joint national mathematics meetings—the latest being the meetings held in January of 2010 in San Francisco. In addition, the topics have also been presented completely, or in part, at more than a dozen state sectional meetings of the Mathematical Association of America and at several workshops, where, on occasion, some high school students were in attendance. Evaluations provided by those who attended the lectures directed me to further relevant material and also helped to improve the presentations.

At all times, the presentations were developed so that everyone in the audience would be able to understand at least some, if not a substantial amount, of the material. Consequently, this resulting book, which has grown out of these experiences, should be looked upon as an introduction to the many interesting properties, examples, and applications that arise in the study of two of the most fascinating sequences of numbers. As we progress through the various chapters, we should soon come to understand why these sequences are often referred to as ubiquitous, especially in courses in discrete mathematics and combinatorics, where they appear so very often. For the Fibonacci numbers, we shall find applications in such diverse areas as set theory, the compositions of integers, graph theory, matrix theory, trigonometry, botany, chemistry, physics, probability, and computational complexity. We shall find the Catalan numbers arise in situations dealing with lattice paths, graph theory, geometry, partial orders, sequences, pattern avoidance, partitions, computer science, and even sporting events. xiii

Features

Following are brief descriptions of four of the major features of this book.

1.Useful Resources

The book can be used in a variety of ways:

i. As a textbook for an introductory course on the Fibonacci numbers and/or the Catalan numbers.

ii. As a supplement for a course in discrete mathematics or combinatorics.

iii. As a source for students seeking a topic for a research paper or some other type of project in a mathematical area they have not covered, or only briefly covered, in a formal mathematics course.

iv. As a source for independent study.

2.Organization

The book is divided into 36 chapters. The first 17 chapters constitute Part One of the book and deal with the Fibonacci numbers. Chapters 18 through 36 comprise Part Two, which covers the material on the Catalan numbers. The two parts can be covered in either order. In Part Two, some references are made to material in Part One. These are usually only comparisons. Should the need arise, one can readily find the material from Part One that is mentioned in conjunction with something covered in Part Two.

Furthermore, each of Parts One and Two ends with a bibliography. These references should prove useful for the reader interested in learning even more about either of these two rather amazing number sequences.

3.Detailed Explanations

Since this book is to be regarded as an introduction, examples and, especially, proofs are presented with detailed explanations. Such examples and proofs are designed to be careful and thorough. Throughout the book, the presentation is focused primarily on improving understanding for the reader who is seeing most, if not all, of this material for the first time.

In addition, every attempt has been made to provide any necessary background material, whenever needed.

4.Exercises

There are over 300 exercises throughout the book. These exercises are primarily designed to review the basic ideas provided in a given chapter and to introduce additional properties and examples. In some cases, the exercises also extend what is covered in one or more of the chapters. Answers for all the odd-numbered exercises are provided at the back of the book.

Ancillary

There is an Instructor's Solution Manual that is available for those instructors who adopt this book. The manual can be obtained from the publisher via written request on departmental letterhead. It contains the solutions for all the exercises within both parts of the book.

Acknowledgments

If space permitted, I should like to thank each of the many participants at the minicourses, sectional meetings, and workshops, who were so very encouraging over the years. I should also like to acknowledge their many helpful suggestions about the material and the way it was presented.

The work behind this book could not have been possible without the education I received because of the numerous sacrifices made by my parents Carmela and Ralph Grimaldi. Thanks are also due to Helen Calabrese for her constant encouragement. As an undergraduate at the State University of New York at Albany, I was so very fortunate to have professors like Robert C. Luippold, Paul T. Schaefer, and, especially, Violet H. Larney, who first introduced me to the fascinating world of abstract algebra. When I attended New Mexico State University as a graduate student, there I crossed paths, both inside and outside the classroom, with Professors David Arnold, Carol Walker, and Elbert Walker. They had a definite impact on my education. Even more thanks is due to Professor Edward Gaughan and, especially, my ever-patient and encouraging advisor, Professor Ray Mines. Also, it was on a recent sabbatical at New Mexico State University where I was able to put together so much of the material that now makes up this book. Hence, I must thank their mathematics department for providing me with an office, with such a beautiful view, and the resources necessary for researching so much of what is written here.

One cannot attempt to write a book such as this without help and guidance. Consequently, I want to thank John Wiley & Sons, Inc. for publishing this book. On a more individual level, I want to thank Shannon Corliss, Stephen Quigley, and Laurie Rosatone for their initial interest in the book. In particular, I must acknowledge the assistance and guidance provided throughout the development of the project by my editors Susanne Steitz-Filler and Jacqueline Palmieri. Special thanks are due to Dean Gonzalez for all his efforts in developing the figures. Finally, I must gratefully applaud the constant help and encouagment provided by Senior Production Editor Kristen Parrish who managed to get this author over so many hurdles that seemed to pop up.

I also want to acknowledge the helpful comments provided by Charles Anderson and the reviewers Professor Gary Stevens of Hartwick College and Professor Barry Balof of Whitman College. My past and present colleagues in the Mathematics Department at Rose-Hulman Institute of Technology have been very supportive during the duration of the project. In particular, I thank Diane Evans, Al Holder, Leanne Holder, Tanya Jajcay, John J. Kinney, Thomas Langley, Jeffery J. Leader, David Rader, and John Rickert. I must also thank Dean Art Western for approving the sabbatical which provided the time for me to start writing this book.

I thank Larry Alldredge for his help in dealing with the computer science material, Professor Rebecca DeVasher of the Rose-Hulman Institute of Technology for her guidance on the applications in chemistry, and Professor Jerome Wagner of the Rose-Hulman Institute of Technology for his enlightening remarks on the physics applications.

A book of this nature requires the use of many references. The members of the library staff of the Rose-Hulman Institute of Technology were always so helpful when books and articles were needed. Consequently, it is only fitting to recognize the behind-the-scenes efforts of Jan Jerrell and, especially, Amy Harshbarger.

The last note of thanks belongs to Mrs. Mary Lou McCullough, the now-retired one-time secretary of the Rose-Hulman mathematics department. Although not directly involved in this project, her friendship and encouragement in working with me on several editions of another book and numerous research articles had a tremendous effect on my work in writing this new book. I shall remain ever grateful for everything she has done for me.

Unfortunately, any remaining errors, ambiguities, or misleading comments are the sole responsibility of the author.

Ralph P. Grimaldi

Terre Haute, Indiana

Part One

The Fibonacci Numbers

Chapter 2

The Problem of the Rabbits

In the now famous “Problem of the Rabbits,” Leonardo introduces us to a person who has a pair of newborn rabbits—one of each gender. We are interested in determining the number of pairs of rabbits that can be bred from (and include) this initial pair in a year if

1. each newborn pair, a female and a male, matures in one month and then starts to breed;

2. two months after their birth, and every month thereafter, a now mature pair breed at the beginning of each month. This breeding then results in the birth of one (newborn) pair, a female and a male, at the end of that month; and,

3. no rabbits die during the course of the year.

If we start to examine this situation on the first day of a calendar year, we find the results in Table 2.1 on p. 6.

Table 2.1

We need to remember that at the end of each month, a newborn pair (born at the end of the month) grows to maturity, regardless of the number of days—be it 28, 30, or 31—in the next month. This makes the new maturity entry equal to the sum of the prior maturity entry plus the prior newborn entry. Also, since each mature pair produces a newborn pair at the end of that month, the newborn entry for any given month equals the mature entry for the prior month. From the third column in Table 2.1, we see that at the end of the year, the person who started with this one pair of newborn rabbits now has a total of 233 pairs of rabbits, including the initial pair.

This sequence of numbers—namely, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .—is often called the Fibonacci sequence. The name Fibonacci is a contraction of Filius Bonaccii, the Latin form for “son of Bonaccio,” and the name was given to the sequence in May of 1876 by the renowned French number theorist François Edouard Anatole Lucas (pronounced Lucah) (1842–1891). In reality, Leonardo was not the first to describe the sequence, but he did publish it in the Liber Abaci, which introduced it to the West.

The Fibonacci sequence has proved to be one of the most intriguing and ubiquitous number sequences in all of mathematics. Unfortunately, when these numbers arise, far too many students, and even teachers of mathematics, are only aware of the connection between these numbers and the “Problem of the Rabbits.” However, as the reader will soon learn, these numbers possess a great number of fascinating properties and arise in so many different areas.